Taller de Matemáticas y Física CIMAT, 4-8 Agosto, 1997

Teoría de Números

Plan general: 1. Introducción y conceptos básicos

• Divisibilidad de enteros

• Números primos

• El Teorema Fundamental de la Aritmética

• La sucesión de los primos

• Algunas preguntas acerca de los primos

• La demostración del Teorema Fundamental de la Aritmética

2. Congruencias

• Definición de congruencias

• Propiedades elementales de congruencias

• El “pequeño’’ teorema de Fermat

1 Introducción y conceptos básicos

1.1 Divisibilidad de enteros

Los números

…, −3, −2, −1, 0, 1, 2, …

se llaman los enteros; los números

0, 1, 2, 3, …

los enteros no-negativos; y los números

1, 2, 3 …

los enteros positivos. Los enteros positivos forman la materia prima de la aritmética, pero a veces es esencial considerarlos como una sub-clase de una clase más amplia de números como los enteros.

Se dice que un entero n es divisible por otro entero d, distinto de cero, si existe un entero, digamos m, tal que n = d · m.

Si n y d son positivos, m también es necesariamente positivo. Expresamos el hecho que n es divisible por d, o que d es un divisor de n, por

d|n.

Así tenemos que

1|n y n|n,

para todo n, y d|0 para todo d ≠ 0.

Es bastante fácil demostrar que

a|b, b|c ⟹ a|c,  (1)
a|b ⟹ ac|bc,  (2)
a|b, a|c ⟹ a| (bm + cn)  (3)

para todo m, n enteros. (La notación “A ⟹ B’’ significa “el hecho A implica el hecho B’’).

Demostramos (1): Si a|b entonces existe un entero m_{1} tal que b = am_{1}; y si b|c existe un entero m_{2} tal que c = bm_{2}. Llamamos m al producto m_{1}m_{2}; entonces tenemos que c = bm_{2} = (am_{1})m_{2} = a(m_{1}m_{2}) = am, así que a|c, según la definición. Dejamos la demostración de (2) y (3) como un ejercicio.

1.2 Números primos

Entre los enteros positivos hay una sub-clase de importancia particular, la clase de los primos. Un número entero positivo p se llama primo si

(i) p > 1,

(ii) p no tiene divisores positivos además de 1 y p.

Por ejemplo, 37 es un primo. Es importante notar que 1 no se considera primo. Normalmente reservamos la letra p para los primos.

Un número entero positivo mayor que 1 y no primo se llama compuesto. Aquí está nuestro primer teorema:

Teorema 1 Todo entero positivo, con excepción del 1, es un producto de primos.

Demostración. Sea n un entero positivo mayor que 1. Si n es primo, no hay nada que probar. Si n no es primo, o sea compuesto, entonces tiene divisores entre 1 y n. Si m es el más pequeño entre estos divisores, m debe ser primo; porque si no, entonces m tendría un divisor l, 1 < l < m, que necesariamente sería también un divisor de n. Esto contradice la elección de m como el divisor más pequeño; así que m debe ser primo.

Concluimos entonces que si n no es primo es divisible por un primo, digamos p_{1}, o sea

n = p_{1}n_{1},

donde n_{1} es un entero positivo, 1 < n_{1} < n. Si n_{1} es primo la demostración está terminada, y si no, continuamos como antes: n_{1} es divisible por un primo p_{2} menor que n_{1}, así que

n = p_{1}n_{1} = p_{1}p_{2}n_{2},

donde n_{2} es un entero positivo, 1 < n_{2} < n_{1} < n.

Así seguimos y obtenemos una suceción decreciente de enteros positivos n > n_{1} > n_{2} > n_{3} > … > 1. Tarde o temprano este proceso tiene que parar, o sea obtenemos un n_{k} = p_{k} primo, y

n = p_{1}p_{2}p_{3} … p_{k−1}p_{k}.  (4)

Esto completa la demostración. □

Por ejemplo, si empezamos con 666, obtenemos

666 = 2 · 3 · 3 · 37.

