Archivo de la etiqueta: modulos

Teorema de navidad de Fermat: primos suma de dos cuadrados

Por Leonardo Ignacio Martínez Sandoval

Comentario de Leo: Esta es una escrita en conjunto con por Alexandher Vergara, estudiante en ESFM. En ella hablamos del teorema de navidad de Fermat, una idea de la prueba y de las consecuencias. Si quieres contribuir con algún tema de matemáticas, puedes contactarme por correo electrónico, o dejando un comentario aquí en el blog.

Introducción

En entradas anteriores hemos visto temas de teoría de números, como divisibilidad y teoría de congruencias. También hablamos acerca de números primos y del teorema fundamental de la aritmética. A continuación probaremos una parte del famoso «teorema de navidad de Fermat», el cual dice cuáles primos impares son la suma de dos cuadrados.

Teorema (teorema de Navidad de Fermat). Un número primo p>2 es la suma del cuadrado de dos enteros si y sólo si p1(mod4).

Enunciado del teorema de Navidad de Fermat

El teorema recibe este nombre pues Fermat escribió una carta con muchos detalles acerca del resultado para Mersenne, cuya fecha fue el 25 de diciembre de 1640.

Este resultado nos lleva un paso más adelante en teoría de números. Por un lado, tiene «el mismo sabor» que el teorema de los cuatro cuadrados de Lagrange.

Teorema (teorema de los cuatro cuadrados de Lagrange). Todo entero no negativo puede ser escrito como suma de los cuadrados de cuatro números enteros.

Por otro lado, el teorema de Navidad de Fermat también nos ayuda a demostrar un caso particular del teorema de Dirichlet para primos sobre progresiones aritméticas.

Teorema 1. Hay infinitos números primos de la forma 4k+1 e infinitos números de la forma 4k+3.

El teorema de Dirichlet es una generalización de este resultado.

Teorema (teorema de Dirichlet). Si a y b son primos relativos, entonces existe una infinidad de primos p tales que pa(modb).

Las demostraciones de los teoremas de Lagrange y de Dirichlet requieren de varios argumentos para los cuales aún no hemos desarrollado teoría suficiente. La idea de esta entrada de blog es demostrar el teorema de Navidad de Fermat y usarlo para demostrar el Teorema 1.

El teorema de Navidad de Fermat

En la demostración del teorema de navidad de Fermat usaremos el siguiente resultado.

Teorema 2. Si p es un número primo y la ecuación a2+10(modp) tiene solución para algún a, entonces p se puede representar como una suma de dos cuadrados.

Por el momento, no nos enfocaremos en demostrar este resultado auxiliar. Existen muchas pruebas en la literatura, por ejemplo, una por J.H. Grace usando latices de enteros (The four square theorem).

Demostración del teorema de Navidad de Fermat. Supongamos primero que p=x2+y2 para enteros no negativos x,y. El hecho de que p1(mod4) se desprende de dos propiedades del anillo Z4. Notemos primero que cualquier entero impar es congruente con 1(mod4) o con 3(mod4). Además, cualquier cuadrado es congruente con 0(mod4) o 1(mod4), pues si x es congruente con 0,1,2,3(mod4) entonces x2 es congruente con 0,1,0,1(mod4), respectivamente. Como p=x2+y2, sabemos entonces que px2+y2=0,1 \’o 2(mod4). Pero p es un primo mayor que 2, entonces p es impar. Así, p1(mod4).

Observación. En esta parte de la prueba en realidad es un poco más general, pues muestra que si n es un entero impar que se puede representar como suma de dos cuadrados, entonces n1(mod4).

Supongamos ahora que p1(mod4). Lo primero que haremos es mostrar que a2+10(modp) tiene solución para alguna a, y después usaremos el Teorema 2 para obtener que p es suma de dos cuadrados.

