Seminario de problemas.

Curso 2018–19

Estrategias matemáticas: congruencias

Objetivo.
Dado un entero positivo m, hacer operaciones cuando solamente nos interesa el resto
del resultado al ser dividido por m.

En ese sentido, en cualquier suma a + b se podrá cambiar a por a + m o por a − m

ya que, por ejemplo, a + b y (a + m) + b dan el mismo resto al ser divididos por m. Algo
similar ocurre con las diferencias a − b y en los producto a · b donde también le podremos
sumar/restas múltiplos de m a a o a b. Ası́ pues, para cualquier k ∈ Z, podemos cambiar a
por a − km en las operaciones a ± b y a · b anteriores (lo mismo sirve para b). A este cambio
lo llamaremos reducción (módulo m). El algoritmo de la división asegura que cualquier
entero a puede reducirse módulo m hasta un único r ∈ {0, 1, . . . , m − 1}, su resto al ser
dividido entre m.

Ejemplo.
¿Cuál es el resto de dividir 201810 entre 3?
Una potencia es un producto múltiple, ası́ que como 2018 = 2 + 673 · 3, en
201810 = (2 + 673 · 3) · · · (2 + 673 · 3) podemos reducir módulo 3 cada uno de los
factores quedándonos 210 . Como 210 = (22 )5 = 45 , reduciendo el 4 módulo 3 llega-
mos a que 201810 se reduce a 1 módulo 3. Por tanto, el resto de dividir 201810 entre
3 es 1.

El que a y b den el mismo resto al ser divididos por m lo representaremos por

a ≡ b (mód m)

y diremos que a es congruente con b módulo m.

Ten siempre en cuenta...

a ≡ b (mód m) también es lo mismo que decir que m divide a b − a.

Ası́, en el ejemplo anterior podı́amos haber escrito

201810 ≡ (2 + 673 · 3) · · · (2 + 673 · 3) ≡ 210 ≡ 45 ≡ 15 ≡ 1 (mód 3),

y serı́a una solución clara y correcta.

Criterios de divisibilidad.
Conocer las potencias de 10 módulo m es muy útil ya que los enteros positivos los
escribimos en base 10:
cd 10d + · · · + c1 10 + c0 .

Criterio de divisibilidad por 3: para saber el resto que da un número al ser

dividido entre 3 basta observar que 10 ≡ 1 (mód 3), ası́

cd 10d + · · · + c1 10 + c0 ≡ cd + · · · + c1 + c0 (mód 3)

Es decir, cualquier número da el mismo resto al ser dividido entre 3 que el que da
la suma de sus cifras decimales. Por ejemplo, 2018 ≡ 2 + 1 + 8 ≡ 2 (mód 3).

Criterio de divisibilidad por 9: análogo al anterior.

Criterio de divisibilidad por 4: en este caso las potencias de 10 módulo 4 son:

10 ≡ 2, 102 ≡ 0, 103 ≡ 0, . . . (mód 4). Ası́

cd 10d + · · · + c1 10 + c0 ≡ c1 10 + c0 (mód 4)

y el criterio nos dirı́a que un número es divisible por 4 si y solamente si lo es el

número formado por sus dos últimas cifras.

Criterio de divisibilidad por 11: en este caso las potencias de 10 módulo 11 son
10 ≡ −1, 102 ≡ 1, 103 ≡ −1, . . . (mód 11). Ası́

cd 10d + · · · + c1 10 + c0 ≡ c0 − c1 + c2 − c3 + · · · + (−1)d cd (mód 11)

y el criterio nos dirı́a que un número es divisible por 11 si y solamente si al sumar

las cifras en posición par y restarle las de posición impar se obtiene un múltiplo de
11.

Reducción del exponente en potencias modulares.

Si queremos calcular el resto de dividir an entre m, lo mejor que nos puede pasar
es que conozcamos algún exponente pequeño d tal que ad ≡ 1 (mód m).

En efecto, en tal caso dividiremos n entre d, n = cd + e con 0 ≤ e < |d| y

an ≡ acd+e ≡ (ad )c ae ≡ 1c ae ≡ ae (mód m).

