Archivo de la etiqueta: fermat

Teorema de navidad de Fermat: primos suma de dos cuadrados

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 p\equiv 1 \pmod 4.

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 p\equiv a \pmod b.

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 a^2+1 \equiv 0 \pmod p 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=x^2+y^2 para enteros no negativos x,y. El hecho de que p \equiv 1 \pmod 4 se desprende de dos propiedades del anillo \mathbb{Z}_4. Notemos primero que cualquier entero impar es congruente con 1 \pmod 4 o con 3\pmod 4. Además, cualquier cuadrado es congruente con 0 \pmod 4 o 1\pmod 4, pues si x es congruente con 0,1,2,3 \pmod 4 entonces x^2 es congruente con 0,1,0,1 \pmod 4, respectivamente. Como p=x^2+y^2, sabemos entonces que

    \[p\equiv x^2+y^2=0,1 \text{ \'o } 2 \pmod 4.\]

Pero p es un primo mayor que 2, entonces p es impar. Así, p\equiv 1 \pmod 4.

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 n\equiv 1 \pmod 4.

Supongamos ahora que p\equiv 1 \pmod 4. Lo primero que haremos es mostrar que a^2+1\equiv 0 \pmod p 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

    \[(p-1)!=1\cdot 2 \cdot \ldots \cdot \frac{p-1}{2} \cdot \frac{p+1}{2}\cdot \ldots \cdot (p-2) \cdot (p-1).\]

A los últimos (p-1)/2 factores los pensamos como sigue: p-1\equiv -1 \pmod p, p-2\equiv -2\pmod p, …, \frac{p+1}{2}\equiv -\frac{p-1}{2} \pmod p. El factorial se convierte entonces en

    \begin{align*}(p-1)!&\equiv 1\cdot \ldots \cdot \left(\frac{p-1}{2}\right) \cdot \left(-\frac{p-1}{2}\right) \cdot \ldots \cdot (-1)\\&\equiv (-1)^{(p-1)/2} \left(1\cdot \ldots \cdot \frac{p-1}{2}\right)^2 \pmod p.\end{align*}

Definiendo a= 1\cdot \ldots \cdot \frac{p-1}{2}, lo anterior se puede escribir como

    \[(p-1)!\equiv (-1)^{(p-1)/2} a^2 \pmod p.\]

Por el teorema de Wilson, (p-1)!\equiv -1 \pmod p. Como p\equiv 1 \pmod 4, tenemos p=4k+1 para algún entero k. Entonces, (p-1)/2=2k, que es par, de modo que (-1)^{(p-1)/2}=1. De esta forma, tenemos que

    \[-1\equiv a^2 \pmod p.\]

Sumando 1 de ambos lados, tenemos que a^2+1\equiv 0 \pmod p. Aplicando el Teorema 2, concluimos que p es suma de dos cuadrados.

\square

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 p_1<\ldots<p_n, en donde p_1=3. Consideremos el número N=4p_2p_3\ldots p_n +3 (ojo: no estamos incluyendo al 3 en la multiplicación). Este número no puede ser primo pues es mayor que p_n y N\equiv 3\pmod 4. 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\pmod 4, entonces N sería 1\pmod 4, pero esto no es cierto. De este modo, algún divisor primo p de N debe satisfacer p\equiv 3 \pmod 4. Notemos que p no puede ser 3, pues si 3\mid N, tendríamos 3\mid 4p_1 \ldots p_n, pero esto es imposible pues el número de la derecha no tiene ningún factor 3. Con esto concluimos que p=p_i para algún entero i=2,\ldots,n. Sin embargo, si p_i\mid N, entonces p_i\mid N-(p_2\ldots p_n)=3. Esto también es imposible pues p_i\neq 3. Así, es inevitable llegar a una contradicción, por lo que hay una infinidad de primos de la forma 4k+3.

\square

La demostración anterior no funciona directamente para los primos de la forma 4k+1, pues si hubiera una cantidad finita n de ellos p_1<\ldots < p_n y consideramos al número 4p_1\ldots p_n+1, este número es congruente con 1\pmod 4, pero nada garantiza que sus factores primos deban ser de la forma 1\pmod 4 pues, por ejemplo, 3\equiv 3\pmod 4, 7\equiv 3\pmod 4, pero 3\cdot 7 \equiv 21 \equiv 1\pmod 4. 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 p_1<\ldots<p_n. Consideremos al número N=4(p_1p_2\ldots p_n)^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 p_i.

Sea p un divisor primo de N. Como N es impar, p\neq 2. Como p divide a N, tenemos que (2p_1\ldots p_n)^2+1\equiv 0 \pmod p, de modo que x^2+1\equiv 0 \pmod p tiene solución y por el Teorema 2, p se puede escribir como suma de dos cuadrados. Por el teorema de Navidad de Fermat, p\equiv 1\pmod 4. De esta forma, p=p_i para alguna i. Pero entonces, p divide a N y a 4(p_1\ldots p_n)^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.

\square

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:

Álgebra Superior II: Ejercicios de los teoremas de Fermat y de Wilson

Primero, un ejercicio más de congruencias:

Un ejercicio de congruencias

Un ejercicio utilizando el teorema de Fermat:

Ejercicio utilizando el teorema de Fermat

Ejercicio sencillo utilizando el Teorema de Wilson:

17!=1 (mod 19)

Otro ejercicio utilizando el Teorema de Wilson:

Si p primo, (p-1)! = -1 (mod p)

Álgebra Superior II: Teoremas de Fermat y de Wilson

Introducción

En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo n y vimos algunos problemas. La gran ventaja de trabajar en \mathbb{Z}_n, o bien, de trabajar módulo n, es que para n pequeña hay una cantidad pequeña de elementos y entonces las operaciones se vuelven muy sencillas.

Problema. Determina cuál es el residuo obtenido de dividir 705\cdot 702+714\cdot 711 al dividirse entre 7.

Solución. Tenemos que 705, 702, 714 y 711 los podemos poner como un múltiplo de 7 más un residuo como sigue: 700+5, 700+2 y 714=714+0, 711=707+4. Así, 705\equiv 5\pmod 7, 702\equiv 2 \pmod 7, 714\equiv 0 \pmod 7 y 711\equiv 4 \pmod 7. Así, trabajando módulo 7 tenemos que:

    \begin{align*}705\cdot 702+714\cdot 711 \equiv 5\cdot 2 + 0\cdot 4 \equiv 10 + 0 \equiv 10 \equiv 3 \pmod 7\end{align*}


De esta forma, 705\cdot 702+714\cdot 711 deja residuo 3 al dividirse entre 7.

\square

Trabajando de esta forma, podemos encontrar el residuo al dividirse por n de expresiones que involucran sumas y productos. El objetivo de esta entrada es entender qué sucede cuando queremos encontrar el residuo de expresiones que tienen potencias y factoriales.

Pequeño teorema de Fermat

Intentemos entender qué sucede con las potencias de un número a en cierto módulo n.

Ejemplo. Imagina que tomamos al número 3 y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre 7. Tenemos, trabajando módulo 7:

    \begin{align*}3^0\equiv 1\\3^1\equiv 3\\3^2\equiv 9 \equiv 2\\3^3=27\equiv 21+6\equiv 6\end{align*}

Nota que podríamos seguir, poniendo 3^4=81. Pero podemos ahorrarnos trabajo pues 3^4\equiv 3\cdot 3^3 \equiv 3 \cdot 6 \equiv 18\equiv 4, en donde usamos que ya sabíamos que 3^3\equiv 6. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener

    \begin{align*}3^5\equiv 3\cdot 4\equiv 12\equiv 5\\3^6\equiv 3\cdot 5 = 15\equiv 1\\3^7\equiv 3\cdot 1 = 3\\3^8\equiv 3\cdot 3 = 9 \equiv 2\end{align*}

Podríamos seguir y seguir, pero ya no tiene mucho caso. A partir de aquí es fácil convencerse de que los residuos se ciclan: 1,3,2,6,4,5,1,3,2,6,4,5,1\ldots. Notemos que si la potencia es múltiplo de 6, entonces el residuo será 1, es decir, 3^{6k}\equiv 1 \pmod 7. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos, 3^{605} entre 7, basta ver que módulo 7 tenemos

    \[3^{605}=3^{600}\cdot 3^5 \equiv 1\cdot 5 \equiv 5,\]

en donde estamos usando lo que mencionamos para k=100 y que ya hicimos 3^5 módulo 7.

A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo a^m\equiv 1\pmod n, pues en ese momento las potencias «se empiezan a ciclar». El pequeño teorema de Fermat es un resultado que podemos aplicar cuando trabajamos módulo un número primo p. Dice que la potencia p-1 funciona para esto.

Teorema. Si p es un número primo y p no divide a a, entonces p divide a a^{p-1}-1 o, dicho en otras palabras a^{p-1}\equiv 1 \pmod p.

Demostración. Afirmamos que los números a, 2a, 3a, \ldots, (p-1)a dejan todos ellos residuos distintos al dividirse entre p y, además, que ninguno de esos residuos es 0. Probemos esto. Tomemos 0<i<j<p-1. En una entrada anterior vimos que [a]_p tiene inverso en Z_p. Sea [b]_p su inverso. Si [ia]_p=[ja]_p, entonces multiplicando por [b]_p de ambos lados tendríamos

    \[[i]_p=[i(ab)]_p=[j(ab)]_p=[j]_p.\]

Pero como i y j están entre 1 y p-1, esto implica que i=j. Ninguno es cero pues si [ia]_p=[0]_p, entonces al multiplicar por b tendríamos la contradicción [i]_p=[i(ab)]_p=[0b]_p=[0]_p. Esto muestra la afirmación.

Así, usando la afirmación en el segundo paso de la siguiente cadena módulo p, tenemos:

    \begin{align*}(p-1)! a^{p-1} &= (a)(2a)(3a)\cdots((p-1)a)\\&\equiv 1\cdot 2 \cdot \ldots \cdot (p-1)\\&= (p-1)!.\end{align*}

El número (p-1)! no es divisible entre p, pues es producto de puros números menores que p, de modo que \text{MCD}(p, (p-1)!)=1, así que tiene inverso módulo p, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos:

    \[a^{p-1}\equiv 1 \pmod p.\]

\square

Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.

Problema. Demuestra que 13 divide a 25^{181}-181^{25}

Solución. Notemos primero que 13 es primo y que no divide ni a 25 ni a 181. Por el pequeño teorema de Fermat, tenemos módulo 13 que 25^{12}\equiv 1 y que 181^{12}\equiv 1. Así, módulo 13 tenemos que

    \[25^{181}\equiv 25^{15\cdot 12}\cdot 25 \equiv 25 \equiv 12,\]

y que

    \[181^{25}\equiv 181^{2\cdot 12}\cdot 181\equiv 181 \equiv 12.\]

De esta forma, 25^{181}-181^{25}\equiv 12-12\equiv 0\pmod {13}, es decir, 13 divide a 25^{181}-181^{25}

\square

Teorema de Wilson

En la demostración del teorema de Fermat aparece la expresión (p-1)!. ¿Qué residuo dejará al dividirse entre p? Hagamos una prueba.

Problema. Encuentra el residuo que se obtiene al dividir 10! entre 11.

Solución. Para no trabajar con números tan grandes, notemos que en

    \[10!=1\cdot 2\cdot 3\cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10\]

podemos cambiar a 6,7,8,9,10 por -5, -4, -3, -2, -1 al trabajar módulo 11, así que basta encontrar -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 módulo 11. Notemos que 3\cdot 4\equiv 12 \equiv 1 \pmod {11} y que 2\cdot 5 =10 \equiv -1 \pmod {11}. Así,

    \[10!\equiv -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 \equiv -(1\cdot 1 \cdot -1)^2 \equiv -1 \equiv 10 \pmod {11},\]

es decir, el residuo que deja 10! al dividirse entre 11 es 10.

\square

El teorema de Wilson ayuda a cuando queremos encontrar el residuo de un factorial al dividirse entre un número primo. Una de las ideas del ejercicio anterior fue buena: nos conviene agrupar a números del factorial en productos sencillos. Lo más conveniente es que agrupemos a cada número con su inverso multiplicativo, pues así obtendremos un 1. Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.

Proposición. Sea p un número primo. Los únicos elementos en \mathbb{Z}_p que son inversos de sí mismos son [1]_p y [p-1]_p.

Demostración. Claramente [1]_p y [p-1]_p=[-1]_p son inversos multiplicativos de sí mismos, pues 1\cdot 1=1=(-1)\cdot(-1). Ahora, si tenemos a tal que a es inverso multiplicativo de sí mismo, tenemos que [a^2]_p\equiv [1]_p, que por definición quiere decir que p divide a a^2-1=(a+1)(a-1). Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces p divide a a+1 o a a-1, y obtenemos, respectivamente, que [a]_p=[-1]_p=[p-1]_p o que [a]_p=[1]_p, como queríamos.

\square

Estamos listos para enunciar y demostrar el teorema de Wilson.

Teorema. Si p es un número primo, entonces p divide a (p-1)!+1 o, dicho en otras palabras, (p-1)!\equiv -1 \pmod p.

Demostración. Si p=2, el resultado es inmediato. Supongamos que p\geq 3. En (p-1)! aparecen todos los números de 1 a p-1. Todos ellos son primos relativos con p, así que tienen inverso módulo p. Ese inverso también aparece en (p-1)!. Así, podemos agrupar esos números en (p-3)/2 parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el 1 y el -1. De esta forma,

    \[(p-1)!\equiv (1)(-1)(1\cdot 1\cdot \ldots\cdot 1) \equiv -1 \pmod p,\]

en donde en la expresión intermedia tenemos un 1, un -1 y (p-3)/2 unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.

\square

Veamos una posible aplicación.

Problema. Determina el residuo que se obtiene al dividir 15!+16!+17! entre 17.

Solución. Notemos que 17 divide a 17!, así que 17!\equiv 0 \pmod {17}. Por el teorema de Wilson, 16!\equiv -1 \pmod {17}. Podemos multiplicar esa igualdad por -1 para obtener módulo 17 que

    \[15! = 15! (-1)(-1) \equiv 15! \cdot 16 \cdot (-1) \equiv 16! (-1)\equiv (-1)(-1)\equiv 1.\]

Así, 15!+16!+17!\equiv 1 + (-1) + 0 \equiv 0 \pmod {17}.

\square

Una solución alternativa es darse cuenta de que

    \[15!+16!+17!=15!(1+16)+17\cdot 16!=17\cdot (15!+16!)\]

y por lo tanto es múltiplo de 17. Aunque tengamos herramientas fuertes, ¡siempre hay que recordar los básicos!