Primero, examinaremos los factores en (p1)!=12p12p+12(p2)(p1). A los últimos (p1)/2 factores los pensamos como sigue: p11(modp), p22(modp), …, p+12p12(modp). El factorial se convierte entonces en
(p1)!1(p12)(p12)(1)(1)(p1)/2(1p12)2(modp).

Definiendo a=1p12, lo anterior se puede escribir como (p1)!(1)(p1)/2a2(modp).

Por el teorema de Wilson, (p1)!1(modp). Como p1(mod4), tenemos p=4k+1 para algún entero k. Entonces, (p1)/2=2k, que es par, de modo que (1)(p1)/2=1. De esta forma, tenemos que 1a2(modp). Sumando 1 de ambos lados, tenemos que a2+10(modp). Aplicando el Teorema 2, concluimos que p es suma de dos cuadrados.

◻

Infinidad de primos de las formas 4k+1 y 4k+3

Todos los primos mayores que 2 son impares, así que son o bien de la forma 4k+1, o bien de la forma 4k+3. Sabemos además que hay una infinidad de números primos. ¿Será cierto que hay una infinidad de ellos de la forma 4k+1 y una infinidad de ellos de la forma 4k+3?

Por el principio de las casillas, tiene que suceder por lo menos alguna de estas dos opciones. Si hubiera una cantidad finita de la forma 4k+1 y de la forma 4k+3, entonces por el párrafo anterior habría sólo una cantidad finita de primos, lo cual es una contradicción.

Lo que dice el Teorema 1 es más fuerte. Lo volvemos a poner aquí por conveniencia para el lector.

Teorema 1. Hay infinitos números primos de la forma 4k+1 e infinitos números de la forma 4k+3.

Es decir, el Teorema 1 afirma que para cada uno de los tipos hay una infinidad de primos. Veamos que en efecto esto sucede.

La primera parte del Teorema 1 no necesita que usemos el teorema de Navidad de Fermat.

Proposición 1. Hay una infinidad de primos de la forma 4k+3.

Demostración. Supongamos que existiera únicamente una cantidad finita n de primos de la forma 4k+3 y supongamos que ellos son p1<<pn, en donde p1=3. Consideremos el número N=4p2p3pn+3 (ojo: no estamos incluyendo al 3 en la multiplicación). Este número no puede ser primo pues es mayor que pn y N3(mod4). De esta forma, debe tener al menos un divisor primo.

Tenemos que N es impar, así que 2 no divide a N. Si todos los divisores primos de N fueran 1(mod4), entonces N sería 1(mod4), pero esto no es cierto. De este modo, algún divisor primo p de N debe satisfacer p3(mod4). Notemos que p no puede ser 3, pues si 3N, tendríamos 34p1pn, pero esto es imposible pues el número de la derecha no tiene ningún factor 3. Con esto concluimos que p=pi para algún entero i=2,,n. Sin embargo, si piN, entonces piN(p2pn)=3. Esto también es imposible pues pi3. Así, es inevitable llegar a una contradicción, por lo que hay una infinidad de primos de la forma 4k+3.

◻

La demostración anterior no funciona directamente para los primos de la forma 4k+1, pues si hubiera una cantidad finita n de ellos p1<<pn y consideramos al número 4p1pn+1, este número es congruente con 1(mod4), pero nada garantiza que sus factores primos deban ser de la forma 1(mod4) pues, por ejemplo, 33(mod4), 73(mod4), pero 37211(mod4). Tenemos que hacer algo distinto.

Proposición 2. Hay una infinidad de primos de la forma 4k+1.

Demostración. Supongamos que existe una cantidad finita n de primos de la forma 4k+1 y que son p1<<pn. Consideremos al número N=4(p1p2pn)2+1. Este número es de la forma 4k+1. Por esta razón, es imposible que N sea primo, pues es mayor que todo pi.