Ejemplo.
¿Cuál es el resto de dividir 14921969 entre 13?
Reducimos la base, 1492 ≡ 114 · 13 + 10 ≡ 10 (mód 13), y examinamos las
potencias de 10 módulo 13 en busca de alguna relación: 101 ≡ 10, 102 ≡ (−3)2 ≡ 9,
103 ≡ 9 · 10 ≡ 9 · (−3) ≡ −27 ≡ −1 (mód 13), por lo que 106 ≡ 1 (mód 13). Puesto
 que 1969 = 328 · 6 + 1,

14921969 ≡ 101969 ≡ (106 )328 · 10 ≡ 10 (mód 13).

Sorprendentemente, a veces podemos encontrar, sin apenas hacer cálculos, exponentes

d tales que ad ≡ 1 (mód m). Eso sı́, necesitaremos que a sea primo con m. Consideramos
todos los números {a1 , . . . , ad } entre 1 y m − 1 primos con m y dividimos cada a · ai entre
m obteniendo a · ai = ci · m + ri . Ahora:
Los números ri son primos con m. En efecto, como a y ai son primos con m, también
ası́ ri .

Los números {r1 , . . . , rd } son distintos entre sı́. En efecto, si ri = rj con i 6= j

entonces m divide a (ci · m + ri ) − (cj · m + rj ) = aai − aaj = a(ai − aj ), y por tanto
m divide a ai − aj , pues a es primo con m. Sin embargo esto no es posible ya que
−(m − 1) < ai − aj < m − 1 y ai − aj 6= 0.
Ası́ pues, {r1 , . . . , rd } = {a1 , . . . ad } ya que el primer conjunto está contenido en el segundo
y ambos tienen el mismo número de elementos. Usando esto obtenemos que a1 · · · ad ≡
r1 · · · rd ≡ (aa1 ) · · · (aad ) ≡ ad a1 · · · ad (mód m) y por tanto que m divide a (ad −1)a1 . . . ar .
Como a1 · · · ar es primo con m concluimos que m divide a ad − 1, es decir,

ad ≡ 1 (mód m).

La cantidad d de enteros entre 1 y m primos con m se denota por φ(m) (función indicatriz
de Euler ).

Teorema de Euler-Fermat.
Si a es primo con m entonces aφ(m) ≡ 1 (mód m).

En el ejemplo anterior, como 10 es primo con 13, sin hacer ninguna operación sabrı́amos
que 1012 ≡ 1 (mód 13). Puesto que 1969 = 164 · 12 + 1, al igual que en ejemplo obtenemos
que 1012 ≡ 1 (mód 13).
Al mı́nimo exponente positivo d que cumple que ad ≡ 1 (mód m) lo llamamos orden
multiplicativo de a módulo m y lo denotamos por o(a). Si an ≡ 1 (mód m) entonces,
dividiendo n entre o(a), n = c · o(a) + r nos dice que ar ≡ 1 (mód m) con 0 ≤ r < o(a).
Por la minimalidad de o(a), r = 0 y o(a) divide a cualquier exponente n tal que an ≡ 1
(mód m).

Orden multiplicativo y su relación con la indicatriz de Euler.

Sea a un entero primo con m. Se tiene que ad ≡ 1 (mód m) si y solo si o(a) divide
a d. En particular o(a) divide a φ(m).

Hay una fórmula sencilla para calcular la indicatriz de Euler. Si m = pe11 · · · perr con
p1 , . . . , pr primos distintos y e1 , . . . , er ≥ 1 entonces

φ(m) = (p1 − 1)pe11 −1 · · · (pr − 1)perr −1 .

 El −1 es especial para primos congruentes con 3 módulo 4.
Si p es un número primo congruente con 3 módulo 4 entonces no existe x tal que
x2 ≡ −1 (mód p).
En efecto, un tal x tendrı́a, módulo p, orden multiplicativo 4 y por lo tanto 4
dividirı́a a φ(p) = p − 1. Sin embargo, p − 1 ≡ 2 (mód 4).

Antes de seguir conviene aprovechar un poco más que si p es primo entonces φ(p) =
p − 1.

Curiosidades módulo un primo p ...