Ahora una observación que nos ayuda a averiguar si un entero n es compuesto o primo: si n = a · b, entonces a y b no pueden ser ambos mayores que \sqrt{n}, así que si n es compuesto, es divisible por un primo no mayor que \sqrt{n}. Por ejemplo, para averiguar si 79 es un primo, es suficiente verificar si tiene un divisor primo menor que 9 (notando que 8 < \sqrt{79} < 9). Como 2,3,5 y 7 no dividen a 79 concluimos que 79 es un primo.

Los primos en la factorización (4) no son necesariamente distintos, o arreglados en un orden particular. Si los arreglamos en orden creciente, agrupando conjuntos de primos idénticos en un único factor, y cambiamos la notación un poco, obtenemos

n = p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}} … p_{k}^{a_{k}},  (5)

donde a_{1}, a_{2}, … son enteros positivos. Decimos entonces que n está expresado en forma estandar. Por ejemplo,

169400 = 2^{3} · 5^{2} · 11^{2}

es una expresión de 169400 en forma estandar.

1.3 El Teorema Fundamental de la Aritmética

No hay nada en la demostración del Teorema 1 que nos asegure que la expresión de n como un producto de primos es única, salvo orden de los factores, o dicho de otra manera, que n tiene una sola forma estandar. Pero si consideramos algunos casos particulares sospechamos que esto es cierto.

Teorema 2 (“El Teorema Fundamental de la aritmética’’) La forma estandar de un entero positivo n es única; en otras palabras, se puede expresar n como un producto de primos en solo una manera, salvo por el orden de los factores.

El teorema 2, como su nombre implica, es muy básico, e indispensable para el estudio sistemático de los números enteros. Al parecer, el teorema fue anunciado explicitamente por primera vez por el matemático alemán Carl Friedrich Gauss (1777-1855) en su libro Disquisitiones arithmeticae (1801), aunque sin duda el resultado ya era conocido antes de Gauss. La demostración del teorema no es muy difícil, pero sí un poco larga. Por el momento la posponemos.

Ahora, debe ser obvio porque insistimos que 1 no sea primo. Si lo fuera, tendríamos que corregir el Teorema 2, pues siempre podría uno añadir cualquier número de 1’s en la forma estandar.

Damos ahora algunas ilustraciones de la utilidad de nuestro Teorema Fundamental.

Un entero positivo d que divide a dos enteros a y b simultáneamente, d|a y d|b, se llama un divisor común de a y b. Obviamente, d ≤ min{a, b} (el mínimo entre a y b). Denotamos el divisor común máximo de a y b por (a, b). Por ejemplo, (4, 6) = 2, y si a > 0 entonces (a, 0) = (−a, 0) = a.

Si (a, b) = 1 decimos que a y b son primos relativos, o coprimos. Por ejemplo, 9 y 14 son primos relativos. Usando el Teorema Fundamental obtenemos una fórmula sencilla para (a, b).

Teorema 3 Si

a = Π_{p}p^{α} (α ≥ 0)

y

b = Π_{p}p^{β} (β ≥ 0),

entonces

(a, b) = Π_{p}p^{min{α,β}}.

La notación a = Π_{p}p^{α} es una notación breve para la factorización de a en primos, y significa que estamos considerando un producto de términos de la forma p^{α}, para todo los primos p, donde la potencia α depende de p. Por su puesto, los α’s son todos ceros excepto para un número finito de primos, así que el producto es realmente finito.

El teorema es una consecuencia inmediata del Teorema Fundamental y dejamos la demostración como un ejercicio.

Por ejemplo, para obetener el divisor común maximal de 79380 y 2142, calculamos primero sus formas estandar,

79380 = 2^{2} · 3^{4} · 5 · 7^{2}, 2142 = 2 · 3^{2} · 7 · 17,

y obtenemos inmediatamente que su divisor común máximo es

2 · 3^{2} · 7 = 126.

El mínimo común múltiple de dos números a y b es el positivo mínimo divisible por ambos a y b, y está denotado por {a, b}. Tenemos entonces que a|{a, b}, b|{a, b}.

