Archivo de la etiqueta: modulos

Teorema de navidad de Fermat: primos suma de dos cuadrados

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

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:

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

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

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 $a-b$. En este caso decimos que $a\equiv b \pmod n$, 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 $1305\cdot 1302+1314\cdot 1311$ 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í, $1305\equiv 5\pmod {13}$, $1302\equiv 2 \pmod {13}$, $1314\equiv 1 \pmod {13}$ y $1311\equiv 11 \pmod {13}$. Así, trabajando módulo $1$ tenemos que:

\begin{align*}
1305\cdot 1302+1314\cdot 1311 &\equiv 5\cdot 2 + 1\cdot 11 \\
&\equiv 10 + 11 \equiv 21 \\
&\equiv 8 \pmod {13}
\end{align*}
De esta forma, $1305\cdot 1302+1314\cdot 1311$ deja residuo $8$ al dividirse entre $13$.

$\square$

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,\ldots,n-1\}$ tal que $a\equiv r\pmod n$, 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\mid (a-b)(b-c)(c-a).$$

Sugerencia pre-solución. Notemos que $1331=11^3$, 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:

$n$$n^2 \pmod {11}$
$0$$0$
$1$$1$
$2$$4$
$3$$9$
$4$$16\equiv 5$
$5$$25\equiv 3$
$6$$36\equiv 3$
$7$$(-4)^2\equiv 5$
$8$$9$
$9$$4$
$10$$1$

A partir del $6$ estamos aprovechando que ya conocemos los del $1$ al $6$ y que $a \equiv a-11 \pmod {11}$. 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 $11\mid a-b$, $11\mid b-c$ y $11\mid c-a$, de donde se sigue la conclusión que queremos.

$\square$

Últimos dígitos

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

Problema. Determina los últimos dos dígitos de $7^{25}+25^7$.

Sugerencia pre-solución. Trabajamos módulo $100$, así que todas las congruencias son módulo $100$. Hay muchas formas de proceder para encontrar $7^{21}$. Notemos que $7^{2}\equiv 49$. y que $$7^4\equiv 49\times 49 = 2401 \equiv 1.$$ Esto es una gran ventaja, pues entonces $7^{24}\equiv (7^4)^6 \equiv 1^6 \equiv 1$, así que $7^{25}\equiv 7$.

Para $25^7$, nos conviene notar que $25=20+5$, de modo que
\begin{align*}
25^2&=(20+5)^2\\
&=20^2+2\cdot 20 \cdot 5 + 25\\
&\equiv 25,
\end{align*}

pues los primeros dos sumandos son múltiplos de $100$. De esta forma, $25^7\equiv 25$. Así, $7^{25}+25^7\equiv 7+25\equiv 32$, por lo que los dos últimos dígitos de la expresión son $32$.

$\square$

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=777\cdots770$, en donde hay $2002$ dígitos iguales a $7$.

El máximo común divisor de $2002$ y $10^{2003}$ es $2$, de modo que existen enteros $m$ y $n$ tales que $2002m+10^{2003}n=2$.

Multiplicando esta igualdad por el entero $N/2$, obtenemos que $2002\cdot \frac{mN}{2}+10^{2003}\frac{nN}{2}=N$. Aplicando módulo $10^{2003}$ obtenemos que $2002\cdot \frac{mN}{2} \equiv N \pmod {10^{2003}}$.

Como $N<10^{2003}$, esto nos dice que $2002\cdot \frac{mN}{2}$ 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$.

$\square$

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 $n\geq 2$ un entero, $b_i$ enteros para $i\in\{1,2,\ldots,n\}$ y $m_i$ enteros positivos para $i\in\{1,\ldots,n\}$. Supongamos además que cada par $m_i, m_j$ de enteros ($i\neq j$) son primos relativos. Entonces el sistema lineal de congruencias
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}
\end{align*}
tiene una y sólo una solución módulo $m_1m_2\ldots m_n$.

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 $b_i$ son consecutivos.

Solución. Por el teorema chino del residuo, existe un entero positivo $n$ tal que
\begin{align*}
n&\equiv 0 \pmod{2^3}\\
n&\equiv -1\pmod{3^3}\\
n&\equiv -2\pmod{5^3}\\
n&\equiv -3\pmod{7^3}\\
n&\equiv -4\pmod{11^3}
\end{align*}

Para este entero, se tiene que $2^3$ divide a $n$, $3^3$ divide a $n+1$, $5^3$ divide a $n+2$, $7^3$ divide a $n+3$ y $11^3$ divide a $n+4$.

$\square$

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.