(Pequeño Teorema de Fermat) Si p no divide a a entonces ap−1 ≡ 1 (mód p).

Para cualquier entero a se tiene que ap ≡ a (mód p).

Para cualesquiera enteros a, b se tiene que (a + b)p ≡ ap + bp (mód p).

Es interesante observar que a y b tienen los mismos divisores comunes que b y a − kb

para cualquier k.

Reducir para calcular el máximo común divisor.

mcd(a, b) = mcd(b, a − kb).

Este tipo de manipulaciones puede venir bien en problemas.

Ejemplo (Problems for the mathematical olympiads, A. Negut).

Sean x, y enteros positivos tales que 3x2 + x = 4y 2 + y. Prueba que x − y es un
cuadrado perfecto.
Simplemente escribimos la relación como 3x2 − 3y 2 + x − y = y 2 y, factorizando,
tenemos (x − y)(3x + 3y + 1) = y 2 . Ahora vamos a fijarnos en el máximo común
divisor de los factores: d = mcd(x − y, 3x + 3y + 1) = mcd(x − y, 6y + 1). Ası́ que
d divide a 6y + 1 pero también, por la relación, a y 2 . Concluimos que d = 1. Al ser
primos entre sı́ x − y y 3x + 3y + 1 y tener como producto un cuadrado, ambos son
cuadrados.

Estas manipulaciones ayudan a calcular fácilmente el máximo común divisor (Algorit-

mo euclı́deo). Por ejemplo, para calcular mcd(61, 24) observamos que

61 = 2 · 24 + 13, 24 = 1 · 13 + 11, 13 = 1 · 11 + 2, 11 = 5 · 2 + 1, 2=2·1+0

y ası́

mcd(61, 24) = mcd(24, 13) = mcd(13, 11) = mcd(11, 2) = mcd(2, 1) = mcd(1, 0) = 1.

De los cálculos también vemos, por sustitución regresiva, que

1 = 1 · 11 − 5 · 2 = 1 · 11 − 5(13 − 1 · 11) = −5 · 13 + 6 · 11 = −5 · 13 + 6(24 − 1 · 13)

= −11 · 13 + 6 · 24 = −11(61 − 2 · 24) + 6 · 24 = −11 · 61 + 28 · 24.

Identidad de Bézout.
Dados enteros a, b, siendo al menos uno de ellos no nulo, existen enteros s, t tales
que
mcd(a, b) = s · a + t · b.

La Identidad de Bézout es útil para calcular inversos modulares.

Inversos modulares.
Si a es primo con m ≥ 2 siempre existe 1 ≤ a0 ≤ m−1 tal que a0 a ≡ 1 (mód m). Un
tal número a0 se puede calcular a partir del s en la Identidad de Bézout sa+tm = 1.

Esto viene muy bien para encontrar un x que cumpla un conjunto de ecuaciones del
tipo 
x ≡ a1 (mód n1 )  
x ≡ a2 (mód n2 ) 

.. (∗)
. 


x ≡ ak (mód nk )


cuando n1 , . . . , nk son primos entre sı́ dos a dos. La idea es primero calcular la Identidad
de Bézout si n1n···n
i
k
+ ti ni = 1 y después...

Teorema chino de los restos.

Las soluciones de (∗) son x0 + múltiplos de n1 · · · nk donde
n1 · · · nk n1 · · · nk
x0 = a1 s1 + · · · + ak sk .
n1 nk