Teorema 4 En la notación del Teorema 3,

{a, b} = Π_{p}p^{max{α,β}}.

Por ejemplo, el mínimo común múltiple de 79380 = 2^{2} · 3^{4} · 5 · 7^{2} y 2142 = 2 · 3^{2} · 7 · 17 es

2^{2} · 3^{4} · 5 · 7^{2} · 17 = 1, 349, 460.

Dejamos la demostración de este teorema también como un ejercicio.

Teorema 5

\{a, b\} = \frac{ab}{(a, b)}.

Demostración. Es una consecuencia de los dos teoremas anteriores y la identidad obvia

min{α, β} + max{α, β} = α + β.
□

Otro resultado básico que derivamos del Teorema Fundamental es

Teorema 6 Si p es un primo, y p|ab, entonces p|a ó p|b.

La condición de ser primo es claramente esencial; por ejemplo, 6|3 · 4, pero 6 no divide a 3 ni a 4.

Demostración. Escribimos a y b como productos de primos, a = p_{1}p_{2} …, b = q_{1}q_{2} …, así que ab = p_{1}p_{2} … q_{1}q_{2} . . .. Segun el Teorema Fundamental, si p|ab entonces p debe ser uno de los primos en la expresion de ab como producto de primos; o sea p es uno de los p_{i}’s o uno los q_{j}’s. En el primer caso p|a, y en el segundo caso p|b. □

Presentamos una aplicación interesante de este último teorema. Primero una definición: un número, no necesariamente entero, es racional, si se puede expresar como la razón de dos enteros m/n. Un número no racional se llama irracional.

Si construimos un triángulo rectángulo con dos lados de longitud 1, la longitud l del tercer lado, la hipotenusa, satisface, según el teorema de Pitágoras,

l^{2} = 2,

o sea l = \sqrt{2}.

Teorema 7 \sqrt{2} es irracional.

Demostración. Si lo fuera, entonces podríamos escribir \sqrt{2} = m/n, con m y n enteros positivos, y suponer también que son primos relativos, (m, n) = 1. Así que 2n^{2} = m^{2} y 2|m^{2}. Como 2 es un primo, el teorema anterior implica que 2|m, así que m = 2k, donde k es un entero positivo. Obtenemos entonces

2n^{2} = (2k)^{2} = 4k^{2} ⟹ n^{2} = 2k^{2}.

Ahora tenemos 2|n^{2} ⟹ 2|n, así que 2 es un divisor común de m y n, contradiciendo la suposición original. □

1.4 La sucesión de los primos

Los primeros primos son

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, …

Es fácil construir una tabla de primos, hasta un límite N no muy grande, por una técnica conocida como la ”criba de Eratostenes”. Ya hemos visto que si n ≤ N, y n no es primo, o sea n es compuesto, entonces n debe ser divisible por un primo no más grande que \sqrt{N} . Ahora escribimos una lista de los números

2, 3, 4, 5, …, N

y eliminamos sucesivamente

(i) 4, 6, 8, 10, …, o sea 2^{2} y luego cada número par,

(ii) 9, 15, 21, 27, …, o sea 3^{2}, y luego todos los múltiplos de 3 no eliminados todavía,

(iii) 25, 35, 55, 65, …, o sea 5^{2}, el cuadrado del siguiente número que queda, y luego todos los múltiplos de 5 no eliminados todavia,...

Así continuamos el proceso hasta que el siguiente número que queda, despues del último número cuyos múltiplos fueron eliminados, es mayor que \sqrt{N}. Los números que quedaron, los que no fueron eliminados por la criba, son todos los primos entre 1 y N. Prácticamente todas las tablas de primos están construidas por este método.

Las tablas indican que la sucesión de los primos es infinita. El número total de primos menores que 10 millones es 664,579, y el número de primos que hay entre 9,900,000 y 10,000,000 es 6,134. El número total de primos menores que 1,000,000,000 es 50,847,478. Se conocen también unos primos muy grandes, la mayoría de la forma 2^{m} − 1. Los más grandes conocidos tienen miles de dígitos y se siguen encontrando más y más grandes todo el tiempo.