Sea p un divisor primo de N. Como N es impar, p2. Como p divide a N, tenemos que (2p1pn)2+10(modp), de modo que x2+10(modp) tiene solución y por el Teorema 2, p se puede escribir como suma de dos cuadrados. Por el teorema de Navidad de Fermat, p1(mod4). De esta forma, p=pi para alguna i. Pero entonces, p divide a N y a 4(p1pn)2, de modo que divide a su resta, que es 1. Esto es imposible. Esta contradicción muestra que hay una cantidad infinita de primos de la forma 4k+1.

◻

El Teorema 1 se sigue de las proposiciones 1 y 2.

¿Dónde seguir?

Aquí en el blog hay otras entradas en donde hablamos acerca de teoría de números. Puedes revisar las siguientes:

Seminario de Resolución de Problemas: Aritmética modular

Por Leonardo Ignacio Martínez Sandoval

Introducción

En la entrada anterior hablamos de divisibilidad, máximo común divisor y combinaciones lineales enteras. Cuando hablamos de trabajar en artimética modular nos referimos a que tomamos un entero n y realizamos todas las operaciones «sólo en el mundo de n», es decir, aplicando las operaciones únicamente en los residuos que deja un número al ser dividido entre n.

Cuando estamos trabajando módulo n, dos enteros a y b «son los mismos» si n divide a ab. En este caso decimos que ab(modn), que se lee «a es congruente con b módulo n».

En esta entrada de blog discutimos la relación «ser congruente con» y cómo se puede enunciar en términos de anillos. Ahí damos las demostraciones de varias de las propiedades que no probaremos aquí. Es recomendable por lo menos echarle un ojo.

Aritmética modular

Para recordar los principios básicos de la aritmética modular, comencemos con el siguiente problema.

Problema. Determina cuál es el residuo obtenido de dividir 13051302+13141311 al dividirse entre 11.

Sugerencia pre-solución. Intenta resolver este problema trabajando módulo 11.

Solución. Tenemos que 1305, 1302, 1314 y 1311 los podemos poner como un múltiplo de 13 más un residuo como sigue: 1300+5, 1300+2 y 1313+1, 1300+11. Así, 13055(mod13), 13022(mod13), 13141(mod13) y 131111(mod13). Así, trabajando módulo 1 tenemos que:

13051302+1314131152+11110+11218(mod13)
De esta forma, 13051302+13141311 deja residuo 8 al dividirse entre 13.

◻

Utilizando el algoritmo de la división, que vimos en la entrada anterior, se puede probar el siguiente resultado.

Proposición. Para cada entero a y entero positivo n, existe un único número r en {0,1,,n1} tal que ar(modn), que es justo el residuo obtenido al dividir a entre n.

Dicho en otras palabras, sólo hay n posibles residuos al dividir entre n. Esto nos permite que las operaciones módulo n siempre las hagamos con números chiquitos, y que afirmaciones sencillas de divisibilidad entre n dependen sólo de n casos. Esto lo podemos aprovechar para resolver problemas como el siguiente.

Problema. Se tienen 13 números enteros. Muestra que hay tres de ellos a,b,c que satisfacen que 1331(ab)(bc)(ca).

Sugerencia pre-solución. Notemos que 1331=113, así que trabajamos módulo 11. Encuentra todas las posibilidades que pueden tener los números cuadrados.

Solución. Un entero n sólo puede ser congruente con alguno de los números 0,1,2,3,4,5,6,7,8,9,10 módulo 11. Los cuadrados tienen entonces las siguientes posibilidades:

nn2(mod11)
00
11
24
39
4165
5253
6363
7(4)25
89
94
101

A partir del 6 estamos aprovechando que ya conocemos los del 1 al 6 y que aa11(mod11). Notemos que sólo hay 6 residuos posibles para los cuadrados módulo 11, que son 0, 1, 4, 9, 5 y 3.

Ahora sí, resolvamos el problema. Como tenemos 13 números enteros y sólo hay 6 posibles residuos para los cuadrados módulo 11, entonces por principio de las casillas hay tres de estos enteros cuyo cuadrado deja el mismo residuo al dividirse entre 11, digamos a,b,c. Como dejan los tres el mismo residuo, tenemos 11ab, 11bc y 11ca, de donde se sigue la conclusión que queremos.

