Teorema Chino del Resto, Pequeño Teorema de Fermat

Juan Pablo De Rasis

25 de mayo de 2019

Nos proponemos ilustrar algunos ejemplos donde la utilización del Teorema Chino del
Resto o el Pequeño Teorema de Fermat juega un papel fundamental.
Comenzaremos con un ejercicio donde la clave consiste en armar un sistema de ecua-
ciones lineales de congruencia adecuado y resolverlo.

Ejercicio 1. Una banda de 13 piratas asaltó un barco mercantil y se hizo con una gran
cantidad de monedas de oro, todas idénticas entre sí. Cuando trataron de distribuirlas
equitativamente entre ellos, les sobraron 8 monedas. Por lo tanto, decidieron no repartirlas.
Imprevistamente, dos de ellos contrajeron sarampión y murieron. Al volver a intentar
repartir las monedas, les sobraron 3, y por lo tanto volvieron a cancelar la distribución.
Posteriormente murieron otros 3 piratas ahogados. Los restantes volvieron a intentar
distribuir las monedas, pero les sobraron 5. Cansados de tanto intentar distribuir sin poder
ser equitativos, optaron por guardar las monedas hasta que se les ocurriese una solución.
Tiempo después, los piratas se arrepintieron de todas sus fechorías y decidieron hacer
un acto caritativo a modo de redención. Se dirijeron a un pueblo muy pobre en el que había
exactamente 1136 personas viviendo, y decidieron integrarse al pueblo para iniciar una
nueva vida. Más aún, decidieron que repartirían equitativamente todas las monedas entre
todos los habitantes del pueblo, incluyéndose a ellos. Pero, para su sorpresa, volvieron a
sobrar monedas. ¿Cuántas monedas sobraron?

Solución. Sea x la cantidad de monedas robadas. En el primer intento de distribución

sobraron 8 monedas al intentar distribuirlas entre 13 piratas, por lo tanto x ≡ 8 (mod 13).
Tras la muerte de dos piratas por sarampión, se intentó distribuir la misma cantidad
de monedas entre los 11 piratas restantes pero sobraron 3, es decir, x ≡ 3 (mod 11).
Finalmente, tras la muerte de tres piratas por ahogamiento, el intento de distribución entre
los 8 piratas restantes dejó un sobrante de 5 monedas, por lo tanto x ≡ 5 (mod 8).
Cuando los piratas se integraron al pueblo con 1136 personas, se buscó distribuir las
monedas equitativamente entre 1136 + 8 = 1144 personas. Por consiguiente, se nos está
preguntando por el resto de x en la división por 1144. Como 1144 = 13 × 11 × 8 y estos
tres factores son coprimos dos a dos, la respuesta será inducida por la solución del siguiente
sistema de ecuaciones lineales de congruencia:

x ≡ 8 (mod 13)
x ≡ 3 (mod 11)
x ≡ 5 (mod 8)


De la primera ecuación surge que existe k ∈ N0 tal que x = 13k + 8. Sustituyendo en

la segunda ecuación, obtenemos 13k + 8 ≡ 3 (mod 11), que equivale a 2k ≡ 6 (mod 11).
Como 2 y 11 son coprimos, esto equivale a k ≡ 3 (mod 11)1 . Por lo tanto existe m ∈ N0
1
Recordar la siguiente propiedad: Si a, b, c, m son enteros tales que m 6= 0 y (m : c) = 1, entonces se
tiene que a ≡ b (mod m) si y solo si ac ≡ bc (mod m).

1
tal que k = 11m + 3. Sustituyendo en nuestra expresión para x obtenemos

x = 13k + 8 = 13 (11m + 3) + 8 = 143m + 47

Reemplazando en la última ecuación, obtenemos 143m + 47 ≡ 5 (mod 8), que equivale a

7m ≡ 6 (mod 8), que a su vez equivale a −m ≡ −2 (mod 8), y esto, finalmente, equivale a
m ≡ 2 (mod 8). Por lo tanto existe j ∈ N0 tal que m = 8j + 2. De esta forma, obtenemos

x = 143m + 47 = 143 (8j + 2) + 47 = 1144j + 333