Todo esto sugiere el siguiente teorema de Euclides.

Teorema 8 El número de primos es infinito.

Demostración. Existen varias demostraciones del teorema. Presentamos la demostración original de Euclides.

Sean 2, 3, 5, …, p todos los primos entre 2 y un primo p, y vamos a demostrar la existencia de un primo nuevo, mayor que p. Sea

N = (2 · 3 · 5 · . . . · p) + 1.

Si N no es primo es divisible por un primo. Pero N no es divisible por ninguno de los primos 2, 3, 5, …, p (dividiendo a N por cualquiera de estos números da residuo 1), así que si N no es primo es divisible por un primo entre p y N. De cualquier modo obtenemos un primo mayor que p. □

Por ejemplo, empezando con el primo 2, obtenemos por el método de esta demostración una suceción de primos

2, 3, 7, 43, 1907, …

Este método no es muy efectivo – hay maneras mucho mejores de encontrar primos – pero tiene la virtud de convertir a la demostración de Euclides en una demostración constructiva: el argumento de Euclides no solo muestra que el número de primos es infinito, sino también nos construye, paso por paso, una sucesión infinita de primos.

1.5 Algunas preguntas acerca de los primos

La distribución de los primos entre los enteros positivos, en “promedio’’, es muy regular; su densidad muestra una disminución continua pero lenta. El número de primos en los primeros 5 “bloques’’ de 1000 es

168, 135, 127, 120, 119,

y los de los últimos 5 bloques menores que 10,000,000 son

62, 58, 67, 64, 53.

Estos últimos 53 primos estan divididos en grupos de

5, 4, 7, 4, 6, 3, 6, 4, 5, 9

entre los 10 “bloquecitos’’ de 100 del último millar.

Por otro lado, la distribución detallada de los primos es extremadamente irregular. En primer lugar, las tablas muestran bloques grandes de números compuestos. Después del primo 370,261 hay un bloque de 111 números compuestos. Es bastante fácil ver que estos bloques grandes de compuestos deben ocurrir: tomamos todos los primos

2, 3, 5, …, p

hasta un primo p. Si definimos

N = 2 · 3 · 5 · . . . · p,

tenemos que todos los p − 1 números

N + 2, N + 3, N + 4, …, N + p

son compuestos. Esto es cierto porque si tomamos uno de estos números, diagamos N + m, 2 ≤ m ≤ p, m es divisible por uno de los primos, digamos q, 2 ≤ q ≤ p, y este q divide también a N, así que q divide a N + m. Según el Teorema 8 hay primos arbitrariamente grandes, así que obtenemos

Teorema 9 Existen bloques arbitrariamente largos de compuestos consecutivos.

Examinamos ahora otro fenómeno, la ocurrencia de bloques de primos. Las tablas de primos indican la persistencia indefinida de pares primos, como 3, 5 o 101, 103, cuya diferencia es 2. Hay 1224 tales pares (p, p + 2) antes de 100, 000, y 8169 antes de 1,000,000. Esto sugiere la

conjetura: hay un número infinito de pares primos (p, p + 2).

De hecho, es razonable conjeturar más. Si tomamos los tres números p, p + 2, p + 4, los tres no pueden ser primos, porque uno de ellos es divisible entre 3 (ejercicio), pero no hay una razón obvia para no tener ternas de primos de la forma p, p + 2, p + 6, o p, p + 4, p + 6, y la evidencia de las tablas sugiere que estas ternas también persisten indefinitivamente. Llegamos entonces a otra

conjetura: hay un número infinito de ternas de primos de la forma (p, p + 2, p + 6) y (p, p + 4, p + 6).

Estas conjeturas, y otras similares, acerca de bloques más grandes de primos, no tienen hasta la fecha demostraciones ni contraejemplos.

¿Que otras preguntas naturales se puede hacer acerca de una sucesión de números como los primos? Aquí consideramos algunas.

