Teoría de las congruencias versión 5

Vista previa del material en texto

Teoría de Números I
Teoría de las Congruencias
Material elaborado por
Osvaldo Vega
Campus Universitario
San Lorenzo, Paraguay
Índice
1. Enteros congruentes 3
2. Caracterización de los enteros congruentes 4
3. Propiedades de las congruencias 5
4. Sistema completo de restos módulo m 8
5. Sistema reducido de restos módulo m 9
6. La función Φ de Euler 9
7. Teorema de Fermat 11
8. Generalización de Euler 12
9. Congruencias lineales 14
9.1. Soluciones de una congruencia lineal y ecuaciones diofánticas . . . . . . . . 14
9.2. Teorema Chino del resto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.3. Grado de una congruencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
10.Congruencias Cuadráticas 19
10.1.Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
10.2.Criterio de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Bibliografía 22
2
1. Enteros congruentes
La Teoría elemental de números estudia principalmente los números enteros y sus propieda-
des mediante sus propios métodos y técnicas sin involucrar a otros campos de Matemática
además de las elementales. Algunos temas que trata la Teoría elemental de números son la
divisibilidad y las congruencias, y este material pretende brindar los conceptos y fundamen-
tos básicos sobre las congruencias en Z.
El desarrollo del material seguirá principalmente la misma línea del texto (Filho, 1981), pero
con consultas a libros clásicos de Teoría de números como (Zuckerman, 1976) y (Pettofrez-
zo, 1986).
Definición 1.1. Sean a y b dos números enteros cualesquiera y sea m un número entero
positivo. Se dice que a es congruente a b módulo m si m divide a a− b. Es decir, a
es congruente a b módulo m si existe un número entero c tal que a− b = cm. Si a es
congruente a b módulo m escribiremos a ≡ b (modm)
En símbolos:
a ≡ b (modm)⇔ m|(a− b)
equivalentemente
a ≡ b (modm)⇔ ∃ c ∈ Z | a− b = mc.
Ejemplo 1.1. Algunas congruencias son:
3 ≡ 13 (mod 5) porque 5 divide a (3− 13),
− 14 ≡ 10 (mod 4) porque 4 divide a (−14− 10),
68 ≡ (−9) (mod 11) porque 11 divide a (68− (−9)).
Si a no es congruente a b módulo m, es decir, si m - (a − b), diremos que a es
incongruente a b módulo m, y escribiremos:
a 6≡ b (modm)
Ejemplo 1.2. Algunas incongruencias son:
2 6≡ 44 (mod 10) porque 10 no divide a (2− 44),
− 39 6≡ 1 (mod 3) porque 3 no divide a (−39− 1),
48 6≡ (−70) (mod 17) porque 17 no divide a (48− (−70)).
Observación 1.1.
1. Dos enteros cualesquiera son congruentes módulo 1.
2. Dos enteros son congruentes módulo 2 si y solo si tienen la misma paridad.
3. Un entero a es congruente a 0 módulo n si y solo si a es un múltiplo de n.
3
Ejemplo 1.3. Si n es cualquier entero tal que n ≡ 6 (mod 15), entonces n ≡ 1 (mod 5).
Demostración. Sea n ∈ Z con n ≡ 6 (mod 15), entonces existe c ∈ Z tal que
n− 6 = 15c
de modo que
n− 1 = 5(3c+ 1),
y esto implica que
5|(n− 1).
Por lo tanto, n ≡ 1 (mod 5).
Ejemplo 1.4. Si 1906 ≡ 1752 (modn), hallar los posibles valores de n.
Solución:
Si 1906 ≡ 1752 (modn), entonces n|(1906−1752), es decir, n|154. Los posibles valores
de n son los divisores positivos de 154, estos son: 1, 2, 7, 11, 14, 22, 77 y 154.
2. Caracterización de los enteros congruentes
Teorema 2.1. Sean a y b dos números enteros, a ≡ b (modn) si y solo si a y b
dejan el mismo resto cuando se dividen por n.
Demostración. Supongamos que a ≡ b (modn), entonces existe c ∈ Z tal que:
a− b = c n.
Sea r el resto de dividir b entre n, es decir,
b = nq + r, con 0 ≤ r < n.
De la última igualdad:
a = cn+ b = cn+ nq + r = (c+ q)n+ r,
y como 0 ≤ r < n, tenemos que r es el resto de dividir a por n. Así a y b dejan el
mismo resto cuando se dividen por n.
Recíprocamente, si a y b tienen el mismo resto r cuando se dividen por n. Entonces:
a = nq1 + r y b = nq2 + r con 0 ≤ r < n.
Restando miembro a miembro las dos últimas igualdades, tenemos que a− b = (q1 − q2)n,
lo que implica que n|(a− b). Así a ≡ b (modn).
Ejemplo 2.1. Sabemos que −1253 ≡ 1247 (mod 5) porque 5 | (1247− (−1253)). Por el
Teorema 2.1, −1253 y 1247 dejarán el mismo resto al dividir entre 5.
4
3. Propiedades de las congruencias
Teorema 3.1. Sea n un número entero positivo y sean a, b y c números enteros cuales-
quiera. Entonces se cumplen las siguientes propiedades:
1) a ≡ a (modn).
2) Si a ≡ b (modn), entonces b ≡ a (modn).
3) Si a ≡ b (modn) y b ≡ c (modn), entonces a ≡ c (modn).
Demostración.
1) Cualquier entero positivo n divide a 0. Luego n|(a − a), lo que implica que
a ≡ a (modn).
2) Si a ≡ b (modn), entonces existe c ∈ Z tal que a− b = cn, del cual se tiene que
b− a = (−c)n, lo que implica que b ≡ a (modn).
3) Si a ≡ b (modn) y b ≡ c (modn) entonces existen los números enteros d y e
tales que:
a− b = d n y b− c = e n.
Por tanto:
a− c = (a− b) + (b− c) = d n+ e n = (d+ e)n.
Así, a ≡ c (modn).
Observación 3.1. Dado un entero positivo n, la relación R en el conjunto de los números
enteros Z, definida por:
aRb⇔ a ≡ b (modn)
es de equivalencia ya que por el Teorema 3.1, dicha relación es reflexiva, simétrica y transi-
tiva. Esta relación de equivalencia R en Z se denomina “congruencia módulo n”.
Teorema 3.2. Sea n un número entero positivo y sean a y b números enteros cuales-
quiera. Entonces se cumplen las siguientes propiedades:
1) Si a ≡ b (modn) y m|n, con m > 0, entonces a ≡ b (modm).
2) Si a ≡ b (modn) y , m , es un entero positivo, entonces am ≡ bm (modnm).
3) Si a ≡ b (modn) , y a, b y n son divisibles por el número entero m > 0, entonces
a
m
≡ b
m
(
mod
n
m
)
.
Demostración.
1) Si a ≡ b (modn), entonces n | (a − b). Así tenemos que m|n y n | (a − b), que
implican que m | (a− b). De modo que a ≡ b (modm).
2) Si a ≡ b (modn), entonces n | (a− b). Y como m > 0, entonces nm | (a− b)m.
Así tenemos que nm | (am− bm). Luego am ≡ bm (modnm).
3) Si a ≡ b (modn), entonces n | (a − b). Si además a, b y n son divisibles por
el número entero m > 0, entonces a − b es divisible por m y n
m
| a− b
m
. Por lo
tanto,
a
m
≡ b
m
(
mod
n
m
)
.
5
Ejemplo 3.1. Algunas aplicaciones del Teorema 3.2 son:
1) 47 ≡ −7 (mod 9) implica que 47 ≡ −7 (mod 3) ya que 3|9.
2) 2 ≡ 77 (mod 5) implica que 4 ≡ 154 (mod 10).
3) −90 ≡ 1710 (mod 18) implica que −90
9
≡ 1710
9
(mod 18
9
). Es decir, podemos concluir
que −10 ≡ 190 (mod 2).
Teorema 3.3. Sea n un número entero positivo y sean a, b, c y d números enteros
cualesquiera. Entonces se cumplen las siguientes propiedades:
1) Si a ≡ b (modn) y c ≡ d (modn), entonces a + c ≡ b + d (modn) y ac ≡
bd (modn).
2) Si a ≡ b (modn), entonces a+ c ≡ b+ c (modn) y ac ≡ bc (modn).
3) Si a ≡ b (modn), entonces ak ≡ bk (modn) para todo entero positivo k.
Demostración.
1) Si a ≡ b (modn) y c ≡ d (modn), entonces existen los números enteros c1 y c2
tales que:
a− b = c1n y c− d = c2n.
Sumando miembro a miembro las dos últimas igualdades, tenemos:
(a+ c)− (b+ d) = (c1 + c2)n
que nos permite concluir que a+ c ≡ b+ d (modm). Por otro lado,
ac− bd = (b+ c1n)(d+ c2n)− bd = (bc2 + dc1 + c1c2n)n,
por lo que ac ≡ bd (modn).
2) Por hipótesis a ≡ b (modn), y como además sabemos que c ≡ c (modn), por la
propiedad anterior, podemos concluir que:
a+ c ≡ b+ c (modn) y ac ≡ bc (modn).
3) Demostraremos por inducción matemática en k. Si k = 1 la proposición es verda-
dera por hipótesis. Ahora supongamos que ah ≡ bh (modn) es verdadera para un
entero positivo h. Como por hipótesis a ≡ b (modm), por la propiedad anterior 1),
tenemos que:
aha ≡ bhb (modn)
esto es,
ah+1 ≡ bh+1 (modn),
por lo que la proposición es verdadera para el entero positivo h+ 1. Luego, la proposi-
ción es verdadera para todo k.
Ejemplo 3.2. Veamos algunas aplicaciones de las propiedades del Teorema anterior.
(1) Si −12 ≡ 28 (mod 5) y 9 ≡ 34 (mod 5), entonces
−12 + 9 ≡ 28 + 34 (mod 5) es decir − 3 ≡ 62 (mod 5).
6
(2) 4 ≡ 17 (mod 13) entonces
4 + 8 ≡ 17 + 8 (mod 13) equivalentemente 12 ≡ 25 (mod 13)
y
4 · 3 ≡ 17 · 3 (mod 13) o sea 12 ≡ 51 (mod 13).
(3) −1 ≡ −4 (mod 3) implicaque
(−1)2 ≡ (−4)2 (mod 3) o sea 1 ≡ 16 (mod 3).
Proposición 3.4. Si a ≡ b (modn), entonces −a ≡ −b (modn).
Demostración. Por hipótesis a ≡ b (modn), como además −1 ≡ −1 (modn), por el
Teorema 3.3 tenemos que a(−1) ≡ b(−1) (modn), esto es,−a ≡ −b (modn).
Proposición 3.5. Si a+ b ≡ c (modn), entonces a ≡ c− b (modn).
Demostración. Por hipótesis a + b ≡ c (modn) como además −b ≡ −b (modn), por el
Teorema 3.3 tenemos que a+ b+ (−b) ≡ c+ (−b) (modn) es decir, a ≡ c− b (modn).
Teorema 3.6. Si ac ≡ bc (modn) y si mcd(c, n) = d, entonces a ≡ b
(
mod
n
d
)
.
Demostración. Si ac ≡ bc (modn), entonces existe k ∈ Z tal que:
ac− bc = (a− b)c = k n
Por otro lado, si mcd(c, n) = d, entonces existen enteros positivos r y s tales que c = dr
y n = ds, donde r y s son primos relativos. Por tanto (a−b)dr = kds o equivalentemente:
(a− b)r = ks.
De la última igualdad podemos deducir que s|(a − b)r, y como mdc(r, s) = 1, por el
Teorema de Euclides tenemos que s|(a − b). Luego, a ≡ b (mod s) y como s = n/d,
entonces a ≡ b
(
mod
n
d
)
.
A continuación se enuncian dos corolarios del Teorema 3.6, cuyas demostraciones se dejan
al estudiante.
Corolario 3.7. Si ac ≡ bc (modn) y mcd(c, n) = 1, entonces a ≡ b (modn).
Corolario 3.8. Si ac ≡ bc (mod p) siendo p un número primo que no divide a c, entonces
a ≡ b (mod p).
7
4. Sistema completo de restos módulo m
Definición 4.1. Un sistema completo de restos módulom es un conjunto S = {r1, r2, . . . , rm}
de m enteros tal que un entero cualquiera a es congruente módulo m a un único ele-
mento de S.
Ejemplo 4.1.
(1) Cada uno de los conjuntos
{1, 2}, {0, 1}, {−1, 0}, {17, 60}
es un sistema completo de restos módulo 2.
(2) Cada uno de los conjuntos
{1, 2, 3, 4}, {0, 1, 2, 3}, {−3,−2,−1, 0}, {−10, 61, 27, 440}
es un sistema completo de restos módulo 4.
Teorema 4.1. El conjunto S = {0, 1, 2, 3, . . . ,m − 1} es un sistema completo de restos
módulo m.
Demostración. Sea a un entero cualquiera y sean q y r el cociente y el resto de la
división de a por el entero positivo m, esto es:
a = mq + r, donde 0 ≤ r < m.
Entonces, por definición de enteros congruentes módulo m, tenemos:
a ≡ r(modm)
y como r solo puede tomar los valores 0, 1, 2, 3, . . . ,m − 1, de esta forma el entero a
es congruente módulo m a un único elemento del conjunto S, y por consiguiente este
conjunto es un sistema completo de restos módulo m.
Por ejemplo, el conjunto {0, 1, 2, 3, 4, 5, 6} es un sistema completo de restos módulo 7.
Corolario 4.2. Si S = {r1, r2, . . . , rm} es un sistema completo de restos módulo m,
entonces los elementos de S son congruentes módulo m a los números enteros
0, 1, 2, 3, . . . ,m− 1, tomados en cierto orden.
Demostración. Sea a un entero cualesquiera, entonces:
a ≡ ri(modm), con ri ∈ S
a ≡ k(modm), con 0 ≤ k < m.
Luego, por la propiedad transitiva de congruencia módulo m, tenemos que:
ri ≡ k(modm).
8
Por ejemplo, el conjunto
S = {−12,−4, 11, 13, 22, 93}
es un sistema completo de restos módulo 6, porque:
−12 ≡ 0(mod 6), −4 ≡ 2(mod 6), 11 ≡ 5(mod 6)
13 ≡ 1(mod 6), 22 ≡ 4(mod 6), 93 ≡ 3(mod 6).
esto es, los elementos de S son congruentes módulo 6 a los enteros 0, 2, 5, 1, 4, 3.
Ejemplo 4.2. Demostrar que el conjunto S = {−2,−1, 0, 1} es un sistema completo de
restos módulo 4.
Sabemos que cualquier entero a es congruente módulo 4 a un único elemento del
conjunto {0, 1, 2, 3}, esto es:
a ≡ k(mod 4), con 0 ≤ k < 4.
Por otro lado, los elementos de S son congruentes módulo 4 a los enteros 0, 1, 2, 3, tomados
en un cierto orden, porque:
−2 ≡ 2(mod 4), −1 ≡ 3(mod 4), 0 ≡ 0(mod 4)
1 ≡ 1(mod 4)
Luego, el entero a es congruente módulo 4 a un único elemento del conjunto S, lo cual
implica que este conjunto es un sistema completo de restos módulo 4.
5. Sistema reducido de restos módulo m
Definición 5.1. Un subconjunto R del conjunto de los números enteros se dice que es un
sistema reducido de restos módulo m si:
i) mcd(r,m) = 1 para cada r en R.
ii) ningún par de elementos de R son congruentes módulo m.
Por ejemplo, {1, 5} es un sistema reducido de restos módulo 6 ya que mcd(1, 6) = 1,
mcd(5, 6) = 1 y 5 6≡ 1(mod 6).
6. La función Φ de Euler
Esta función indica el número de elementos que posee un sistema reducido de restos módulo
m. El número Φ(m) es el número de enteros positivos menor que o iguales a m y que
son relativamente primo con m.
Nótese que Φ(1) = 1.
Teorema 6.1. Si p es un número primo, entonces Φ(p) = p− 1.
Demostración. Como p es un número primo, entonces todos los números enteros positivos
menores que p son primos relativos con p. Es decir, 1, 2, 3, . . . , p−1 son primos relativos
con p. Vemos que existen p− 1 de tales enteros, y como Φ(m) es el número de enteros
positivos menores que m y primos relativos con m, entonces Φ(p) = p− 1.
9
Teorema 6.2. Si p es primo y α es un entero positivo entonces Φ(pα) = pα − pα−1 o
bien Φ(pα) = pα
(
1− 1
p
)
.
Demostración. Los enteros p, 2p, 3p, . . . , pα−1p son todos los enteros positivos menores
o iguales a pα y que no son primos relativos relativos con pα. Existen pα−1 de tales
enteros, por lo que Φ(pα) = pα − pα−1 o bien Φ(pα) = pα
(
1− 1
p
)
.
Teorema 6.3. Si p es un número primo, entonces
α∑
i=0
Φ(pi) = pα.
Demostración. Sabemos que si p es un número primo, entonces:
Φ(p) = p− 1
Φ(p2) = p2 − p = p(p− 1)
Φ(p3) = p3 − p2 = p2(p− 1)
...
Φ(pα) = pα − pα−1 = pα−1(p− 1)
Entonces,
α∑
i=0
Φ(pi) = Φ(p) + Φ(p2) + Φ(p3) + . . .+ Φ(pα)
= (p− 1)(1 + p+ p2 + . . .+ pα−1) = (p− 1)p
α − 1
p− 1
= pα − 1
Usando el hecho de que
α−1∑
i=0
pi =
pα − 1
p− 1
Teorema 6.4. Sea m un número entero compuesto tal que m = pα11 · pα22 siendo p1 y
p2 números primos, entonces Φ(m) = m
(
1− 1
p1
)(
1− 1
p2
)
Demostración. Como m = pα11 · pα22 entonces los factores primos son p1 y p2. Los enteros
divisibles por p1 y por p2 no son primos relativos con m. Existen
m
p1
y
m
p2
enteros
menores o iguales a m que son divisibles por p1 y p2, respectivamente. Dichos enteros
son todos los que no son primos relativos con m. Entre los enteros divisibles por p1 y por
p2, existen
m
p1 · p2
enteros que son divisibles por p1 · p2. Tenemos entonces:
Φ(m) = m− m
p1
− m
p2
+
m
p1 · p2
Φ(m) = m
(
1− 1
p1
− 1
p2
+
1
p1 · p2
)
Φ(m) = m
(
1− 1
p1
)(
1− 1
p2
)
Se aceptarán sin demostración los siguientes teoremas.
Teorema 6.5. Si m y n son dos enteros positivos primos relativos, entonces Φ(m ·n) =
Φ(m) · Φ(n).
Teorema 6.6. Si n > 1 entonces Φ(n) = n
∏
p|n
(
1− 1
p
)
.
10
Ejemplo 6.1. Veamos los cálculos de la función Φ de Euler para algunos enteros positivos.
(1) Φ(67) = 67− 1 = 66
(2) Φ(64) = Φ(26) = 26
(
1− 1
2
)
= 26 · 1
2
= 25 = 32
(3) Φ(200) = Φ(23 · 52) = 200
(
1− 1
2
)(
1− 1
5
)
= 200 · 1
2
· 4
5
= 80
(4) Φ(1155) = Φ(3·5·7·11) = Φ(3)·Φ(5)·Φ(7)·Φ(11) = (3−1)·(5−1)·(7−1)·(11−1) = 480
8. Teorema de Fermat
Teorema 7.1 (Teorema de Fermat). Sea a un número entero y p un número primo tal
que p - a, entonces:
ap−1 ≡ 1(mod p).
Demostración. Consideremos los primeros p− 1 múltiplos de a:
a, 2a, 3a, . . . , (p− 1)a
Ningún entero de esta lista es divisible por p, y dos de ellos cualesquiera son incongruentes
módulo p, pues si:
ra ≡ sa(mod p), 1 ≤ r < s ≤ p− 1
entonces tendríamos r ≡ s(mod p) porque mcd(a, p) = 1. Lo cual es imposible ya que
0 < s− r < p.
Por lo tanto, cada uno de los enteros a, 2a, 3a, . . . , (p − 1)a es congruente módulo p
a uno de los enteros 1, 2, 3, . . . , p − 1 y solo a uno. Considerándolos en cierto orden, y
multiplicando ordenadamente todas esas p− 1 congruencias, tendremos:
a · 2a · 3a · · · (p− 1)a ≡ 1 · 2 · 3 · · · (p− 1)(mod p),
equivalentemente
ap−1 · (p− 1)! ≡ (p− 1)!(mod p).
Como p es primo y p - (p− 1)!, podemos cancelar (p− 1)! y queda lo que queríamos
probar, es decir,
ap−1 ≡ 1(mod p).
Corolario 7.2. Sea a un número entero y p un número primo, entonces:
ap ≡ a(mod p).
Demostración.
Si p - a y siendo p un número primo, entonces mcd(a, p) = 1, aplicando el teorema de
Fermat tenemos que: ap−1 ≡ 1(modp) y, por tanto ap−1 · a ≡ 1 ·a(mod p), esto es:
ap ≡ a(mod p).
Por otro lado, si p|a entonces a ≡ 0(mod p) y ap ≡ 0(mod p), en consecuencia:
ap ≡ a(mod p)
11
Ejemplo 7.1. Veamos algunos ejemplos sobre el teorema de Fermat.
(1) Verifique el teorema de Fermat con a = 2 y p = 5.
El número entero 5 es primo, y además 5 - 2. Ahora, tenemos que:
25−1 = 24 = 16
Como 5 | (16− 1), se tiene que 16 ≡ 1(mod 5), por lo tanto:
25−1 ≡ 1(mod 5)
(2) Verifique el teorema de Fermat con a = 5 y p = 19.
El número entero 19 es primo, y además 19 - 5. Ahora, tenemos que:
519−1 = 518
que es un número muy grande. Veamos una manera de comprobar el teorema de Fermat
sin calcular dicho número.
Por un lado tenemos que
52 = 25 ≡ 6(mod 19)
lo que implica lo siguiente:
54 ≡ 36 ≡ −2(mod 19)⇒ 58 ≡ 4(mod 19)⇒ 516 ≡ 16 ≡ −3(mod 19)
Luego
519−1 = 518 = 516 · 52 ≡ (−3) · 6(mod 19) ≡ −18(mod 19) ≡ 1(mod 19)
Es decir,
519−1 ≡ 1(mod 19)
7. Generalización de Euler
Teorema 8.1 (Teorema de Generalización de Euler del teorema de Fermat). Sea a un
entero cualquiera y m un entero positivo tal que mcd(a,m) = 1. Sea {r1, r2, . . . , rn} un
sistema completo, o bien, reducido, de residuos módulo m. Entonces {ar1, ar2, . . . , arn}
es un sistema completo, o bien, reducido, respectivamente, de residuos módulo m.
La demostración del Teorema anterior se deja como ejercicio al estudiante.
Teorema 8.2. Si mcd(a,m) = 1, entonces aΦ(m) ≡ 1(modm).
Demostración. Sea {r1, r2, . . . , rΦ(m)} un sistema reducido de restos módulo m. Sabemos
que {ar1, ar2, . . . , arΦ(m)} también es un sistema reducido de restos módulo m. De modo
que, para cada ari existe uno y solo un rj tal que
ari ≡ rj(modm).
Además, a distintos ari corresponden distintos rj . Esto implica que los enteros ar1, ar2, . . . , arΦ(m)
son los residuos módulo m de r1, r2, . . . , rΦ(m) pero no necesariamente en el mismo or-
den. Considerándolos en cierto orden, y multiplicando ordenadamente todas esas Φ(m)
congruencias, tendremos:
Φ(m)∏
i=1
(ari) ≡
Φ(m)∏
i=1
ri(modm)
12
de donde se puede deducir que:
aΦ(m)
Φ(m)∏
i=1
ri ≡
Φ(m)∏
i=1
ri(modm)
Ahora, mcd(ri,m) = 1 por lo que se puede cancelar los ri y así obtener:
aΦ(m) ≡ 1(modm).
13
9. Congruencias lineales
Definición 9.1. Toda ecuación de la forma ax ≡ b(modm) se denomina congruencia
lineal. Todo número entero x0 que satisfaga la congruencia ax ≡ b(modm), es decir,
x0 es un entero tal que ax0 ≡ b(modm), es una solución de la congruencia lineal dada.
9.1. Soluciones de una congruencia lineal y ecuaciones diofánticas
El número entero x0 es tal que ax0 ≡ b(modm) si m | (ax0− b). Esto último se cumple
si y solo si existe y0 tal que ax0 − b = my0. Por lo tanto hallar todas las soluciones de
una congruencia lineal ax ≡ b(modm) equivale a obtener las soluciones de la ecuación
diofántica lineal ax−my = b.
Ejemplo 9.1.
La congruencia 2x ≡ 3(mod 5) implica que 5|2x− 3 esto quiere decir que existe y ∈ Z
tal que 2x− 3 = 5y o equivalentemente 2x− 5y = 3 que es una ecuación diofántica.
Si x0 es una solución de la ecuación diofántica lineal ax ≡ b(modm), se puede verificar
fácilmente que también son soluciones todos los enteros del siguiente conjunto:
{. . . , x0 − 2m,x0 −m,x0, x0 +m,x0 + 2m, . . .}.
Observemos que los elementos de este conjunto son congruentes módulo m, es decir,
pertencen a la misma clase residual módulo m. Dos o más soluciones que pertenezcan a
una misma clase residual, no se consideran soluciones distintas y se denominan soluciones
congruentes módulo m. Así también, dos o más soluciones que pertenezcan a clases
residuales distintas se denominan soluciones incongruentes.
Teorema 9.1. La congruencia lineal ax ≡ b(modm) tiene solución si y solo si d|b siendo
d = mcd(a,m).
Demostración.
(⇒) Supongamos que la congruencia lineal ax ≡ b(modm) tiene solución, es decir, existe
x0 ∈ Z tal que ax0 ≡ b(modm), entonces m|(ax0 − b).
Como d = mcd(a,m) implica que d|a y d|m, de aquí sabemos que d|m y m|(ax0−b)
y de esta forma d|(ax0 − b). Por consiguiente d|a y d|(ax0 − b), lo que implica que
d|(ax0 + (−1)(ax0 − b)), esto es, d|b.
(⇐) Supongamos ahora que d|b, entonces existe q ∈ Z tal que b = dq, además como
d = mcd(a,m) existen x0, y0 ∈ Z tal que d = ax0 +my0.
Por lo tanto, dq = a(x0q) + m(y0q), lo cual implica que dq = a(x0q) −m(−y0q), siendo
q1 = −y0q un elemento de Z. Entonces, b = a(x0q)−m(q1) o bien a(x0q)− b = mq1,
esto implica que m|(a(x0q) − b). Como m|(a(x0q) − b), entonces a(x0q) ≡ b(modm) y
de esta manera x = x0q es solución de la congruencia lineal ax ≡ b(modm).
Teorema 9.2. Si d|b siendo d = mcd(a,m), entonces la congruencia lineal ax ≡
b(modm) tiene exactamente d soluciones incongruentes.
Demostración. Sabemos que la congruencia lineal ax ≡ b(modm) es equivalente a la
ecuación diofántica ax−my = b con y ∈ Z, esta ecuación tiene solución si d|b siendo
d = mcd(a,m).
14
Si d|b, sea x0, y0 una solución particular de la ecuación diofántica ax − my = b,
entonces todas las otras soluciones de esta ecuación están dadas por
x = x0 +
(m
d
)
t
y
y = y0 +
(a
d
)
t,
para t ∈ Z.
Entre el número infinito de enteros dados por la primera ecuación consideremos aquellas de
atribuir a t los valores 0, 1, 2, 3, . . . , d− 1, esto es, los d enteros
x0, x0 +
(m
d
)
, x0 + 2
(m
d
)
, . . . , x0 + (d− 1)
(m
d
)
Estos son mutuamente incongruentes módulo m. Supongamos lo contrario, esto es, su-
pongamos que dos de ellos son congruentes módulo m, es decir:
x0 +
(m
d
)
t1 ≡ x0 +
(m
d
)
t2(modm) donde 0 ≤ t1 < t2 < d
Entonces
m|
(
x0 +
(m
d
)
t2 − x0 −
(m
d
)
t1
)
m|
((m
d
)
(t2 − t1)
)
Como mcd
(
m, m
d
)
=
m
d
, podemos cancelar el factor
m
d
. Entonces
d|(t2 − t1)
lo cual es una contradicción por ser 0 < t2−t1 < d. Luego las soluciones son incongruentes
módulo m.
Además, consideremos cualquier solución de la forma x0 +
(m
d
)
t. Por el Algoritmo de la
división existen enteros q y r tales que:
t = dq + r, con 0 6 r 6 d− 1
y, por tanto:
x0 +
(m
d
)
t = x0 +
(m
d
)
(dq + r) = x0 +mq +
(m
d
)
r
Entonces:
x0 +
(m
d
)
t ≡ x0 +
(m
d
)
r(modm)
donde x0 +
(m
d
)
r es uno de los d enteros que fueron seleccionados.
Corolario 9.3. Si mcd(a,m) = 1, entonces la congruencia lineal ax ≡ b(modm) tiene una
única solución incongruente x = x1. Todas las soluciones están dadas por x = x1 + jm
siendo j = 0,±1,±2, . . .
Teorema 9.4. Si ac ≡ bc(modm) y mcd(c,m) = g, entonces a ≡ b
(
mod
m
g
)
.
Demostración. Como ac ≡ bc(modm) entonces m|(ac−bc) o bien m|(a−b)c y además
si mcd(c,m) = g, entonces mcd
(
c
g
,
m
g
)
= 1.
De aquí, si m|(a − b)c, implica que m
g
|(a − b) c
g
y como mcd
(
c
g
,
m
g
)
= 1, entonces
m
g
|(a− b) lo cual quiere decir que a ≡ b
(
mod
m
g
)
.
15
Veamos algunos ejemplos de aplicación
Ejemplo 9.2. Resuelve la congruencia lineal 64x ≡ 16(mod 84).
Como mcd(64, 84) = 4 y 4|16 entonces la congruencia lineal 64x ≡ 16(mod 84) tiene
4 soluciones incongruentes.
64x ≡ 16(mod 84)
es equivalente a
16x ≡ 4(mod 21)
4x ≡ 1(mod 21),
4x ≡ −20(mod 21),
x ≡ −5(mod 21),
x ≡ 16(mod 21).
De aquí, las soluciones incongruentes son x = 16, 37, 58, 79
{. . . ,−68, 16, 100, . . .}
{. . . ,−47, 37, 121, . . .}
{. . . ,−26, 58, 142, . . .}
{. . . ,−5, 79, 168, . . .}
Ejemplo 9.3. Resuelve la congruencia lineal 18x ≡ 30(mod 42).
Como mcd(18, 42) = 6 y 6|30 entonces la congruencia lineal 18x ≡ 30(mod 42) tiene 6
soluciones incongruentes.
18x ≡ 30(mod 42)
es equivalente a
3x ≡ 5(mod 7)
3x ≡ −9(mod 7),
x ≡ −3(mod 7),
x ≡ 4(mod 7).
De aquí, las soluciones incongruentes son x = 4, 11, 18, 25, 32, 39
{. . . ,−38, 4, 46, . . .}
{. . . ,−31, 11, 53, . . .}
{. . . ,−24, 18, 60, . . .}
{. . . ,−17, 25, 67, . . .}
{. . . ,−10, 32, 74, . . .}
{. . . ,−3, 39, 81, . . .}
Ejemplo 9.4. Resuelve la congruencia lineal 36x ≡ 53(mod 131).
Como mcd(36, 131) = 1 y 1|53, entonces la congruencia lineal 36x ≡ 53(mod 131) tiene
1 solución incongruente.
36x ≡ 53(mod 131)
es equivalente a
36x ≡ −864(mod 7)
x ≡ −24(mod 131),
x ≡ 107(mod 131).
De aquí, la solución incongruente son x = 107
{. . . ,−24, 107,238, . . .}.
16
Observación 9.1. Si mcd(a,m) = 1 entonces por teorema de Euler tenemos que aΦ(m) ≡
1(modm) y como b ≡ b(modm) entonces aΦ(m)b ≡ b(modm) o bien aaΦ(m)−1b ≡
b(modm), entonces una solución de la congruencia lineal ax ≡ b(modm) es x1 =
aΦ(m)−1b.
Ejemplo 9.5. Resolver la congruencia lineal 2x ≡ 1(mod 17).
Como mcd(2, 17) = 1 entonces la congruencia lineal 2x ≡ 1(mod 17) tiene única solución
incongruente que está dada por:
x1 = a
Φ(m)−1b = 2Φ(17)−1 × 1 = 215 = 32768
que pertenece a la clase residual de x1 = 9, entonces por el Corolario 9.3 todas las
soluciones están dadas por x = 9 + 17j con j = 0,±1,±2, . . ..
9.2. Teorema Chino del resto
Teorema 9.5. Suponga que m1,m2, . . . ,mr denotan r enteros positivos, los cuales son
primos relativos en pares y suponga que a1, a2, . . . , ar denotan r enteros cualesquie-
ra. Entonces las congruencias x ≡ ai(modmi) para i = 1, 2, . . . , r tienen soluciones
comunes. Las soluciones comunes son congruentes módulo m1 ·m2 · . . . ·mr.
Demostración. Sea m = m1 ·m2 · · ·mr entonces mj|m para j = 1, 2, 3, . . . , r, además
mcd
(
m
mj
,mj
)
= 1.
Por lo tanto cada congruencia
m
mj
x ≡ 1(modmj) tiene una única solución (incongruente),
sean estas soluciones los enteros bj , es decir, se cumple que
m
mj
bj ≡ 1(modmj). Y como
aj ≡ aj(modmj), se tiene que:
m
mj
bjaj ≡ aj(modmj)
Además, es evidente que
m
mi
bi ≡ 0(modmj) si i 6= j. Por lo que para i 6= j, se tiene
que:
m
mi
biai ≡ 0(modmj)
De esta forma, para cada j = 1, 2, . . . , r se tiene que:
r∑
k=1
m
mk
bkak ≡ aj(modmj)
Entonces, x0 =
r∑
k=1
m
mk
bkak es una solución común de las congruencias.
Ahora, sean x0 y x1 dos soluciones comunes de las congruencias. Entonces para cada
i tenemos que:
x0 ≡ ai(modmi) y x1 ≡ ai(modmi)
Por lo que x0 ≡ x1(modmi) para i = 1, 2, . . . , r. Como mcd(mi,mj) = 1, entonces
x0 − x1 ≡ 0(modm1 ·m2 · . . . ·mr) o bien
x0 ≡ x1(modm).
17
Ejemplo 9.6. Resuelva el sistema de congruencias lineales:
x ≡ 2(mod 3)
x ≡ 3(mod 5)
x ≡ 2(mod 7)
Resolución: Como mcd(3, 5) = mcd(5, 7) = mcd(3, 7) = 1, por el Teorema Chino del
resto, el sistema tiene una única solución módulo m = 3 · 5 · 7 = 105. Calcularemos dicha
solución como en la demostración del mencionado Teorema.
Tenemos que:
a1 = 2, a2 = 3 y a3 = 2.
Además,
m1 = 3, m2 = 5 y m3 = 7.
Cálculo de b1:
m
m1
b1 ≡ 1(modm1) ⇔
105
3
b1 ≡ 1(mod 3) ⇔ 35b1 ≡ 1(mod 3) ⇔ 35b1 ≡ 70(mod 3) ⇔
b1 ≡ 2(mod 3)
Luego b1 = 2.
Cálculo de b2:
m
m2
b2 ≡ 1(modm2) ⇔
105
5
b2 ≡ 1(mod 5) ⇔ 21b2 ≡ 1(mod 5) ⇔ 21b2 ≡ 21(mod 5) ⇔
b2 ≡ 1(mod 5)
Luego b2 = 1.
Cálculo de b3:
m
m3
b3 ≡ 1(modm3) ⇔
105
7
b3 ≡ 1(mod 7) ⇔ 15b3 ≡ 1(mod 7) ⇔ 15b3 ≡ 15(mod 7) ⇔
b3 ≡ 1(mod 7)
Luego b3 = 1.
Por lo tanto, el número entero:
x0 =
3∑
k=1
m
mk
bkak =
m
m1
b1a1 +
m
m2
b2a2 +
m
m3
b3a3 =
105
3
· 2 · 2 + 105
5
· 1 · 3 + 105
7
· 1 · 2 = 233
es una solución común de las congruencias del sistema.
Como 233 ≡ 23(mod 105), entonces x1 ≡ 23(mod 105) es la única solución del sistema
dado.
Observación 9.2. El sistema del Ejemplo 9.6 es equivalente a hallar un número entero que
deja los restos 2, 3 y 2 cuando se divide por 3, 5 y 7, respectivamente.
9.3. Grado de una congruencia
Definición 9.2. Sea f(x) = a0xn + a1xn−1 + . . . + an. Si a0 6≡ 0(modm), el grado de la
congruencia f(x) ≡ 0(modm) es n. Si a0 ≡ 0(modm), sea j el menor entero positivo
tal que aj 6≡ 0(modm), entonces el grado de la congruencia es n − j. Si no existe tal
entero no se asigna grado a la congruencia.
Ejemplo 9.7. Sea g(x) = 6x3 + 3x2 + 1, determina el grado de las siguientes congruencias:
a) g(x) ≡ 0(mod 5)
a0 = 6 6≡ 0(mod 5) por lo que el grado de la congruencia es 3.
b) g(x) ≡ 0(mod 2)
a0 = 6 ≡ 0(mod 2) pero a1 = 3 6≡ 0(mod 2) por lo que el grado de la congruencia es 2.
18
10. Congruencias Cuadráticas
Definición 10.1. Una congruencia de la forma
ax2 + bx+ c ≡ 0(modm)
donde a 6≡ 0(modm) se denomina una congruencia cuadrática.
Estudiaremos los casos donde m es un número primo p.
Si p = 2 entonces la congruencia cuadrática ax2 + bx + c ≡ 0(mod p) es equivalente a una
de las siguientes congruencias:
x2 ≡ 0(mod 2)
x2 + 1 ≡ 0(mod 2)
x2 + x ≡ 0(mod 2)
x2 + x+ 1 ≡ 0(mod 2)
Las soluciones de estas cuatro congruencias se pueden hallar fácilmente por inspección.
Si p es un número primo impar y mcd(a, p) = 1, entonces mcd(4a2, p) = 1 y la congruencia
general con módulo primo p
ax2 + bx+ c ≡ (mod p) (1)
es equivalente a
4a2x2 + 4abx+ 4ac ≡ 0(mod p)
esto es
(2ax+ b)2 ≡ b2 − 4ac(mod p).
Sea X = 2ax+ b y d = b2 − 4ac, entonces
X2 ≡ d(mod p). (2)
Si la congruencia cuadrática (2) no tiene solución, entonces la ecuación (1) tampoco tiene
solución. Además, para cada solución incongruente módulo p de (2), existe una solución
incongruente de (1), es decir, hay una correspondencia uno a uno entre las soluciones de (2)
y de (1).
Aceptaremos sin demostración que una congruencia polinómica de grado n en una variable
con módulo primo tiene a lo más n soluciones incongruentes. Si la ecuación (2) tiene una
solución x0, entonces una segunda solución es p− x0 ya que
(p− x0)2 ≡ x20(mod p)
Ahora, no toda congruencia cuadrática de la forma (2) tiene solución, por ejemplo x2 ≡
3(mod 7) carece de soluciones.
Ejemplo 10.1. Resolver la ecuación cuadrática 3x2 − 4x+ 7 ≡ 0(mod 13).
La congruencia cuadrática 3x2 − 4x+ 7 ≡ 0(mod 13) es equivalente a:
9x2 − 12x+ 21 ≡ 0(mod 13),
(9x2 − 12x+ 4) + 17 ≡ 0(mod 13),
(3x− 2)2 + 17 ≡ 0(mod 13),
(3x− 2)2 ≡ 9(mod 13).
Ahora, hagamos X = 3x− 2. La congruencia cuadrática X2 ≡ 9(mod 13) lo resolvemos por
inspección. Como una solución es 3, la otra solución es 10, esto es,
X ≡ 3(mod 13) o X ≡ 10(mod 13),
3x− 2 ≡ 3(mod 13) o 3x− 2 ≡ 10(mod 13),
x ≡ 6(mod 13) o x ≡ 4(mod 13).
19
10.1. Teorema de Wilson
Teorema 10.1. Si p es un número primo entonces (p− 1)! ≡ −1(mod p)
Demostración. Si p = 2 0 p = 3 la congruencia se verifica fácilmente.
Supongamos que p ≥ 5 y consideremos los enteros cuyo producto es (p− 1)!.
Dado un entero j que satisfaga 1 ≤ j ≤ p − 1, entonces mcd(j, p) = 1, de aquí, existe un
entero i tal que j · i ≡ 1(mod p) con 0 ≤ i ≤ p − 1, para i = 0 es imposible de modo que
1 ≤ i ≤ p− 1.
Asociemos a cada entero j, el entero i correspondiente. Dado que j · i ≡ 1(mod p) esto
significa que j es el entero asociado con i.
El entero 1 se asocia consigo mismo así como (p− 1).
Consideremos ahora los valores 2 ≤ j ≤ p− 2 para estos valores mcd(j − 1, p) = mcd(j +
1, p) = 1 de donde j2 − 1 6≡ 0(mod p) lo cual implica que j2 6≡ 1(mod p).
Por lo tanto cada uno de los valores de j se asocia con un valor i diferente, es decir, i 6= j,
2 ≤ j ≤ p− 2, el asociado de i es j.
Así que los enteros 2, 3, 4, . . . , p − 2 pueden asociarse y la j asociada a la i, multiplicando
estos pares tenemos que
2 · 3 · ·(p− 2) ≡ 1(mod p).
Como 1 ≡ 1(mod p) y (p− 1) ≡ −1(mod p) tenemos que
1 · 2 · 3 · ·(p− 2) · (p− 1) ≡ −1(mod p)
Es decir
(p− 1)! ≡ −1(mod p).
A continuación vamos a estudiar la congruencia cuadrática particular
x2 ≡ −1(mod p)
donde p es primo. El siguiente teorema establece una condición necesaria y suficiente para
la existencia de una solución de x2 ≡ −1(mod p), de hecho es una consecuencia interesante
del teorema de Wilson.
Teorema 10.2. Si p es un número primo, entonces x2 ≡ −1(mod p) tiene una solución si y
solo si p = 2 o p = 4t+ 1, donde t es un entero positivo.
Demostración. Sea p un número primo. Si p = 2, entonces 12 ≡ −1(mod 2), esto es, 1 es
la solución de la congruencia cuadrática x2 ≡ −1(mod p), si p = 2. Si p 6= 2, entonces p es
impar. Por el teorema de Wilson,
(p− 1)! ≡ −1(mod p)
(p− 1)(p− 2)(p− 3) · · · (p− k) · · ·
(
p+ 1
2
)(
p− 1
2
)
· · · 3 · 2 · · · 1 ≡ −1(mod p)
O bién
[1(p− 1)] · [2(p− 2)] · [3(p− 3)] · · · [k(p− k)] · · ·
[(
p+ 1
2
)(
p− 1
2
)]
≡ −1(mod p)
Como k(p− k) ≡ −k2(mod p), la última congruencia puede ser expresada en la forma:
(−1)(−4)(−9) · · · (−k2) · · ·
[
−
(
p− 1
2
)2]
≡ −1(mod p)
(−1)
p−1
2
[
1 · 4 · 9 · · · k2 · · ·
(
p− 1
2
)2]
≡ −1(mod p)
20
(−1)
p−1
2
[
1 · 2 ·· · · k · · ·
(
p− 1
2
)]2
≡ −1(mod p)
Si p = 4t+ 1, donde t es un entero positivo, entonces (−1) p−12 = 1. Por lo tanto,[(
p− 1
2
)
!
]2
≡ −1(mod p)
esto es,
(
p− 1
2
)
! es una solución de la congruencia cuadrática x2 ≡ −1(mod p) si p =
4t+ 1, donde t es un entero positivo.
Recíprocamente, si p 6= 2 y p 6= 4t+1, donde t es un entero positivo, entonces (−1) p−12 = −1.
Supongamos, que existe un entero a tal que
a2 ≡ −1(mod p).
Entonces mcd(a2, p) = mcd(a, p) = 1 y por el teorema de Fermat,
ap−1 ≡ 1(mod p)
a
2(p−1)
2 ≡ 1(mod p)
(a2)
p−1
2 ≡ 1(mod p)
((−1))
p−1
2 ≡ 1(mod p)
−1 ≡ 1(mod p)
sin embargo, la última congruencia es verdadera sólo si p = 2, lo que contradice la hipótesis
hecha. De aquí la suposición de que existe un entero a tal que a2 ≡ −1(mod p) es falsa.
Así, p es un número primo, entonces x2 ≡ −1(mod p) tiene una solución si y solo si p = 2 o
p = 4t+ 1, donde t es un entero positivo.
Ejemplo 10.2. Encontrar una solución, si existe, de la congruencia cuadrática x2 ≡ −1(mod 29).
Como 29 = 4× 7 + 1 puede ser expresado en la forma 4t+ 1, donde t es un entero positivo,
entonces por el teorema anterior existe una solución de la congruencia cuadrática x2 ≡
−1(mod 29). De hecho
(
p− 1
2
)
! representa una solución, esto es, 14!.
10.2. Criterio de Euler
Aceptaremos el siguiente Teorema sin demostración.
Teorema 10.3. Si p es un número primo impar y a 6≡ 0(mod p) entonces la congruencia
cuadrática x2 ≡ a(mod p) tiene una solución si y solo si a
p−1
2 ≡ 1(mod p).
Ejemplo 10.3. La congruencia cuadrática x2 ≡ 4(mod 13) es de la forma x2 ≡ a(mod p),
donde p es un número primo impar. Ahora bien, 4
13−1
2 = 46 = 4096 y 13|(4096− 1), esto es;
a
p−1
2 ≡ 1(mod p). De aquí la congruencia x2 ≡ 4(mod 13) tiene solución.
Ejemplo 10.4. La congruencia cuadrática x2 ≡ 2(mod 11) es de la forma x2 ≡ a(mod p),
donde p es un número primo impar. Ahora bien, 2
11−1
2 = 25 = 32 y 11 - (32 − 1). De aquí la
congruencia x2 ≡ 2(mod 11) no tiene solución.
21
Bibliografía
[1] Zuckerman, H. & Niven, I. (1976). Introducción a la Teoría de los Números. México:
Limusa.
[2] de Alencar Filho, E. (1981). Teoria elementar dos números. Sao Paulo: Nobel.
[3] Pettofrezzo, A. (1986). Introducción a la teoría de números. México: Prentice Hall.
22