Los inversos modulares permiten hacer más cómodas algunas cuentas. Por ejemplo,
dado un número n, lo escribimos como n = 10n0 + d0 donde d0 es la cifra de las unidades.
Para saber si n es divisible por 13 observamos que como 10 · 4 ≡ 1 (mód 13) entonces
n ≡ 0 (mód 13) equivale a decir que 10n0 + d0 ≡ 0 (mód 13) y, multiplicando por el
inverso modular de 10, esto último equivale a n0 + 4d0 ≡ 0. Por ejemplo, para saber si
26234 es múltiplo de 13 calculamos los números 2639, 299, 65, 26 y vemos que como 26 es
múltiplo de 13, también ası́ 2639.
El inverso modular de a es único (si lo tomamos en {1, . . . , m − 1}) debido a que
aa0 ≡ 1, aa00 ≡ 1 (mód m) implica que a00 ≡ (aa0 )a00 ≡ a0 (aa00 ) ≡ a0 (mód m), por lo que
a0 = a00 . También es claro que si a0 es el inverso modular de a entonces a lo será de a0 .
Cuando multipliquemos entre sı́ módulo m todos los elementos en {1, . . . , m − 1} primos
con m, cada uno desaparecerá con su inverso modular, a no ser que él mismo sea su propio
inverso modular (piensa en m − 1 ≡ −1 (mód m)).
 De hecho, dado p primo, los únicos a que son sus propios inversos modulares son los
que cumplen que a2 ≡ 1 (mód p), es decir, p divide a (a + 1)(a − 1). Como 1 ≤ a ≤ p − 1
esto implica que o bien a = 1 o bien a = p − 1. Por tanto hemos demostrado el siguiente
resultado:

Teorema de Wilson.
Sea p un número primo. Se tiene que (p − 1)! ≡ −1 (mód p).

Ejemplo (American Regions Mathematics League, 2002).

1 1 1 1 a
Sae a el entero tal que 1 + 2 + 3 + ··· + 22 + 23 = 23! . Calcular el resto de dividir
a entre 13.
Multiplicando por 23! obtenemos a = 23! + 23! 23! 23! 23!
2 + 3 + · · · + 22 + 23 . Módulo 13
todos estos sumandos son nulos excepto 23!
13 que es congruente con 12! · 10! módulo
13. Usando el Teorema de Wilson y observando que el inverso modular de 11 ≡ −2
(mód 13) es −7 ≡ 6 (mód 13) mientras que el de 12 es −1, el resto de dividir a
entre 13 es congruente con −6 módulo 13. Por tanto ese resto es 7.

Ten siempre en cuenta...

Las igualdades entre números enteros deben mantenerse módulo cualquier m. Esto
permite algunas veces deducir que ciertas igualdades no son posibles.

Algunos problemas acerca de números enteros requieren de esta observación.

Ejemplo (Rusia, 1997).

Encuentra las parejas de primos p, q tales que p3 − q 5 = (p + q)2
En este caso tenemos mezcladas diferentes potencias, pero lo primero que sı́
que es claro es que p > q. Vamos a reducir usando algún módulo pequeño, por
ejemplo 3, a ver qué pasa. Inicialmente obviamos el caso en que p = 3 o q = 3.
Usando el Pequeño Teorema de Fermat tenemos que p − q ≡ (p + q)2 (mód 3). Ası́,
si p ≡ q (mód 3) entonces 0 ≡ q 2 6≡ 0 (mód 3), lo que no es posible. Por tanto
p 6≡ q (mód 3). Pero en este caso (p + q)2 ≡ 0 (mód 3) mientras que p − q 6≡ 0
(mód 3), lo que nuevamente no es posible. Ası́ que no queda más remedio que o
bien p = 3 o bien q = 3. Como 33 − 25 < 0, la única posibilidad es q = 3. En este
caso p3 − 243 = p2 + 6p + 9 implica que p divide a 252, por lo que solamente puede
ser p = 7.

Cuando aparezcan cuadrados o sumas de cuadrados conviene tener en cuenta que,

módulo m, puede no haber muchos cuadrados.
 Restos cuadráticos...
Los cuadrados módulo 3 son solamente 0 y 1.

Los cuadrados módulo 4 son solamente 0 y 1.

La suma de dos cuadrado módulo 4 nunca es 3.

Los cuadrados módulo 8 son solamente 0, 1 y 4.

... muchas otras observaciones de este tipo que se te ocurran.

Problemas bastante complicados pueden abordarse con esta sencilla observación.

Ejemplo (Korea, 1997).