(i) ¿Existe una fórmula sencilla general que produce la sucesión de todos los primos?

No se conoce una fórmula tal, y es probable que no exista, porque la distribución de los primos es distinta de la que esperaríamos de la existencia de esa fórmula. Aún así, no podemos excluir la posibilidad de que tal fórmula exista.

Una pregunta similar, con comentarios semajantes, es

(ii) ¿existe una fórmula general que produce a partir de un primo, el primo que le sigue (o sea una fórmula tipo p_{n+1} = p_{n}^{2} + 1)?

O una pregunta aún más modesta como

(iii) ¿existe una regla sencilla que produce, dado un primo p, otro primo más grande?

Como hemos visto antes, la demostración del Teorema 8 nos sugiere una regla de este tipo, pero esta regla está muy lejos de ser sencilla o efectiva, si la examinamos de cerca. El único intento razonable en la dirección de estas preguntas fue una conjetura del matemático francés Pierre de Fermat (1601-1665). Los llamados “números de Fermat’’ son los números definidos por la fórmula

F_{n} = 2^{2^{n}} + 1,

así que

F_{0} = 3, F_{1} = 5, F_{2} = 17, F_{3} = 257, F_{4} = 65, 537.

Estos 5 números son primos y Fermat conjeturó que todos son primos. Desafortunadamente, no es cierto. En 1732, el matemático suizo Leonhard Euler (1707-1783) descubrió que 641 es un divisor de F_{5} = 2^{32} + 1, así que no es primo. Hoy en día conocemos muchos otros números de Fermat compuestos y de hecho no se ha encontrado ningún otro número de Fermat primo, más que los 5 mencionados arriba, así que más razonable será conjeturar que el número de primos entre los F_{n} es finito. Pero los números de Fermat tienen mucho interés en la teoría de números; por ejemplo, Gauss demostró que si F_{n} es un primo p, entonces es posible construir con compás y regla un polígono regular con p lados. La construcción para el caso de p = 3 es muy fácil, la de p = 5 un poco menos fácil pero todavía “clásica’’ (conocida por los griegos antiguos), pero la construcción para el caso de p = 17 ya es muy difícil y se necesitaba de alguien como Gauss para encontrarla.

Otra pregunta interesante es

(iv) ¿cuantos primos hay menores que un número dado x?

Esta pregunta es mucho más productiva, pero necesita una interpretación cuidadosa. Denotamos por π(x) el número de primos menores o iguales a x, así que π(1) = 0, π(2) = 1, π(20) = 8. De hecho, si tuviésemos una fórmula exacta para π(x), podríamos usarla para producir una lista de todos los números primos; si denotamos por p_{n} el n-ésimo primo (p_{1} = 2, p_{2} = 3, p_{3} = 5, …), es claro que π(p_{n}) = n, así que la fórmula deseada para p_{n} se obtiene al invertir (o resolver) la última ecuación, expresando p_{n} en términos de n. En consecuencia, pedir una fórmula sencilla para π(x) es prácticamente repetir la pregunta (i). Tenemos entonces que reinterpretar la pregunta de otra manera, y preguntar

“ ¿Cuantos primos aproximadamente hay… ?’’ ¿será cierto que la “mayoría’’ de los números son primos, o solo una pequeña fracción? ¿existe una expresión sencilla, f(x), que sea una “buena aproximación’’ a π(x)?

La pregunta, en esta forma modificada, fue respondida por varios matemáticos, empezando por el matemático ruso Pafnuty Lvovich Chebyshev (1821-1894) alrededor de 1850. Para anunciar la respuesta tenemos que usar la función

logarítmica log x.

Teorema 10 (“El teorema de los números primos’’) Una “buena aproximación’’, para x grande, de la función π(x) es

π(x) ∼ \frac{x}{log x};

y más precisamente, si llamamos f(x) al lado derecho de esta aproximación, entonces tenemos que la razón π(x)/f(x) tiende a 1 cuando x tiende a infinito.