Por lo tanto x ≡ 333 (mod 1144), que por el Teorema Chino del Resto es la única
solución. Concluimos que, cuando se intentó distribuir las monedas entre los habitantes del
pueblo, sobraron 333 monedas.

El ejercicio anterior tuvo la ventaja de que el sistema armado de ecuaciones lineales

de congruencia satisfacía las hipótesis del Teorema Chino del Resto para garantizar la
existencia de la solución. El siguiente ejercicio ilustra una situación donde esto no ocurre.

Ejercicio 2. ¿Existe n ∈ N tal que su dígito de las unidades es igual a 9 y además n3 + 3n

es divisible por 5?

Solución. Supongamos que existe n ∈ N como en el enunciado. Que su dígito de las

unidades sea igual a 9 equivale a la congruencia n ≡ 9 (mod 10). En particular, se tiene
que n ≡ 9 ≡ 4 (mod 5)2 . Por lo tanto, la condición 5 | n3 + 3n equivale a

43 + 3 n ≡ 0 (mod 5)

3n ≡ −43 ≡ 1 (mod 5)
Analizaremos entonces el comportamiento de las potencias de 3 módulo 5. Comenzamos
observando que 34 ≡ 1 (mod 5), por lo tanto 34k ≡ 1 (mod 5) para todo k ∈ N0 . Multipli-
cando sucesivamente por 3 esta congruencia, obtenemos

34k ≡ 1 (mod 5)

34k+1 ≡ 3 (mod 5)
34k+2 ≡ 9 ≡ 4 (mod 5)
34k+3 ≡ 12 ≡ 2 (mod 5)
Si volvemos a multiplicar por tres obtendremos 34(k+1) , y volvemos al primer caso, donde
el exponente es múltiplo de 4.
En consecuencia, 3n ≡ 1 (mod 5) si y solo si n ≡ 0 (mod 4).
Resumiendo, las condiciones del enunciado equivalen a n ≡ 9 (mod 10) y n ≡ 0 (mod 4).
Sin embargo, el sistema

 x ≡ 4 (mod 5)
x ≡ 9 (mod 10)
⇒ x ≡ 1 (mod 2)
x ≡ 0 (mod 4)
x ≡ 0 (mod 4)


no admite ninguna solución, ya que las últimas dos relaciones son incompatibles entre sí.
Concluimos que no existe ningún n ∈ N que satisfaga las condiciones del enunciado.
2
Recordar la siguiente propiedad: Si m, n ∈ Z son no nulos y tales que m | n, y además existen a, b ∈ Z
que satisfacen a ≡ b (mod n), entonces a ≡ b (mod m).

2
 Veamos un ejercicio donde requeriremos tanto del Pequeño Teorema de Fermat como
del Teorema Chino del Resto.
7
Ejercicio 3. Hallar el resto de 77 en la división por 3864.3
7
Solución. Factorizamos 3864 como 3 × 7 × 8 × 23. Llamamos x = 77 . Hallaremos el resto
de x en la división por 3, 7, 8 y 23 y encontraremos el resto módulo 3 × 7 × 8 × 23 = 3864
mediante el Teorema Chino del Resto.
Es claro que x ≡ 0 (mod 7). Por otra parte, como 7 ≡ 1 (mod 3), entonces
7
x ≡ 17 = 1 (mod 3)

Además, como 7 ≡ −1 (mod 8), entonces

7
x ≡ (−1)7 = −1 ≡ 7 (mod 8)

Solamente nos queda hallar el resto de x en la división por 23. Por el Pequeño Teorema de
Fermat tenemos que 722 ≡ 1 (mod 23). Como 77 ≡ 17 (mod 22), entonces 77 = 22k + 17
con k ∈ N. De esta manera,
7
k
77 = 722k+17 = 722 · 717 ≡ 1k · 717 = 717 (mod 23)

Para calcular el resto de 717 en la división por 23, podemos reescribirlo como

3
2
x ≡ 717 = 79 · 78 = 73 74 ≡ (−2)3 · 92 = −648 ≡ 19 (mod 23)

Concluimos que x satisface 


 x ≡ 0 (mod 7)
x ≡ 1 (mod 3)


 x ≡ 7 (mod 8)
x ≡ 19 (mod 23)


