Matematica discreta

Apuntes de Matem´tica Discreta a 11. Teorema Fundamental de la Aritm´tica e

Francisco Jos´ Gonz´lez Guti´rrez e a e
C´diz, Octubre de 2004 a

Universidad de C´diz a

Departamento de Matem´ticas a

ii

Lecci´n 11 o

Teorema Fundamental de la Aritm´tica e
Contenido
11.1 N´ meros Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u 11.1.1 Definici´n . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 11.1.2 N´meros Primos entre s´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u ı 11.1.3 Proposici´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 11.1.4 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Criba de Erat´stenes . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . o 11.2.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Teorema Fundamental de la Aritm´tica . . . . . . . . . . . . . . . . . . . . . e 11.3.1 Lema de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3.2 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 11.3.3 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3.4 Teorema Fundamental de la Aritm´tica . . . . . . . . . . . . . . . . . . . . . . e 11.3.5 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4 Divisores de un N´ mero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u11.4.1 Criterio General de Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4.2 Obtenci´n de todos los Divisores de un N´mero . . . . . . . . . . . . . . . . . . o u 11.4.3 N´mero de Divisores de un N´mero Compuesto . . . . . . . . . . . . . . . . . . u u 11.4.4 Suma de los Divisores de un N´mero Compuesto . . . . . . . . . . . . . . . . . u 11.5 M´todo para el C´lculo del M´ximoCom´ n Divisor y el M´ e a a u ınimo Com´ n u M´ ltiplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u 11.5.1 Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.5.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.5.3 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 316 316 316 317 318 323 323 325 325 325 326 329 331 332 332 332 333 335 339 340 340 341

El concepto de n´mero primo se remonta a la antig¨edad. Los griegos pose´ dicho concepto, as´ como u u ıan ı una larga lista de teoremas y propiedades relacionados con ´l. Los cuatro ejemplos siguientes aparecen e en los Elementos de Euclides: − Todo entero positivo distinto de 1 es unproducto de n´meros primos. u − Teorema fundamental de la Aritm´tica: “Todo entero positivo puede descomponerse de manera e unica como un producto de n´meros primos”. ´ u − Existen infinitos n´meros primos. u 315

Universidad de C´diz a

Departamento de Matem´ticas a

− Podemos obtener una lista de los n´meros primos por medio del m´todo conocido como la Criba u e de Erat´stenes. o

11.1N´ meros Primos u

Observemos que si a es cualquier n´mero entero mayor que 1, entonces u a = a · 1, con 1 ∈ Z, es decir, a es un divisor de a. a = 1 · a, con a ∈ Z, es decir, 1 es un divisor de a.

luego todo n´mero entero a > 1 tiene, al menos, dos divisores, el 1 y el propio a. u

11.1.1

Definici´n o

Diremos que el n´mero entero p > 1 es un n´mero primo si los unicos divisorespositivos que tiene u u ´ son 1 y p. Si un n´mero entero no es primo, lo llamaremos compuesto. u En el conjunto de los diez primeros n´meros enteros positivos son primos 2, 3, 5 y 7, siendo compuestos u 4, 6, 8, 9 y 10. Nota 11.1 Obs´rvese que de la definici´n de n´mero primo se sigue que e o u p es primo si, y s´lo si es imposible escribir p = ab con a, b ∈ Z y 1 < a, b < p. o

11.1.2

N´ meros...