Para tener idea de lo que dice el teorema notamos que la función x/ log x es una función que tiende a infinito más lento que x, pero más rápido que cualquier raíz ^{a} \sqrt{(}x), a > 1, y que es la función más sencilla con esta propiedad.

Es interesante comparar el Teorema 10 con la evidencia de las tablas. Los valores de π(x) para x = 10^{3}, x = 10^{6}, x = 10^{9}, son

168, 78,498, 50,847,478;

mientras los valores de la aproximación x/ log x, al entero más cercano, son

145, 72,382, 48,254,942.

Las razones de de estos números son

1.159 …, 1.084 …, 1.053 …,

e indica una convergencia, bastante lenta, a 1.

Existen muchas más conjeturas y preguntas no contestadas acerca de los primos. Aquí están otras.

• ¿Hay un número infinito de primos de la forma n^{2}+1 (como 5, 17, 37, …)?

• ¿Es cierto que cada número par, mayor que 4, es la suma de dos primos impares (como 6 = 3+3 , 8 = 5+3 , 78 = 59+19, …)? Esto se conoce como la conjetura de Goldbach.

• ¿Es cierto que cada número impar, mayor que 7, se puede expresar como la suma de 3 primos impares (como 23 = 5 + 5 + 13, …)?

1.6 La demostración del Teorema Fundamental de la Aritmética

Si el Teorema no fuera cierto, existirán números que son productos de primos de más de una manera. Llamemos temporalmente a tales números raros, y sea n el mínimo número raro. Tenemos entonces dos factorizaciones distintas de n en primos,

n = p_{1}p_{2}p_{3} … = q_{1}q_{2}q_{3} …,

con p_{1} ≤ p_{2} ≤ …, q_{1} ≤ q_{2} ≤ . . .. De hecho, ninguno de los p’s puede ser igual a ninguno de los q’s, pues si P es un primo que aparece en las dos factorizaciones entonces n/P será un número raro menor que n, contradiciendo el hecho de que n fue escogido como el raro mínimo.

Ahora, como p_{1} es el primo mínimo en la primera factorización, tenemos que p_{1}^{2} ≤ n (ver la observación al final de la sección 1.2), y análogamente q_{1}^{2} ≤ n. Además, p_{1} ≠ q_{1}, así que p_{1}q_{1} < n, por lo que N = n − p_{1}q_{1} satisface 0 < N < n, así que N no es raro.

Como p_{1}|n y q_{1}|n, tenemos también que p_{1}|N y q_{1}|N, así que ambos p_{1} y q_{1} aparecen en la factorización única de N, por lo que p_{1}q_{1}|N. De n = N + p_{1}q_{1} tenemos que p_{1}q_{1}|n, así que q_{1}|(n/p_{1}). Pero n/p_{1} < n, así que su factorización p_{2}p_{3} … es única y q_{1} no aparece como ninguno de los factores, contradiciendo al hecho de que q_{1}|(n/p_{1}). □

2 Congruencias

2.1 Definición de congruencias

Si un entero positivo m divide a la diferencia a − b de dos números, decimos que “a es congruente a b modulo m’’, y lo escribimos

a ≡ b (mod m).

Por ejemplo,

5 ≡ 9 (mod 4), −8 ≡ 1 (mod 9), 1997 ≡ 7 (mod 10).

Esta definición no introduce nada nuevo, porque “a ≡ b (mod m)’’ y “m|(a − b)’’ tienen exactamente el mismo significado; pero cada notación tiene su ventaja.

Notamos que en esta definición a y b no tienen que ser números positivos, y de hecho ni enteros, aunque nosotros no lo vamos a usar más que para números enteros.

Si x ≡ a (mod m) decimos tambien que “a es un residuo de x’’ (mod m). Si 0 ≤ a ≤ m−1, llamamos a a el residuo mínimo (no-negativo) de x, módulo m. Así que dos números a y b son congruentes (mod m) si tienen los mismos residuos (mod m).