Este sistema puede resolverse rutinariamente, obteniendo como resultado x ≡ 847 (mod 3864).
7
Concluimos que 77 tiene resto 847 en la división por 3864.

Finalizaremos con un último ejercicio tomado del Certamen Nacional de la Olimpíada

Matemática Argentina llevado a cabo en el año 2000 (Problema 5 del Nivel 3).

Ejercicio 4. Un programa de computadora genera una sucesión de números con la siguiente

regla: el primer número lo escribe Camilo; a partir de entonces, el programa calcula la
división entera del último número generado por 18; obtiene así un cociente y un resto.
La suma de ese cociente más ese resto es el siguiente número generado. Por ejemplo,
si el número de Camilo es 5291, la computadora hace 5291 = 293 × 18 + 17, y genera
el 310 = 293 + 17. El siguiente número generado será 21, pues 310 = 17 × 18 + 4 y
17 + 4 = 21; etc. Cualquiera sea el número inicial de Camilo, a partir de algún momento,
la computadora genera siempre un mismo número. Determinar cuál es ese número que se
repetirá indefinidamente, si el número inicial de Camilo es igual a 2110 .

Solución. Podemos modelizar el problema con la siguiente sucesión recursiva: para cada
n ∈ N definimos an ∈ N inductivamente, de la siguiente manera: a1 = 2110 y, para todo
n ∈ N, an+1 es igual a la suma entre el cociente y el resto de dividir an por 18.
c
c
3
Téngase presente que, si a, b, c ∈ N, entonces ab puede no ser lo mismo que ab . Por ejemplo, no es
2 2
lo mismo 35 = 325 que 35 = 310 .

3
 Si n ∈ N es arbitrario, escribimos an = 18k + r donde k ∈ N0 es el cociente y r ∈ N0 el
resto de la división de an por 18. Entonces an+1 = k + r, luego

an − an+1 = (18k + r) − (k + r) = 17k

Eso implica que nuestra sucesión decrece de a múltiplos de diecisiete. En particular,

el resto módulo 17 no cambia en ningún paso de la sucesión: todos los elementos de la
sucesión son congruentes módulo 17.
Más aún, si an ≥ 18 entonces su cociente k en la división por 18 es estrictamente
positivo, es decir, k > 0, por lo tanto an − an+1 = 17k > 0, es decir, an > an+1 . Si, en
cambio, an < 18, entonces k = 0 y

an = 18 · 0 + r = 0 + r = k + r = an+1

Es decir, en el momento en que un elemento de la sucesión es menor que 18, ese

elemento se repetirá indefinidamente en los siguientes pasos de la sucesión.
Resumimos nuestras conclusiones. Dado n ∈ N, se cumple:

(1) Si an ≥ 18, entonces an+1 < an .

(2) Si an < 18, entonces an+1 = an y este número se repetirá indefinidamente en la sucesión.

(3) Todos los elementos de la sucesión tienen el mismo resto en la división por 17.

Por lo tanto, a partir de estas tres conclusiones, podemos razonar de la siguiente manera:

• La sucesión comienza en 2110 .

• Por (1), la sucesión comenzará a decrecer hasta llegar a un número menor que 18.

• Una vez que llegamos a un número menor que 18, por (2) ese será el número que se
repetirá indefinidamente.

• Ese número que se repite indefinidamente no puede ser igual a 17, porque si lo fuera,
entonces, como 17 ≡ 0 (mod 17), por (3) tendríamos que 2110 ≡ 0 (mod 17), lo
cual es trivialmente falso. Por lo tanto el número que se repite indefinidamente está
acotado entre 0 y 16.

• Ese número que se repite indefinidamente, que está entre 0 y 16, por (3) es congruente
con 2110 módulo 17.

• Por lo tanto, el número que se repite indefinidamente es r17 2110 , ya que es un

número entre 0 y 16 congruente con 2110 módulo 17.

Eso significa que debemos calcular el resto de 2110 en la división por 17. Por el Pequeño
Teorema de Fermat tenemos que 216 ≡ 1 (mod 17). Escribimos 110 = 16 · 6 + 14, luego

6
2110 = 216·6+14 = 216 214 ≡ 214 ≡ 13 (mod 17)

Concluimos que la respuesta a nuestro problema es 13.