Encuentra todos los enteros x, y, z que cumplen x2 + y 2 + z 2 − 2xyz = 0.
La ecuación es
2xyz = x2 + y 2 + z 2 .
Si x, y, z son impares entonces el lado derecho serı́a impar pero el izquierdo serı́a
par, ası́ que al menos uno de los enteros x, y, z es par, y por lo tanto 2xyz es múltiplo
de 4. Puesto que los cuadrados módulo 4 son 0 y 1, la ecuación obliga a que x, y, z
sean pares.
Escribamos x = 2x1 , y = 2y1 , z = 2z1 . La ecuación queda 16x1 y1 z1 = 4(x21 +
y12 + z12 ), y simplificando,

4x1 y1 z1 = x21 + y12 + z12 .

En este punto nos damos cuenta de que podemos repetir el razonamiento anterior,
y que ası́ x1 = 2x2 , y1 = 2y2 , z1 = 2z2 para ciertos x2 , y2 , z2 . Reiterando el mismo
argumento con estos x2 , y2 , z2 y con los sucesivos que obtengamos, al final llegamos
a que x, y, z son divisibles por infinitas potencias de 2. Esto solo lo cumplen x =
0, y = 0, z = 0.

Otros problemas relativos a ecuaciones con números enteros (ecuaciones diofánticas)

se basan en pı́caras factorizaciones.

Ejemplo (Olimpiada matemática de Polonia).

Encuentra las soluciones enteras de la siguiente ecuación

x2 (y − 1) + y 2 (x − 1) = 1.

Realizamos el cambio x = u+1, y = v +1 de modo que la ecuación se transforma en

(u + 1)2 v + (v + 1)2 u = 1 y en el lado izquierdo ya no hay término independiente. Es
decir, u2 v + 2uv + v + v 2 u + 2uv + u = 1. Si uv fuese −1 entonces el lado izquierdo
valdrı́a −4, por lo que si le sumamos 4 podremos factorizarlo mediante el factor
uv + 1. Es decir, 5 = u2 v + 4uv + v 2 u + u + v + 4 = (uv + 1)(u + v + 4). Ahora
el problema e mucho más sencillo ya que uno de los factores debe ser ±1 y el otro
 ±5. Por tanto hay cuatro posibles sistemas de ecuaciones:
   
u+v = 1 u + v = −9 u + v = −3 u + v = −5
, , , .
uv = 0 uv = 2 uv = 4 uv = −6

Las soluciones para (u, v) son (0, 1), (1, 0), (−6, 1), (1, −6), por lo que las soluciones
para (x, y) son las parejas (1, 2), (−5, 2), (2, 1), (2, −5).

Problemas más complicados requieren entender mejor qué potencias de un número

primo pueden dividir a otros números.
Dado p un número primo sea vp (a) el mayor exponente v tal que pv divide al entero
a. Por ejemplo v2 (40) = 3 ya que 40 = 23 · 5. También serı́a cierto que v5 (40) = 1 y que
v7 (40) = 0.
Dado un primo p que divide a x − y pero que no divide ni a x ni a y vamos a intentar
encontrar qué potencia de p divide a xn − y n . Inicialmente asumimos que p es primo con
n. Recordamos que

xn − y n = (x − y)(xn−1 + xn−2 y + · · · + xy n−2 + y n−1 ).

Como p divide a x − y entonces xn−1 + xn−2 y + · · · + xy n−2 + y n−1 ≡ nxn−1 6≡ 0 (mód p)

ya que n y x son primos con p. Ası́ que en este caso vp (xn − y n ) = vp (x − y). Ahora
abordamos el caso en que p divide a n. Escribimos n = pe N con N primo con p, ası́
e e e e
vp (xn − y n ) = vp ((xp )N − (y p )N ) = vp (xp − y p ) debido al caso inicial que hemos
desarrollado. Ahora escribimos x = y + Kpv con v ≥ 1 y observamos que
     
p p−1 v p p−2 p
xp − y p = (y + Kpv )p − y p = y Kp + y (Kpv )2 + · · · + (Kpv )p
1 2 p
     
v+1 p−1 p p−2 2 v−1 p p pv−v−1
=p y K+ y K p + ··· + K p ,
2 p