El residuo mínimo (mod m) de un entero no-negativo x se puede determinar así: se divide x entre m, y lo que sobra es el residuo mínimo. Por ejemplo, el residuo mínimo de 100 (mod 7) es 2, porque al dividir 100 entre 7 el resultado es 14 (esto no importa) y sobran 2 (esto sí importa). El residuo mínimo de −100 (mod 7) es 7 − 2 = 5. (¿Por qué?)

Una clase de residuos (mod m) es la clase de todos los números congruentes a un número dado (mod m). Por ejemplo, la clase de residuos de 3 (mod 5) consiste de los números

… − 12, −7, −2, 3, 8, 13, 18, …,

y la clase de residuos de 0 (mod m) consiste de todos los múltiplos de m

…, −3m, −2m, −m, 0, m, 2m, 3m, ….

Cada miembro de una clase de residuos (mod m) se llama un representante de la clase. Obviamente hay m clases de residuos (mod m), representados por los residuos mínimos

0, 1, 2, 3, …, m − 1.

Las congruencias son de gran importancia práctica en la vida cotidiana. Por ejemplo, “hoy me levanté a las 6 de la mañana’’ es una afirmación acerca del número de horas que han pasado, módulo 24, desde algún tiempo fijo. La clase de residuos de este número de horas, o sea la hora del día, es normalmente mucho más importante que el número real de horas que han pasado desde, digamos, la creación del universo. Calendarios y horarios de camión o clases, son tablas de congruencias, módulo 7, 365 y 24.

2.2 Propiedades elementales de congruencias

Es fácil demostrar que congruencias módulo un entero positivo fijo m satisfacen las siguientes propiedades:

(i) a ≡ b  ⟹ b ≡ a,
(ii) a ≡ b, b ≡ c ⟹ a ≡ c,
(iii) a ≡ b  ⟹ ka ≡ kb, para cualquier k,
(iv) a ≡ a’, b ≡ b’ ⟹ a + b ≡ a’ + b’ y ab ≡ a’b’.

Demostramos por ejemplo (iii). Si a ≡ b entonces m|(a − b) así que existe un

l tal que a − b = ml. Así que k(a − b) = ka − kb = mlk, así que m|ka − kb, y obtenemos que ka ≡ kb (mod m). Dejamos la demostración de las otras propiedades como un ejercicio.

Las propiedades (i) – (iv) son muy parecidas a las propiedades conocidas de las ecuaciones del álgebra ordinaria, pero de pronto encontramos una diferencia importante. En álgebra, tenemos también un converso a (iii). Es decir,

ka = kb ⟹ a = b, si k ≠ 0.  (6)

Pero con congruencias no es cierto. Por ejemplo

4 · 5 ≡ 4 · 3 y 4 ≢ 0 (mod 8),  (7)

pero

5 ≢ 3 (mod 8).

Para entender lo que sí es cierto en esta dirección, revisamos primero la justificación usual de (6).

En álgebra ordinaria de números, si k ≠ 0, entoces k tiene un inverso, o sea, existe un número, denotado por 1/k, tal que k·(1/k) = 1. Multiplicando los dos lados de la ecuación ka = kb por 1/k (usando una regla tipo (iii)), obtenemos (1/k)·k·a = (1/k)·k·b, y por la propiedad del inverso, k·(1/k) = 1, obtenemos a = b. De este argumento, aplicado a congruencias, obtenemos entonces el siguiente converso a (iii):

Teorema 11 Si k es invertible (mod m), entonces ka ≡ kb (mod m) implica a ≡ b.

Ahora podemos entender mejor el problema con el ejemplo de (7). El problema surgió del hecho que 4 no tiene inverso modulo 8; o sea, no existe un número x que satisface 4x ≡ 1 (mod 8).

La siguiente pregunta, entonces, es fundamental para trabajar con congruencias:

¿Que residuos, modulo m, tienen inverso?

o dicho de otra manera, ¿para cuáles k la congruencia kx ≡ 1 (mod m) tiene una solución x?

La respuesta esta dada por

Teorema 12 Los residuos invertibles (mod m) son los residuos que son primos relativos a m; o sea los residuos que no tienen un divisor común con m mayor que 1.

