adad

30

Cap´
ıtulo 3
Congruencias
3.1.

Clases residuales

En su obra Disquisitiones Arithmeticae, publicada en el a˜o 1801, Gauss inn
trodujo en las Matem´ticas el concepto de congruencia.
a
Supongamos que a, b y m > 0 son n´meros enteros. Diremos que a y b son
u
congruentes m´dulo m si m | a−b y designaremos esta situaci´n mediante el s´
o
o
ımbolo
a ≡ b (m´d m).
o
Lacongruencia es una relaci´n de equivalencia puesto que verifica las propiedades
o
reflexiva, sim´trica y transitiva. Por lo tanto podemos agrupar a los enteros en fae
milias disjuntas de manera que dos n´meros son congruentes m´dulo m si y s´lo si
u
o
o
est´n en la misma. Estas familias se denominan clases residuales m´dulo m, y se
a
o
designa por Zm al conjunto formado por ellas.
De la definici´nanterior se deducen inmediatamente las siguientes propiedades.
o
Proposici´n 3.1.1. Si a ≡ b
o
i) a + b ≡ c + d

(m´d m) y c ≡ d
o

(m´d m), entonces
o

(m´d m).
o

ii) ka ≡ kb

(m´d m) para todo entero k ∈ Z.
o

iii) ac ≡ bd

(m´d m).
o

iv) an ≡ bn

(m´d m)
o

v) f (a) ≡ f (b)

(m´d m) para todo polinomio f con coeficientes enteros.
o

Los enteros 0, 1, . . . ,m−1 est´n en clases residuales distintas. Como todo entero
a
n puede escribirse de manera unica de la forma n = mc+r con 0 ≤ r ≤ m−1, resulta
´
31

CAP´
ITULO 3. CONGRUENCIAS

32

que todo entero es congruente m´dulo m con uno de los enteros 0, 1, . . . , m − 1. En
o
particular existen exactamente m clases residuales m´dulo m y cualquier conjunto
o
de enteros incongruentes m´dulo mconstituyen un sistema residual completo.
o
El conjunto Zm , m ≥ 2, dotado de las operaciones suma y producto emanadas
de la proposici´n anterior es un anillo conmutativo cuyo elemento neutro aditivo,
o
clase 0, es 0 = (m) = mZ y cuya unidad multiplicativa es 1 + (m).
Proposici´n 3.1.2. Si {a1 , . . . , am } es un sistema residual completo y (k, m) = 1,
o
entonces el conjunto {ka1 , . . ., kam } tambi´n es un sistema residual completo.
e
Demostraci´n. Si kai ≡ kaj (m´d m) entonces m | k(ai − aj ). Pero al ser k y m
o
o
primos entre s´ m | (ai − aj ). Es decir, los kai son incongruentes entre s´ m´dulo m
ı,
ı o
y por lo tanto forman un sistema residual completo.
De una manera an´loga podemos definir un sistema residual reducido como
a
todo conjunto de φ(m) residuosincongruentes m´dulo m, cada uno de ellos primo
o
con m. De manera similar se demuestra la siguiente proposici´n.
o
Proposici´n 3.1.3. Si {a1 , . . . , aφ(m) } es un sistema residual reducido y (k, m) = 1,
o
entonces el conjunto {ka1 , . . . , kam } tambi´n es un sistema residual reducido.
e
Se designa por Z∗ al conjunto de las clases residuales primas con m. Es f´cil
a
m
ver que constituyenun grupo multiplicativo de orden φ(m).

3.2.

Congruencias lineales

En esta secci´n intentaremos resolver la ecuaci´n en congruencias m´s sencilla
o
o
a
de todas: la congruencia lineal.
Teorema 3.2.1. Si (a, m) = 1, la congruencia ax ≡ b
una soluci´n m´dulo m.
o
o

(m´d m) tiene exactamente
o

Demostraci´n. Por la proposici´n 3.1.2, el conjunto {a, 2a, . . . , ma} es unsistema
o
o
residual completo. En particular uno y s´lo uno de los residuos ser´ congruente con
o
a
b m´dulo m.
o
Lema 3.2.2. Si ac ≡ bc (m´d m) y d = (m, c), entonces a ≡ b
o

(m´d m/d).
o

Demostraci´n. Como m | c(b − a), entonces (m/d) | (c/d)(a − b). Pero como
o
(m/d, c/d) = 1, entonces (m/d) | a − b.

3.2. CONGRUENCIAS LINEALES

33

Teorema 3.2.3. Supongamos que (a, m) = d.Si d b la congruencia
ax ≡ b (m´d m)
o
no tiene soluciones, mientras que si d | b la congruencia tiene exactamente d soluciones m´dulo m que vienen dadas por
o
x1 , x1 + m1 , . . . , x1 + (d − 1)m1 ,
donde x1 es la soluci´n de la congruencia a1 x ≡ b1
o

b
(m´d m1 ) y a1 = a , b1 = d .
o
d

Demostraci´n. Si la congruencia tiene alguna soluci´n entonces, como d | a y d | b,
o
o...