◻

Últimos dígitos

Los últimos m dígitos de un entero n corresponden con el residuo de dividir n entre 10m. Por esta razón, en este tipo de problemas es conveniente usar módulos.

Problema. Determina los últimos dos dígitos de 725+257.

Sugerencia pre-solución. Trabajamos módulo 100, así que todas las congruencias son módulo 100. Hay muchas formas de proceder para encontrar 721. Notemos que 7249. y que 7449×49=24011. Esto es una gran ventaja, pues entonces 724(74)6161, así que 7257.

Para 257, nos conviene notar que 25=20+5, de modo que
252=(20+5)2=202+2205+2525,

pues los primeros dos sumandos son múltiplos de 100. De esta forma, 25725. Así, 725+2577+2532, por lo que los dos últimos dígitos de la expresión son 32.

◻

Veamos otro ejemplo en el que además combinamos un poco de la teoría mencionada en la entrada anterior.

Problema. Demuestra que existe un entero que es múltiplo de 2002 y que tiene por lo menos 2002 dígitos iguales a 7.

Sugerencia pre-solución. Intenta hacer que los 2002 dígitos 7 que se necesitan aparezcan hacia el final. Esto te permitirá usar congruencias. Además, necesitarás el resultado de la entrada anterior que dice que el máximo común divisor de dos números se puede expresar como combinación lineal entera de ellos.

Solución. Tomemos el número N=777770, en donde hay 2002 dígitos iguales a 7.

El máximo común divisor de 2002 y 102003 es 2, de modo que existen enteros m y n tales que 2002m+102003n=2.

Multiplicando esta igualdad por el entero N/2, obtenemos que 2002mN2+102003nN2=N. Aplicando módulo 102003 obtenemos que 2002mN2N(mod102003).

Como N<102003, esto nos dice que 2002mN2 es un múltiplo de 2002 cuyos últimos 2003 dígitos son los de N, es decir, que tiene por lo menos 2002 dígitos iguales a 7.

◻

Teorema chino del residuo

En algunos problemas necesitamos construir un entero que satisfaga un conjunto de congruencias. El teorema chino del residuo nos da una condición bajo la cual podemos garantizar la existencia de dicho número.

Teorema. Sea n2 un entero, bi enteros para i{1,2,,n} y mi enteros positivos para i{1,,n}. Supongamos además que cada par mi,mj de enteros (ij) son primos relativos. Entonces el sistema lineal de congruencias
xb1(modm1)xb2(modm2)xbn(modmn)
tiene una y sólo una solución módulo m1m2mn.

El teorema tiene muchas aplicaciones tanto en resolución de problemas, como en matemáticas en general. Veamos un ejemplo.

Problema. ¿Será posible encontrar 5 enteros consecutivos tales que cada uno de ellos sea divisible entre un cubo distinto de 1?

Sugerencia pre-solución. Intenta construir el ejemplo usando el teorema chino del residuo con 5 módulos y en donde los bi son consecutivos.

Solución. Por el teorema chino del residuo, existe un entero positivo n tal que
n0(mod23)n1(mod33)n2(mod53)n3(mod73)n4(mod113)

Para este entero, se tiene que 23 divide a n, 33 divide a n+1, 53 divide a n+2, 73 divide a n+3 y 113 divide a n+4.

◻

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.2 del libro Problem Solving through Problems de Loren Larson.

Hay otros dos teoremas que sirven cuando estamos trabajando módulo n, de los cuales hemos escrito aquí en el blog. Para empezar, aquí hay una entrada con videos de ejercicios de trabajar módulo n.

El teorema de Fermat y el de Wilson ayudan a entender potencias y factoriales, respectivamente. En la entrada sobre el teorema chino del residuo damos una demostración al teorema.