Archivo de la etiqueta: congruencias\

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 $p \equiv 1 (\mod 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 $4 k + 1$ e infinitos números de la forma $4 k + 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 (\mod 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 (\mod 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 (\mod 4)$ se desprende de dos propiedades del anillo $Z_{4}$ . Notemos primero que cualquier entero impar es congruente con $1 (\mod 4)$ o con $3 (\mod 4)$ . Además, cualquier cuadrado es congruente con $0 (\mod 4)$ o $1 (\mod 4)$ , pues si $x$ es congruente con $0, 1, 2, 3 (\mod 4)$ entonces $x^{2}$ es congruente con $0, 1, 0, 1 (\mod 4)$ , respectivamente. Como $p = x^{2} + y^{2}$ , sabemos entonces que $p \equiv x^{2} + y^{2} = 0, 1 \’o 2 (\mod 4) .$ Pero $p$ es un primo mayor que $2$ , entonces $p$ es impar. Así, $p \equiv 1 (\mod 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 (\mod 4)$ .

Supongamos ahora que $p \equiv 1 (\mod 4)$ . Lo primero que haremos es mostrar que $a^{2} + 1 \equiv 0 (\mod 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 \dots \cdot \frac{p - 1}{2} \cdot \frac{p + 1}{2} \cdot \dots \cdot (p - 2) \cdot (p - 1) .$ A los últimos $(p - 1) / 2$ factores los pensamos como sigue: $p - 1 \equiv - 1 (\mod p)$ , $p - 2 \equiv - 2 (\mod p)$ , …, $\frac{p + 1}{2} \equiv - \frac{p - 1}{2} (\mod p)$ . El factorial se convierte entonces en
$\begin{aligned} (p - 1)! & \equiv 1 \cdot \dots \cdot (\frac{p - 1}{2}) \cdot (- \frac{p - 1}{2}) \cdot \dots \cdot (- 1) \\ \equiv (- 1)^{(p - 1) / 2} {(1 \cdot \dots \cdot \frac{p - 1}{2})}^{2} (\mod p) . \end{aligned}$

Definiendo $a = 1 \cdot \dots \cdot \frac{p - 1}{2}$ , lo anterior se puede escribir como $(p - 1)! \equiv (- 1)^{(p - 1) / 2} a^{2} (\mod p) .$

Por el teorema de Wilson, $(p - 1)! \equiv - 1 (\mod p)$ . Como $p \equiv 1 (\mod 4)$ , tenemos $p = 4 k + 1$ para algún entero $k$ . Entonces, $(p - 1) / 2 = 2 k$ , que es par, de modo que $(- 1)^{(p - 1) / 2} = 1$ . De esta forma, tenemos que $- 1 \equiv a^{2} (\mod p) .$ Sumando $1$ de ambos lados, tenemos que $a^{2} + 1 \equiv 0 (\mod p)$ . Aplicando el Teorema 2, concluimos que $p$ es suma de dos cuadrados.

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

Todos los primos mayores que $2$ son impares, así que son o bien de la forma $4 k + 1$ , o bien de la forma $4 k + 3$ . Sabemos además que hay una infinidad de números primos. ¿Será cierto que hay una infinidad de ellos de la forma $4 k + 1$ y una infinidad de ellos de la forma $4 k + 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 $4 k + 1$ y de la forma $4 k + 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 $4 k + 1$ e infinitos números de la forma $4 k + 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 $4 k + 3$ .

Demostración. Supongamos que existiera únicamente una cantidad finita $n$ de primos de la forma $4 k + 3$ y supongamos que ellos son $p_{1} < \dots < p_{n}$ , en donde $p_{1} = 3$ . Consideremos el número $N = 4 p_{2} p_{3} \dots 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 (\mod 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 (\mod 4)$ , entonces $N$ sería $1 (\mod 4)$ , pero esto no es cierto. De este modo, algún divisor primo $p$ de $N$ debe satisfacer $p \equiv 3 (\mod 4)$ . Notemos que $p$ no puede ser $3$ , pues si $3 ∣ N$ , tendríamos $3 ∣ 4 p_{1} \dots 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, \dots, n$ . Sin embargo, si $p_{i} ∣ N$ , entonces $p_{i} ∣ N - (p_{2} \dots 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 $4 k + 3$ .

La demostración anterior no funciona directamente para los primos de la forma $4 k + 1$ , pues si hubiera una cantidad finita $n$ de ellos $p_{1} < \dots < p_{n}$ y consideramos al número $4 p_{1} \dots p_{n} + 1$ , este número es congruente con $1 (\mod 4)$ , pero nada garantiza que sus factores primos deban ser de la forma $1 (\mod 4)$ pues, por ejemplo, $3 \equiv 3 (\mod 4)$ , $7 \equiv 3 (\mod 4)$ , pero $3 \cdot 7 \equiv 21 \equiv 1 (\mod 4)$ . Tenemos que hacer algo distinto.

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

Demostración. Supongamos que existe una cantidad finita $n$ de primos de la forma $4 k + 1$ y que son $p_{1} < \dots < p_{n}$ . Consideremos al número $N = 4 (p_{1} p_{2} \dots p_{n})^{2} + 1$ . Este número es de la forma $4 k + 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 $(2 p_{1} \dots p_{n})^{2} + 1 \equiv 0 (\mod p)$ , de modo que $x^{2} + 1 \equiv 0 (\mod 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 (\mod 4)$ . De esta forma, $p = p_{i}$ para alguna $i$ . Pero entonces, $p$ divide a $N$ y a $4 (p_{1} \dots 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 $4 k + 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:

Álgebra Superior II: Teorema chino del residuo

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. También, aprendimos a resolver una ecuación lineal módulo $n$ . El resultado principal fue el siguiente:

Teorema 1. Sean $a, b$ enteros y $n$ un entero positivo. La ecuación $a x \equiv b (\mod n)$ tiene solución si y sólo si $M := MCD (a, n)$ divide a $b$ . Cuando sí hay solución, ésta se puede expresar de manera única en módulo $n^{'} := n / M$ .

Ya que sabemos resolver una ecuación lineal, el siguiente paso es aprender a resolver sistemas que involucren dos o más ecuaciones lineales. En esta entrada veremos primero cómo resolver un sistema de dos ecuaciones lineales.

Luego, veremos cómo resolver un sistema con más ecuaciones y demostraremos un resultado clásico: el teorema chino del residuo. Pero para eso necesitaremos el resultado para dos ecuaciones lineales. Vamos poco a poco.

Sistemas de dos ecuaciones lineales

Supongamos que queremos entender por completo el sistema de ecuaciones
$\begin{aligned} a x & \equiv b (\mod m) \\ c x & \equiv d (\mod n), \end{aligned}$

es decir, determinar cuándo existe una $x$ que satisfaga ambas ecuaciones y, si existe, determinar cómo se ven todas las soluciones. Por lo primero que nos tenemos que preocupar es por que cada una de las ecuaciones tenga solución: si alguna no tiene, entonces no hay solución para el sistema.

Así, lo primero que tiene que pasar es que $MCD (a, m)$ divida a $b$ y que $MCD (c, n)$ divida a $d$ . Cuando sí tienen solución, entonces podemos intercambiar a las ecuaciones por sus ecuaciones reducidas y obtener el sistema de ecuaciones lineales equivalente
$\begin{aligned} a^{'} x & \equiv b^{'} (\mod m^{'}) \\ c^{'} x & \equiv d^{'} (\mod n^{'}) . \end{aligned}$

La primera ecuación tiene una única solución módulo $m^{'}$ y la segunda una única solución módulo $n^{'}$ , así que este sistema es equivalente al sistema
$\begin{aligned} x & \equiv e (\mod m^{'}) \\ x & \equiv f (\mod n^{'}), \end{aligned}$

en donde $e$ y $f$ son las soluciones a cada una de las ecuaciones lineales reducidas por separado. Ahora sí podemos combinar ambas ecuaciones. Lo único que nos falta es entender cuándo los sistemas de esta forma tienen solución.

Ejemplo 1. El sistema lineal de ecuaciones
$\begin{aligned} x & \equiv 2 (\mod 6) \\ x & \equiv 4 (\mod 15) \end{aligned}$
no tiene solución.

Solución. La primera ecuación implica que $6 ∣ x - 2$ . Como $3 ∣ 6$ , por transitividad tenemos $3 ∣ x - 2$ , así que la primera ecuación implica que $x$ deja residuo $2$ al dividirse entre $3$ .

La segunda ecuación implica que $15 ∣ x - 4$ . Como $3 ∣ 15$ , por transitividad $3 ∣ x - 4$ , o bien $x \equiv 4 \equiv 1 (\mod 3)$ . Es decir, la segunda ecuación implica que $x$ deja residuo $1$ al dividirse entre $3$ . De esta forma, es imposible satisfacer simultáneamente ambas ecuaciones.

$△$

En el ejemplo anterior, $3$ es el máximo común divisor de $6$ y $15$ y por eso convino estudiar la divisibilidad entre $3$ . La siguiente proposición justo dice cuándo el sistema tiene solución en términos de cierta divisibilidad por el máximo común divisor de los módulos.

Proposición 4. Sean $a$ y $b$ enteros y $m$ y $n$ enteros positivos. El sistema lineal de ecuaciones en congruencias
$\begin{aligned} x & \equiv a (\mod m) \\ x & \equiv b (\mod n) \end{aligned}$

tiene solución si y sólo si $M := MCD (m, n)$ divide a $a - b$ . En este caso, la solución se puede expresar de manera única módulo $N := mcm (m, n)$ , el mínimo común múltiplo de $m$ y $n$ .

Demostración. Supongamos que $x$ es solución. Por la primera ecuación, $m ∣ x - a$ y como $M ∣ m$ , entonces $M ∣ x - a$ . De manera análoga, $M ∣ x - b$ . Así, $M ∣ (x - b) - (x - a) = a - b$ , lo cual prueba una implicación de la proposición.

Por otro lado, si $M$ divide a $a - b$ , entonces existe una combinación lineal de $m$ y $n$ que da $a - b$ , digamos $y m + z n = a - b$ , que podemos reescribir como $b + z n = a - y m$ . Tomemos $x = b + z n = a - y m$ . Notemos que
$\begin{aligned} x & = a - y m \equiv a (\mod m) \\ x & = b + z n \equiv b (\mod n), \end{aligned}$

de modo que $x$ es solución para el sistema. Notemos que $x + r N$ para cualquier $r$ entero y $N$ el mínimo común múltiplo de $m$ y $n$ también es solución pues $N \equiv 0 (\mod m)$ y $N \equiv 0 (\mod n)$ .

Veamos que la solución es única módulo $N$ . Si tenemos $x$ y $y$ que son soluciones al sistema, entonces tenemos
$\begin{aligned} x & \equiv a \equiv y (\mod m) \\ x & \equiv b \equiv y (\mod n), \end{aligned}$

lo cual implica $m ∣ x - y$ y $n ∣ x - y$ . Como $N$ es el mínimo común múltiplo, $N ∣ x - y$ , de modo que $x \equiv y (\mod N)$ .

Terminamos esta sección con un teorema que recopila todo lo que hemos mostrado para dos ecuaciones lineales.

Teorema 2. Consideremos el sistema de ecuaciones
$\begin{aligned} a x & \equiv b (\mod m) \\ c x & \equiv d (\mod n) . \end{aligned}$

Si $MCD (a, m)$ no divide a $b$ o $MCD (c, n)$ no divide a $d$ , entonces el sistema no tiene solución. Si tenemos ambas divisibilidades, entonces el sistema original es equivalente al sistema
$\begin{aligned} x & \equiv e (\mod m^{'}) \\ x & \equiv f (\mod n^{'}), \end{aligned}$

donde $e$ y $f$ son las soluciones únicas a las reducciones de la primer y segunda congruencia respectivamente. Si $MCD (m^{'}, n^{'})$ no divide a $e - f$ , entonces el sistema original no tiene solución. Si sí, entonces el sistema original tiene una única solución módulo $mcm (m^{'}, n^{'})$ .

Ejemplo 2. Determina las soluciones al siguiente sistema lineal de ecuaciones:
$\begin{aligned} 4 x & \equiv 12 (\mod 24) \\ 10 x & \equiv 5 (\mod 75) . \end{aligned}$

Solución. Para la primera ecuación, notamos que $MCD (4, 24) = 4$ sí divide a $12$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x \equiv 3 (\mod 6)$ .

Para la segunda ecuación, notamos que $MCD (10, 75) = 5$ sí divide a $5$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $2 x \equiv 1 (\mod 15)$ . La solución de esta ecuación es $x \equiv 8 (\mod 15)$ . De este modo, el sistema original es equivalente al sistema:

$\begin{aligned} x & \equiv 3 (\mod 6) \\ x & \equiv 8 (\mod 15) . \end{aligned}$

Tenemos que $MCD (6, 15) = 3$ . Pero $3$ no divide a $3 - 8 = - 5$ . Entonces este sistema no tiene solución, y por lo tanto el original tampoco.

$△$

Hagamos un ligero cambio en el sistema de ecuaciones.

Ejemplo 3. Determina las soluciones al siguiente sistema lineal de ecuaciones:
$\begin{aligned} 4 x & \equiv 20 (\mod 24) \\ 10 x & \equiv 5 (\mod 75) . \end{aligned}$

Solución. Para la primera ecuación, notamos que $MCD (4, 24) = 4$ sí divide a $20$ así que la ecuación sí tiene solución, y su conjunto solución es el mismo que el de $x \equiv 5 (\mod 6)$ .

Tenemos que $MCD (6, 15) = 3$ y que $3$ sí divide a $5 - 8 = - 3$ , de modo que sí hay solución. Para encontrarla, expresamos a $- 3$ como combinación lineal de $6$ y $15$ : $5 - 8 = - 3 = (- 3) \cdot 6 + 1 \cdot 15.$

De aquí, $x = 8 + 15 = 23$ es una solución, y por lo tanto el conjunto de soluciones queda descrito módulo $mcm (6, 15) = 30$ de manera única como $x \equiv 23 (\mod 30)$ .

$△$

El teorema chino del residuo

Varias de las ideas que usamos para un sistema de dos ecuaciones lineales las podemos reciclar para cuando queremos encontrar una $x$ que satisfaga simultáneamente el sistema de ecuaciones lineales en congruencias
$\begin{aligned} a_{1} x & \equiv b_{1} (\mod m_{1}) \\ a_{2} x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ a_{n} x & \equiv b_{n} (\mod m_{n}) \end{aligned}$

Si este sistema tiene solución, entonces claramente:

Cada una de las ecuaciones debe tener solución y,
cada par de ellas debe tener solución.

Lo impresionante del siguiente teorema es que estas dos condiciones son las únicas que tenemos que verificar para que el sistema tenga solución. Y afortunadamente ya estudiamos cuándo dos ecuaciones lineales en congruencias tienen una solución simultánea.

Si cada una de las ecuaciones del sistema tiene solución, entonces es única, así que podemos remplazar cada ecuación por su solución y obtener un sistema de ecuaciones en donde todos los coeficientes de $x$ son $1$ (como le hicimos en el caso de dos ecuaciones). El siguiente resultado estudia estos sistemas.

Teorema 3. Sea $n \geq 2$ un entero, $b_{i}$ enteros para $i \in {1, \dots, n}$ y $m_{i}$ enteros positivos para $i \in {1, \dots, n}$ . El sistema de ecuaciones en congruencias
$\begin{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \end{aligned}$
tiene solución si y sólo si para cada par de índices $i$ y $j$ en ${1, 2, \dots, n}$ se tiene que la ecuación $i$ y la ecuación $j$ tienen solución, es decir, si y sólo si $MCD (m_{i}, m_{j}) ∣ b_{i} - b_{j}$ . En este caso, la solución es única módulo $mcd (m_{1}, \dots, m_{n})$ .

Demostración. Si el sistema completo tiene solución, entonces claramente cualquier par de ecuaciones tiene solución. Para demostrar la afirmación inversa, procederemos por inducción. Para $n = 2$ la afirmación es directa, pues justo la hipótesis es que ese par de ecuaciones tiene solución.

Supongamos entonces el resultado cierto para cuando tenemos $n$ ecuaciones y consideremos un sistema con $n + 1$ ecuaciones
$\begin{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \\ x & \equiv b_{n + 1} (\mod m_{n + 1}) . \end{aligned}$

Supongamos que cualquier par de ellas tienen solución. Tenemos que mostrar que todo el sistema tiene solución y que es única módulo $mcm (m_{1}, \dots, m_{n + 1})$ . Como cualquier par tienen solución, entonces cualquier par de las primeras $n$ tienen solución. Por hipótesis inductiva, entonces podemos reemplazar a las primeras ecuaciones por una ecuación módulo $N = mcm (m_{1}, \dots, m_{n})$ , que es única por la unicidad en la hipótesis inductiva. En otras palabras, existe un entero $c$ tal que el sistema de ecuaciones original es equivalente al sistema de ecuaciones
$\begin{aligned} x & \equiv c (\mod N) \\ x & \equiv b_{n + 1} (\mod m_{n + 1}) \end{aligned}$

Mostraremos ahora que este sistema tiene solución. Para esto, basta mostrar que $MCD (N, m_{n + 1})$ divide a $c - b_{n + 1}$ .

Como $c$ es solución del sistema para las primeras $n$ ecuaciones, tenemos que $c \equiv b_{i} (\mod m_{i})$ para toda $i = 1, \dots, n$ , es decir, $m_{i} ∣ c - b_{i}$ . Por transitividad, $MCD (m_{n + 1}, m_{i}) ∣ c - b_{i}$ .

Como cualquier par de ecuaciones de las originales tenía solución, tenemos que $MCD (m_{n + 1}, m_{i}) ∣ b_{i} - b_{n + 1}$ . De esta forma, $MCD (m_{n + 1}, m_{i}) ∣ - (c - b_{i}) - (b_{i} - b_{n + 1}) = b_{n + 1} - c .$

Con esto mostramos que cada $MCD (m_{n + 1}, m_{i})$ divide a $b_{n + 1} - c$ , de modo que el mínimo común múltiplo de estos números también divide a $b_{n + 1} - c$ . Pero el mínimo común múltiplo de estos números precisamente $MCD (N, m_{n + 1})$ .

En otras palabras, el sistema
$\begin{aligned} x & \equiv c (\mod N) \\ x & \equiv b_{n + 1} (\mod m_{n + 1}), \end{aligned}$

que es esquivalente al original, tiene una solución, y esta es única módulo $mcm (N, m_{n + 1}) = mcm (m_{1}, \dots, m_{n}, m_{n + 1}) .$

Esto es justo lo que queríamos para dar el paso inductivo.

Como corolario, obtenemos el teorema chino del residuo, que habla acerca de soluciones a sistemas de ecuaciones en los cuales los módulos que tomamos son primos relativos entre sí.

Teorema 4 (teorema chino del residuo). Sea $n \geq 2$ un entero, $b_{i}$ enteros para $i \in {1, 2, \dots, n}$ y $m_{i}$ enteros positivos para $i \in {1, \dots, 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{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \end{aligned}$
tiene una y sólo una solución módulo $m_{1} m_{2} \dots m_{n}$ .

Demostración. Como cada pareja de módulos son primos relativos, tenemos que $MCD (m_{i}, m_{j}) = 1$ y entonces claramente cada par de ecuaciones tiene solución. Por el Teorema 3, el sistema tiene solución y esta es única módulo el mínimo común múltiplo de $m_{1}, \dots, m_{n}$ , que como son primos relativos dos a dos, es $m_{1} m_{2} \dots m_{n}$ .

La demostración del Teorema 3 también nos da un procedimiento para resolver de manera práctica los sistemas de ecuaciones lineales en congruencias:

Si los coeficientes de $x$ del sistema no son $1$ , entonces primero resolvemos todas las ecuaciones con coeficiente distinto de $1$ para transformarla en una del estilo de las del Teorema 3. Si alguna no se puede, entonces el sistema no tiene solución.
Una vez que el sistema está en la forma del Teorema 3, verificamos si cada par de ecuaciones tienen solución calculando los máximos comunes divisores de dos en dos y viendo que dividen a las restas respectivas. Si alguno de estos pares falla, entonces el sistema no tiene solución.
Si todos los pares cumplen la hipótesis, entonces resolvemos las primeras dos ecuaciones para remplazarlas por otra módulo su mínimo común múltiplo. Luego, usamos esa que obtuvimos y la tercera para remplazarlas por otra. Seguimos así hasta que sólo nos queden dos ecuaciones. La solución a esas será la solución al sistema original.

Ejemplo. Resolvamos el siguiente sistema de congruencias:

$\begin{aligned} x & \equiv 11 (\mod 5) \\ x & \equiv 5 (\mod 7) \\ x & \equiv 7 (\mod 11) \end{aligned}$

Solución. Los números $5$ , $7$ y $11$ son primos relativos por parejas, de modo que la solución existe y es única módulo $5 \cdot 7 \cdot 11 = 385$ . Para encontrarla, primero resolvemos las primeras dos ecuaciones. Estas corresponden al sistema
$\begin{aligned} x & \equiv 11 \equiv 1 (\mod 5) \\ x & \equiv 5 (\mod 7) \end{aligned}$

Para encontrar la solución, ponemos a $1 - 5 = - 4$ como combinación lineal de $5$ y $7$ , que tras explorar un poco, se puede hacer así: $1 - 5 = - 4 = 2 \cdot 5 + (- 2) \cdot 7$ . De este modo, la solución es $x \equiv 5 - 14 \equiv - 9 \equiv 26 (\mod 35)$ (este es un buen momento para substituir en las dos ecuaciones originales y ver que todo vaya bien).

Así, el sistema original es equivalente al sistema
$\begin{aligned} x & \equiv 26 (\mod 35) \\ x & \equiv 7 (\mod 11) \end{aligned}$

Ahora lo que tenemos que hacer es expresar a $26 - 7 = 19$ como combinación lineal de $35$ y $11$ . Es difícil encontrar una combinación «al tanteo», así que aquí es mejor usar el algoritmo de la división de Euclides:
$\begin{aligned} 35 & = 3 \cdot 11 + 2 \\ 11 & = 2 \cdot 5 + 1 \end{aligned}$

De aquí, $1 = 11 - 2 \cdot 5 = 11 - (35 - 3 \cdot 11) \cdot 5 = (- 5) \cdot 35 + 16 \cdot 11,$ por lo que $19 = (- 5 \cdot 19) \cdot 35 + (19 \cdot 16) \cdot 11 = (- 95) \cdot 35 + (304) \cdot 11.$

Así, la solución al sistema está dada por $x = 7 + 304 \cdot 11 = 3351 \equiv 271 (\mod 385)$ .

Más adelante…

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 2 sí son soluciones de la ecuación original.
Cuando un sistema de dos ecuaciones en módulos $m$ y $n$ sí tiene solución, ¿cuántas soluciones módulo $m n$ tiene?
Usando $(\dots)$ para máximo común divisor y $[\dots]$ para mínimo común múltiplo, demuestra que para cualesquiera enteros $m_{1}, m_{2}, \dots, m_{n}$ se tiene que $([m_{1}, \dots, m_{n}], m_{n + 1}) = [(m_{1}, m_{n + 1}), \dots, (m_{n}, m_{n + 1})] .$
Verifica que las soluciones del último ejemplo en efecto satisfacen el sistema de ecuaciones inicial.
Demuestra que para cualquier entero $n \geq 1$ existen $n$ enteros consecutivos tal que la factorización en primos de cada uno de ellos usa al menos dos primos diferentes.

Entradas relacionadas

Ir a: Álgebra Superior II
Entrada anterior del curso: Ecuaciones en congruencias
Entrada siguiente del curso: Problemas de ecuaciones en congruencias y teorema chino del residuo

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

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

Por Claudia Silva

3 respuestas

Introducción

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)

Más adelante…

Tarea moral

Entradas relacionadas

Ir a: Álgebra Superior II
Entrada anterior del curso: Teoremas de Fermat y de Wilson
Entrada siguiente del curso: Ecuaciones en congruencias

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Ecuaciones en congruencias

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. Ya que tenemos un buen manejo de la aritmética en congruencias, podemos comenzar a hacernos preguntas acerca de las ecuaciones que pueden se plantear y resolver en estos términos.

Ejemplo 1. ¿Cuáles son las soluciones enteras a la ecuación $x \equiv 3 (\mod 6)$ ?

Solución. Un número $x$ satisface la ecuación si y sólo si $6$ divide a $x - 3$ , lo cual sucede si y sólo si $x$ es de la forma $x = 6 r + 3$ , donde $r$ es un número entero. Así, el conjunto de soluciones es de la forma $6 Z + 3 := {6 r + 3 : r \in Z} .$ Dicho de otra forma, el conjunto de soluciones es la clase de equivalencia del $3$ módulo $6$ , es decir, $[3]_{6}$ .

$△$

Cuando tengamos ecuaciones más complicadas, usualmente lo que haremos es dejar expresada la solución en términos de congruencias, es decir, como uno o varios elementos de $Z_{n}$ . Si se quiere encontrar a todos los enteros (en $Z$ ) que sean solución, basta recordar este ejemplo para expresar a las soluciones en $Z_{n}$ como conjuntos de soluciones en $Z$ .

Ejemplo 2. ¿Cuáles son las soluciones enteras a la ecuación $2 x + 1 \equiv 0 (\mod 7)$ ?

Solución. Trabajemos módulo $7$ . Restando $1$ de ambos lados obtenemos $2 x \equiv - 1 \equiv 6 (\mod 7) .$ Multiplicando por $4$ de ambos lados tenemos que $8 x \equiv 24 \equiv 3 (\mod 7) .$ Como $8 x \equiv x (\mod 7)$ , tenemos que $x \equiv 3 (\mod 7)$ es la solución.

$△$

En el ejemplo anterior encontramos las soluciones módulo $7$ . Si queremos encontrar las soluciones en enteros, basta expresar esta congruencia en términos de enteros: las soluciones en $Z$ son los números de la forma $7 r + 3$ con $r$ entero.

Ecuaciones lineales en congruencias

Una ecuación lineal en congruencias es de la forma $a x \equiv b (\mod n) .$ Vamos a estudiar esta ecuación, viendo cuándo tiene solución y cuántas soluciones módulo $n$ tiene. Hay un caso fácil de estudiar, que es cuando $a$ y $n$ son primos relativos.

Proposición 1. Sean $a, b$ enteros y $n$ un entero positivo tales que $MCD (a, n) = 1$ . Entonces la ecuación $a x \equiv b (\mod n)$ tiene una única solución $x$ módulo $n$ .

Demostración. Como $a$ y $n$ son primos relativos, $a$ tiene un inverso multiplicativo módulo $n$ , digamos $a^{- 1}$ . Afirmamos que $x = a^{- 1} b$ es solución. En efecto, $a (a^{- 1} b) \equiv 1 \cdot b \equiv b (\mod n)$ .

Ahora, afirmamos que la solución es única. Supongamos que $x$ y $y$ son solución. Tendríamos entonces que $a x \equiv b \equiv a y (\mod n) .$ Multiplicando ambos extremos de esta ecuación por $a^{- 1}$ , tenemos que $x \equiv a^{- 1} a x \equiv a^{- 1} a y \equiv y (\mod n) .$

Sin embargo, como ya vimos antes, no siempre pasa que todo elemento tenga inverso multiplicativo. Necesitamos un análisis más detallado.

Notemos que $x$ es solución de $a x \equiv b (\mod n)$ si y sólo si $n$ divide a $a x - b$ , lo cual sucede si y sólo si existe un entero $y$ tal que $a x - b = n y$ . Reordenando, tenemos que $a x - n y = b$ . En otras palabras, la ecuación en congruencias tiene solución si y sólo si podemos expresar a $b$ como combinación lineal entera de $a$ y $n$ , lo cual sucede si y sólo si $b \in a Z + n Z = MCD (a, n) Z,$ es decir, si y sólo si $b$ es múltiplo del máximo común divisor de $a$ y $n$ . Resumimos esta primer parte del análisis en la siguiente proposición.

Proposición 2. Sean $a, b$ enteros y $n$ un entero positivo. La ecuación $a x \equiv b (\mod n)$ tiene solución si y sólo si $MCD (a, n)$ divide a $b$ .

Ahora, queremos entender cuántas soluciones diferentes hay módulo $n$ .

Ejemplo. Encuentra todas las soluciones a la ecuación $4 x \equiv 1 (\mod 8)$ y a la ecuación $4 x \equiv 0 (\mod 8)$ .

Solución. Tenemos que $MCD (4, 8) = 4$ y que $4$ no divide a $1$ , así que la primer ecuación no tiene solución. Tenemos que $4$ sí divide a $0$ , así que la segunda ecuación sí tiene solución. Veamos cuántas tiene.

Notemos que al multiplicar por $4$ cada uno de los elementos $0, 2, 4, 6$ obtenemos respectivamente $0, 8, 16, 24$ , que son todos múltiplos de $8$ , así que estos elementos de $Z_{8}$ son solución. Al multiplicar $4$ por $1, 3, 5, 7$ obtenemos $4, 12, 20, 28$ , que módulo $8$ son $4, 4, 4, 4$ , así que ninguno de estos números son solución. Así, las soluciones son $x \equiv 0, 2, 4, 6 (\mod 8)$ .

$△$

Una forma alternativa de expresar la solución del problema anterior es darse cuenta de que las soluciones en enteros son los números pares, o bien los enteros $n$ tales que $n \equiv 0 (\mod 2)$ . En general, cuando la solución existe, podemos encontrar un módulo en la que la podemos describir de manera única. Este es el contenido de las siguientes dos proposiciones.

Proposición 3. Sean $a, b$ enteros y $n$ un entero positivo tales que $M = MCD (a, n)$ divide a $b$ . Sean $a^{'} = a / M$ , $b^{'} = b / M$ y $n^{'} = n / M$ (con $a^{'}$ , $b^{'}$ , $n^{'}$ enteros). El entero $x$ es solución a la ecuación en congruencias $a x \equiv b (\mod n)$ si y sólo si es solución a la ecuación en congruencias $a^{'} x \equiv b^{'} (\mod n^{'})$ .

Demostración. Tenemos que $x$ es solución a $a x \equiv b (\mod n)$ si y sólo si existe una combinación lineal entera $a x - n y = b$ . Al dividir entre $M \neq 0$ , esto sucede si y sólo si $a^{'} x - n^{'} y = b^{'}$ , lo cual sucede si y sólo si $x$ es solución a la ecuación en congruencias $a^{'} x \equiv b^{'} (\mod n^{'})$ .

Estamos listos para enunciar el resultado principal de esta sección. Viene de la combinación de las ideas anteriores.

Demostración. La primer parte es la Proposición 2. Una vez que sabemos que la ecuación tiene solución, por la Proposición 3 podemos encontrar la ecuación equivalente $a^{'} x \equiv b^{'} (\mod n^{'})$ , en donde $a^{'} = a / M$ y $b^{'} = b / M$ . En esta ecuación, $a^{'}$ y $n^{'}$ son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo $n^{'}$ .

Como empezamos con una ecuación módulo $n$ , quizás queremos saber cuántas soluciones tiene módulo $n$ , y no módulo $n^{'}$ . De manera inmediata, obtenemos el siguiente resultado.

Corolario. Con la notación del teorema anterior, cuando la ecuación tiene solución, entonces tiene $M$ soluciones módulo $n$ .

Ejercicio. Resuelve la ecuación lineal en congruencias $12 x \equiv 18 (\mod 30) .$

Intenta resolver este ejercicio antes de ver la solución. Puedes comenzar calculando el máximo común divisor de $12$ y $30$ .

Solución. El máximo común divisor de $12$ y $30$ es $6$ , que sí divide a $18$ . Entonces sí hay soluciones, y habrá $6$ soluciones módulo $30$ . Para encontrar la ecuación reducida equivalente, dividimos entre $6$ para obtener $2 x \equiv 3 (\mod 5) .$

El inverso de $2$ módulo $5$ es $3$ . Multiplicando en ambos lados por $3$ obtenemos la solución $x \equiv 9 \equiv 4 (\mod 5) .$

Para recuperar las soluciones módulo $30$ , a cada una de estas soluciones le sumamos $30 / 6 = 5$ repetidamente para obtener las soluciones $x \equiv 4, 9, 14, 19, 24, 29 (\mod 30)$ .

$△$

En la siguiente entrada veremos cómo resolver sistemas de ecuaciones lineales en los que tenemos más de una congruencia.

Más adelante…

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

Sea $a$ un entero y $n$ un entero positivo. Sea $M = MCD (a, n)$ y sean $a^{'} = a / M$ y $n^{'} = n / M$ . Muestra que $MCD (a^{'}, n^{'}) = 1$ .
Demuestra el corolario al Teorema 1.
Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
Diseña una ecuación lineal módulo $60$ que tenga exactamente $15$ soluciones módulo $60$ .
Para prepararte para la siguiente entrada, intenta resolver por completo el sistema de congruencias

$\begin{aligned} x & \equiv - 1 (\mod 77) \\ x & \equiv - 1 (\mod 55) \end{aligned}$

Entradas relacionadas

Ir a: Álgebra Superior II
Entrada anterior del curso: Problemas que usan teoremas de Fermat y Wilson
Entrada siguiente del curso: Teorema chino del residuo

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

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 (\mod 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 (\mod 13)$ , $1302 \equiv 2 (\mod 13)$ , $1314 \equiv 1 (\mod 13)$ y $1311 \equiv 11 (\mod 13)$ . Así, trabajando módulo $1$ tenemos que:

$\begin{aligned} 1305 \cdot 1302 + 1314 \cdot 1311 & \equiv 5 \cdot 2 + 1 \cdot 11 \\ \equiv 10 + 11 \equiv 21 \\ \equiv 8 (\mod 13) \end{aligned}$
De esta forma, $1305 \cdot 1302 + 1314 \cdot 1311$ 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, \dots, n - 1}$ tal que $a \equiv r (\mod 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 ∣ (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} (\mod 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 (\mod 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 ∣ a - b$ , $11 ∣ b - c$ y $11 ∣ c - a$ , 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 $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{aligned} 25^{2} & = (20 + 5)^{2} \\ = 20^{2} + 2 \cdot 20 \cdot 5 + 25 \\ \equiv 25, \end{aligned}$

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$ .

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 \dots 770$ , 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 $2002 m + 10^{2003} n = 2$ .

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

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

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, \dots, n}$ y $m_{i}$ enteros positivos para $i \in {1, \dots, 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{aligned} x & \equiv b_{1} (\mod m_{1}) \\ x & \equiv b_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv b_{n} (\mod m_{n}) \end{aligned}$
tiene una y sólo una solución módulo $m_{1} m_{2} \dots 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{aligned} n & \equiv 0 (\mod 2^{3}) \\ n & \equiv - 1 (\mod 3^{3}) \\ n & \equiv - 2 (\mod 5^{3}) \\ n & \equiv - 3 (\mod 7^{3}) \\ n & \equiv - 4 (\mod 11^{3}) \end{aligned}$

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$ .

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.

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Archivo de la etiqueta: congruencias\

Teorema de navidad de Fermat: primos suma de dos cuadrados

Introducción

El teorema de Navidad de Fermat

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

¿Dónde seguir?

Álgebra Superior II: Teorema chino del residuo

Introducción

Sistemas de dos ecuaciones lineales

El teorema chino del residuo

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

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

Introducción

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Álgebra Superior II: Ecuaciones en congruencias

Introducción

Ecuaciones lineales en congruencias

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

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

Introducción

Aritmética modular

Últimos dígitos

Teorema chino del residuo

Más ejemplos

Introducción

El teorema de Navidad de Fermat

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

¿Dónde seguir?

Introducción

Sistemas de dos ecuaciones lineales

El teorema chino del residuo

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Introducción

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Introducción

Ecuaciones lineales en congruencias

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Introducción

Aritmética modular

Últimos dígitos

Teorema chino del residuo

Más ejemplos

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