Por ejemplo, segun el teorema, de los 8 residuos mínimos (mod 8), hay 4 que son invertibles (los impares), y 4 que no son invertibles (los pares). En particular, 4 no es invertible, como ya vimos.

Demostración. Suponemos que k es invertible (mod m) y d es un divisor común de m y k. Entonces k = da y m = db para algunos enteros a y b, donde 1 ≤ b ≤ m. Ahora kb = dab = ma ≡ 0 (mod m), así que si k es invertible, obtenemos, segun el Teorema 11, que b ≡ 0; pero esto es posible, por la condición 1 ≤ b ≤ m, solamente si b = m, así que d = 1.

Para el converso, suponemos que k y m no tienen un divisor común mayor que 1, y consideramos los m − 1 números

k, 2k, 3k, …, (m − 1)k.

Demostramos que alguno de estos números es congruente a 1 (mod m). Para eso, es suficiente ver que estos m − 1 números representan m − 1 clases de congruencias distintas. Si dos de estos números son congruentes, digamos ka ≡ kb (mod m), 1 ≤ a < b ≤ m − 1, tenemos que m divide a la diferencia kb−ka = k(b−a). Ahora como m no tiene factor común con k, m|k(b−a) ⟹ m|(b − a) (usando el Teorema Fundamental). Pero esto es imposible porque 1 ≤ b − a ≤ m − 1. □

Un caso particular, pero importante, del último teorema es

Teorema 13 Si p es un primo, entonces a es invertible (mod p) para todo a ≢ 0.

Por este Teorema, y la discución al principio de esta sección, tenemos que la álgebra módulo un primo p se parece, en sus aspectos formal, a la álgebra ordinaria. En la siguiente sección ilustramos el uso de este “principio’’, en la demostración de un teorema de la más famosos de la teoría de números.

2.3 El “pequeño’’ teorema de Fermat

Teorema 14 Si p es un primo, entonces a^{p} ≡ a (mod p), para todo entero a.

Este teorema fue anunciado por Fermat en 1640 y demostrado por primera vez por Euler en 1736. El “gran’’ teorema de Fermat (o “último’’ teorema) afirma que la ecuación x^{n} + y^{n} = z^{n} no tiene soluciones enteras para n > 2. Su demostración se llevó acabo, despues de grandes esfuerzos de muchos matemáticos, por el matemático inglés Andrew Wiles (1954– ) hace 3 años.

Demostración. Para a ≡ 0 (mod p) el teorema es obvio. Suponemos entonces que a ≢ 0. En este caso, usando que p es primo, sabemos que a es invertible (mod p), así que los residuos mínimos de sus p − 1 múltiplos

a, 2a, 3a, …, (p − 1)a

son todos distintos, y distintos de cero, así que deben constituir a todos los p − 1 residuos mínimos 1, 2, …, p − 1. Así obtenemos

a · 2a · . . . · (p − 1)a ≡ 1 · 2 · . . . · (p − 1) (mod p),

así que

a^{p−1} · 1 · 2 · . . . · (p − 1) ≡ 1 · 2 · . . . · (p − 1) (mod p);

pero 1 · 2 · . . . · (p − 1) ≢ 0 (mod p), así que

a^{p−1} ≡ 1 (mod p).
□

El principio combinatorio usado en la última demostración se llama el “principio de la palomera”: si N palomas se instalan en una palomera con N sitios, y en cada sitio no cabe más que una paloma, entonces todos los sitios tienen que estar ocupados (a veces se afirma esto en una forma equivalente: si N palomas se instalan en una palomera con n sitios, y n < N, entonces hay por lo menos un sitio ocupado por más de una paloma). Este principio, tan “obvio” al parecer, es de gran utilidad en nuestra teoría. En la última demostración las “palomas” eran los números a, 2a, 3a, …, (p − 1)a y la “palomera” el sistema de residuos mínimos distintos de cero (mod p). Otro lugar en donde hemos usado este principio fue en la demostración del Teorema 12.