de donde, si p 6= 2, la máxima potencia de p que lo divide es pv+1 ya que p divide a todos los
sumandos del paréntesis excepto al primero. Esto nos dice que vp (xp − y p ) = vp (x − y) + 1.
Reiterando llegamos a que
e e e−1 e−1
vp (xn − y n ) = vp (xp − y p ) = vp (xp − yp ) + 1 = · · · = vp (x − y) + vp (n).

Lema LTE (Lifting The Exponent).

Sea p un número primo y sean vp (a) el mayor exponente v tal que pv divide a a, n
un entero positivo y a, b enteros no divisibles por p:

Si p divide a a − b pero p no divide a n entonces vp (an − bn ) = vp (a − b).

Si p 6= 2 y p divide a a − b entonces vp (an − bn ) = vp (a − b) + vp (n).

Si p = 2 divide a a − b y también divide a n entonces v2 (an − bn ) = v2 (a −

b) + v2 (a + b) + v2 (n) − 1.

Si p = 2 y 4 divide a a − b entonces v2 (an − bn ) = v2 (a − b) + v2 (n).

Como consecuencia, también es cierto:

 Si n es impar, no es divisible por p pero p divide a a+b entonces vp (an +bn ) =
vp (a + b).

Si n es impar p 6= 2 y p divide a a + b entonces vp (an + bn ) = vp (a + b) + vp (n).

Ejemplo (T. Shin).

Calcula el menor entero positivo n1 tal que n = n21 cumpla que 7n ≡ 1 (mód 69 ).
Aquı́ el problema es que las potencias modulares módulo 69 son complicadas de
calcular a mano. Usamos otra estrategia. Decir que 7n ≡ 1 (mód 69 ) es lo mismo
que decir que 7n ≡ 1 (mód 29 ) y 7n ≡ 1 (mód 39 ). Usamos el LTE para hacernos
una idea. Para p = 3, 9 ≤ v3 (7n − 1n ) = v3 (7 − 1) + v3 (n) = 1 + 2v3 (n1 ). Ası́ pues, el
mı́nimo exponente de 3 en n1 es 4. También observamos que n no puede ser impar
ya que 7n ≡ 1 (mód 29 ) implica que el orden multiplicativo de 7 divide a n y a
φ(29 ) = 28 , por lo que n es par. Ası́ 9 ≤ v2 (7n −1n ) = v2 (7−1)+v2 (7+1)+v2 (n)−1 =
1 + 3 + 2v2 (n1 ) − 1 implica que el mı́nimo exponente de 2 en n1 es 3. Por tanto, el
mı́nimo n1 posible es n1 = 23 34 = 648.

Ejemplo (Rusia, 1996).

Encuentra todos los enteros positivos n para los cuales existen enteros positivos
x, y, k tales que mcd(x, y) = 1, k > 1 y 3n = xk + y k .
Es sorprendente la cantidad de información que puede proporcionar el LTE
en esta situación. Primero observamos que, por supuesto, x + y es impar o de lo
contrario xk + y k serı́a par. También es cierto que k es impar (basta examinar la
ecuación en módulo 3). Ahora nos preguntamos por sus divisores primos. Sea p
primo impar divisor de x + y (esto implica que no puede dividir ni a x ni a y ya
que mcd(x, y) = 1). Tenemos que vp (3n ) = vp (x + y) + vp (k). Por tanto, si p 6= 3
entonces p no divide ni a x + y ni a k, es decir, x + y = 3m , k = 3e para ciertos m, e
con e ≥ 1 y n = m + e. Esto nos lleva a
e e
(x + y)3e = 3n = x3 + y 3 .

Inmediatamente vemos que esta relación no es muy natural ya que el lado de la

derecha tenderá a ser mucho mayor que el de la izquierda. Ası́ que el problema pasa
a ser un problema de acotaciones. Si lo piensas con cuidado verás que las únicas
soluciones para (x, y, e) son (1, 2, 1) y (2, 1, 1), las cuales se corresponden con las
soluciones (1, 2, 3) y (2, 1, 3) para (x, y, k).

Referencias
1. J. Stevens: Olympiad Number Theory Through Challenging Problems.

2. T. Andreescu, D. Andrica, I. Cucurezeanu: An Introduction to Diophantine Equa-

tiosn. A problem-based approach. Birkhäuser, 2010.