Matematicas Finitas

Cap´ ıtulo 1 N´ meros primos y compuestos u
En este cap´ ıtulo consideraremos algunas propiedades del conjunto de los n´meros u enteros y positivos: 1, 2, 3, . . . Es costumbre utilizar la letra N para designar a dicho conjunto, as´ como Z es la notaci´n usual en Matem´ticas para representar al ı o a conjunto de todos los n´meros enteros (positivos, negativos y cero). La aritm´tica u e elementalse ocupa del estudio de las operaciones b´sicas de los enteros, suma, resa ta y multiplicaci´n y, junto con la Geometr´ Eucl´ o ıa ıdea, constituye los cimientos y aporta los primeros modelos sobre los que luego se construyen y conforman otras ramas de la Matem´tica. En los sucesivo supondremos ciertos conocimientos de la a Aritm´tica elemental para pasar directamente a estudiar la relaci´n dedivisibilidad. e o

1.1.

El teorema fundamental de la aritm´tica e

Un entero positivo p > 1 es un n´mero primo si sus unicos divisores positivos u ´ son 1 y p. Por ejemplo los n´meros 2, 3, 5, 7, 11, 13 son primos. Los enteros positivos u mayores que 1 que no son primos se llaman compuestos. El concepto de n´mero primo se remonta a la antig¨edad. Los griegos pose´ u u ıan dicho concepto, as´como una larga lista de teoremas y propiedades relacionadas con ı ´l. Los cuatro ejemplos siguientes aparecen el Los Elementos de Euclides: e Todo entero positivo, distinto de 1, es un producto de primos. Teorema fundamental de la aritm´tica: Todo entero positivo puede descome ponerse de manera unica en un producto de primos. ´ Existen infinitos n´meros primos. u 1

2

´ CAP´ ITULO 1. NUMEROSPRIMOS Y COMPUESTOS Podemos obtener una lista de los n´meros primos por medio del m´todo conou e cido con el nombre de Criba de Erat´stenes. o

Estas propiedades justifican la importancia de los n´meros primos y la curiosiu dad que han inspirado entre los matem´ticos de todas las ´pocas. a e Proposici´n 1.1.1. Todo entero positivo mayor que 1 es un producto de n´meros o u primos. Demostraci´n.Por inducci´n. La hip´tesis es cierta en el caso n = 2. Supong´mosla o o o a cierta para n ≤ m y probemos que m + 1 es un producto de primos. Si tenemos tanta suerte que m + 1 es primo, entonces no hay nada que demostrar; en caso contrario m + 1 se podr´ escribir de la forma m + 1 = n1 n2 con a 1 < n1 ≤ n2 < m + 1. Por ser n1 y n2 menores que m + 1 y mayores que 1, ambos ser´n productos de primos ytambi´n lo habr´ de ser m + 1. a e a Sean a y b dos n´meros enteros alguno de los cuales es distinto de 0. El m´ximo u a com´n divisor de a y b es el mayor entero positivo (a, b) que divide a ambos a y b. El u caso en que (a, b) = 1 recibe un nombre especial, se dice que a y b son primos relativos o primos entre s´ El m´ ı. ınimo com´n m´ltiplo [a, b] es el menor entero no negativo u u que esdivisible por a y por b. Si a y b son primos relativos entonces [a, b] = |ab|. En general se verifica que |ab| = (a, b)[a, b]. Proposici´n 1.1.2 (Algoritmo de la divisi´n). Dados dos enteros cualesquiera a y o o b (a > 0), existen dos unicos enteros q y r tales que b = aq + r, 0 ≤ r < a. Si a b ´ entonces 0 < r < a. e u Demostraci´n. Consid´rese el conjunto {b − qa, q ∈ Z}. Sea r el menor n´mero no onegativo de la sucesi´n. Obviamente r = b − qa para alg´n q. Es claro que r < a. o u En caso contrario 0 ≤ b − (q + 1)a = r − a < r y entonces r no ya ser´ el m´ ıa ınimo entero positivo con esa propiedad. La unicidad de r implica la de q. Algoritmo de Euclides. Supongamos que a > b y a = bc + r, a ≤ r < b. Es claro que todo divisor com´n de a y b lo es tambi´n de b y r, y viceversa. En u eparticular (a, b) = (b, r). Esta estrategia puede ser iterada. El ultimo resto distinto ´ de 0 es el m´ximo com´n divisor de los n´meros a y b. a u u Proposici´n 1.1.3. Fijados b y c, existen enteros x0 y y0 tales que (b, c) = bx0 +cy0 . o Demostraci´n. Consideremos el menor entero positivo l del conjunto {bx + cy : o x, y ∈ Z}. Sea l = bx0 + cy0 . Si l b, existen q y r tales que b = lq + r, 0 < r <...