Aritmética Modular

MATEMÁTICA DISCRETA I

F. Informática. UPM

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 1 / 30

 Congruencias en Z módulo m La relación de congruencia

La relación de congruencia
Definición
Dado m ∈ Z, m ≥ 1, diremos que a, b ∈ Z son congruentes módulo m si y
solo si m|(a − b). Se denota a ≡ b (mod m). Llamaremos a m módulo de
la congruencia.

Proposición
La relación de congruencia módulo m es una relación de equivalencia, para
todo m ∈ Z.

Definición
Llamaremos Zm al conjunto cociente de Z respecto a la relación de
congruencia módulo m. A la clase de a ∈ Z se le denota por [a]m , am
o simplemente a.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 2 / 30

 Congruencias en Z módulo m La relación de congruencia

La relación de congruencia
Teorema
Sea m ∈ N, entonces
1 a ≡ b (mod m) ⇔ el resto al dividir a entre m coincide con el resto al
dividir b entre m,
2 para todo a ∈ Z existe r ∈ {0, 1, . . . , m − 1} tal que a ≡ r (mod m).

Observación
Por el teorema anterior Zm = {[0]m , [1]m , . . . , [m − 1]m }, donde

[i]m = {a ∈ Z | a ≡ i (mod m)} = {i + zm | z ∈ Z}.

Denoteremos, por simplicidad, Zm = {0, 1, . . . , m − 1} y le llamaremos

conjunto de menores residuos no negativos.

Ejemplo
El menor residuo no negativo de 23 en módulo 7 es 2 y el de −48 es 1.
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 3 / 30
 Congruencias en Z módulo m Compatibilidad de la suma y producto en Z

Compatibilidad de la suma y producto en Z

Las operaciones de suma y producto en Z se pueden trasladar a Zm puesto
que son compatibles con la estructura de este último conjunto.
Teorema
Sean n ∈ N y a, b, c, d ∈ Z tales que a ≡ b (mod m) y c ≡ d (mod m).
Entonces
i) a + c ≡ b + d (mod m),
ii) ac ≡ bd (mod m).

Dem.
Supongamos que a ≡ b (mod m) y c ≡ d (mod m). Entonces a = b +k1 m
y c = d +k2 m con k1 , k2 ∈ Z y por tanto (a +c) = (b +d)+(k1 +k2 )m con
k1 + k2 ∈ Z y ac = bd + (bk2 + ck1 + k1 k2 )m con bk2 + ck1 + k1 k2 ∈ Z.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 4 / 30

 Congruencias en Z módulo m Compatibilidad de la suma y producto en Z

Compatibilidad de la suma y producto en Z

Ejercicio
Construir las tablas de la suma y el producto en Z5 y Z6 .

Ejemplo
Como 1234567 · 90213 ≡ 7 · 3 (mod 10) y 21 ≡ 1 (mod 10) se tiene que
1234567 · 90213 = 1 en Z10 .

Ejemplo
El resto al dividir 6123 entre 5 es igual al resto al dividir 1123 entre 5, que
es 1. El resto al dividir 7123 entre 5 es igual al resto al dividir 2123 entre 5,
que no es inmediato. Pero observamos que 24 ≡ 1 (mod 5) y por tanto

2123 = 24·30+3 = (24 )30 · 23 ≡ 23 ≡ 3 (mod 5).

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 5 / 30

 Congruencias en Z módulo m Criterios de divisibilidad y regla del producto

Criterios de divisibilidad y regla del producto

Teorema (Criterios de divisibilidad)
Sea n = (ap . . . a0 )10 ∈ N en base 10. Entonces n = ap 10p + ap−1 10p−1 +
ap−2 10p−2 + · · · + a2 102 + a1 10 + a0 y por tanto,
i) n ≡ a0 (mod 2), luego n es divisible por 2 ⇔ a0 lo es,
p
Pp X
ii) n ≡ i=0 ai (mod 3), luego n es divisible por 3 ⇔ ai lo es,
i=1
iii) n ≡ 10a1 +a0 ≡ 2a1 +a0 (mod 4), luego n es divisible por 4 ⇔ (a1 a0 )10
lo es,
iv) n ≡ a0 (mod 5), luego n es divisible por 5 ⇔ a0 lo es,
p
v) n ≡ pi=0 ai (mod 9), luego n es divisible por 9 ⇔
P X
ai lo es,
i=1
p
Pp X
vi) n ≡ i
i=0 (−1) ai (mod 11), luego n es divisible por 11 ⇔ (−1)i ai
i=1
lo es.
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 6 / 30
 Congruencias en Z módulo m Criterios de divisibilidad y regla del producto

Prueba del 9 para la multiplicación

Teorema
Sean x, y , z ∈ N. Entonces xy = z ⇒ θ(x)θ(y ) ≡ θ(z) (mod 9), donde
θ((ap . . . a0 )10 ) = ap + ap−1 + · · · + a1 + a0 .

Ejemplo
Como θ(12)θ(12) = 9 6≡ θ(145) (mod 9) se tiene que 12 · 12 6= 145.
Por otra parte, como θ(12)θ(12) = 9 ≡ θ(144) (mod 9) es posible que
12·12 6= 144 aunque en principio no tiene porque ser ası́ puesto que también
se tiene que θ(12)θ(12) = 9 ≡ θ(135) (mod 9).

Observación
La prueba del 9 también se puede utilizar para la recuperación de datos
perdidos. Por ejemplo, si 53928719937 · 376648 = 20312144X 06831176,
entonces θ(53928719937) ≡ 0 (mod 9), θ(376648) ≡ 7 (mod 9) y
θ(20312144X 06831176) = 49 + X ≡ 4 + X (mod 9). Por tanto 0 ≡ 4 + X
(mod 9) y como 0 ≤ X ≤ 9 ha de ser X = 5.
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 7 / 30
 Congruencias en Z módulo m Aritmética en Zn

Aritmética en Zn
Definición
En Zm podemos definir dos operaciones binarias internas + y · dadas por
a + b = a + b, ab = ab.

Propiedades
En (Zm , +, ·) se verifican las siguientes propiedades:
i) a + (b + c) = (a + b) + c, a(bc) = (ab)c para cualesquiera a, b, c ∈ Z
(asociativa),
ii) a + b = b + a, ab = ba, para cualesquiera a, b ∈ Z (conmutativa),
iii) a + 0 = a, a1 = a, para todo a ∈ Z (existencia de elemento neutro),
iv) para todo a ∈ Z existe −a ∈ Zm tal que a + −a = 0 (existencia de
elemento opuesto),
v) a(b + c) = ab + ac, para cualesquiera a, b, c ∈ Z (distributiva).

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 8 / 30

 Congruencias en Z módulo m Aritmética en Zn

Aritmética en Zn
En general no se cumple la propiedad cancelativa, por ejemplo [2]6 + [1]6 =
[2]6 + [4]6 pero [1]6 6= [4]6 .
Proposición
m
Si ac ≡ bc (mod m) ⇒ a ≡ b (mod ) o lo que es equivalente,
mcd(m, c)
si ac = bc en Zm ⇒ a = b en Z mcd(m,c)
m .

Corolario
Zm tiene la propiedad cancelativa para el producto si m es primo.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 9 / 30

 Congruencias en Z módulo m Unidades en Zm

Unidades en Zm
Definición
Diremos que a ∈ Zm es invertible en Zm si existe b ∈ Zm tal que ab = 1
en Zm .

Proposición
a es invertible en Zm ⇔ existe b ∈ Zm tal que ab = 1 en Zm ⇔ existen
b, k ∈ Z tales que ab + km = 1 ⇔ mcd(a, m) = 1 (en cuyo caso se puede
calcular el inverso por el algoritmo de Euclides).

Definición
Si a ∈ Zm es invertible en Zm y ab = 1 en Zm diremos que b es el inverso
de a módulo m y lo denotamos por b = a−1 (por la propiedad anterior es
fácil ver el inverso de un elemento en módulo m es único).

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 10 / 30

 Congruencias en Z módulo m Unidades en Zm

Unidades en Zm
Definición
Denotaremos por Um al conjunto de elementos invertibles de Zm .

Proposición
Si p es primo entonces |Up | = p − 1.

Propiedades
En Zm se verifican las siguientes propiedades:
i) Si a, b ∈ Um entonces ab ∈ Um y a−1 ∈ Um .
ii) Si a ∈ Um entonces aUm = {ab | b ∈ Um } = Um .

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 11 / 30

 Congruencias en Z módulo m La función de Euler

La función de Euler
Definición
Se define la función φ de Euler como la función φ : N −→ N que a cada n le
hace corresponder el número de enteros x tales que 1 ≤ x ≤ n, mcd(x, n) =
1. Se tiene que φ(m) = |Um |. En particular

φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6, . . .

Propiedades
i) Si p es primo ⇒ φ(p r ) = p r − p r −1 .
ii) Si mcd(a, b) = 1 ⇒ φ(ab) = φ(a)φ(b).
    
r1 r2 rk 1 1 1
iii) Si n = p1 p2 · · · pk ⇒ φ(n) = n 1 − 1− ··· 1 − .
p1 p2 pn
X
iv) φ(d) = n.
d|n

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 12 / 30

 Congruencias en Z módulo m Teoremas de Euler y Fermat

Teoremas de Euler y Fermat

Teorema (Teorema de Euler)
Si a ∈ Um entonces aφ(m) = 1 en Zm . Por tanto, si b ∈ Z verifica que
mcd(b, m) = 1 entonces b φ(m) ≡ 1 (mod m).

Dem.
Supongamos que Um = {a1 , a2 , . . . , ar } (por tanto φ(m) = |Um | = r ).
Sea a ∈ Um . Entonces aUm = {aa1 , aa2 , . . . , aar } = Um y por tanto
a1 a2 · · · ar = (aa1 )(aa2 ) · · · (aar ) = ar a1 a2 · · · ar en Zm . Además, como
a1 a2 · · · ar es invertible, podemos multiplicar por su inverso y obtenemos
que ar ≡ 1 (mod m).
Por otra parte, si b ∈ Z existe r ∈ {0, 1, 2, . . . , p − 1} tal que b ≡ r
(mod p). Entonces mcd(p, r ) = mcd(b, p) = 1 y por tanto r ∈ Um . Por
tanto b φ(m) ≡ r φ(m) ≡ 1 (mod m).

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 13 / 30

 Congruencias en Z módulo m Teoremas de Euler y Fermat

Teoremas de Euler y Fermat

Teorema (Teorema de Fermat)
Si p es primo y p6 |a entonces ap−1 ≡ 1 (mod p).
En particular 2p−1 ≡ 1 (mod p) para todo número primo p. Sin embargo,
el recı́proco no es cierto (basta considerar 341 = 11 · 13 que verifica que
2340 ≡ 1 (mod p)).

Dem.
Si p es primo y p6 |a entonces mcd(a, p) = 1. Por otra parte, como p es
primo se tiene que φ(p) = p − 1. Por tanto ap−1 = aφ(p) ≡ 1 (mod p).

Ejercicio
Usar el teorema de Fermat para calcular el resto de dividir 347 entre 23.

Solución
Como 23 es primo y 236 |3 entonces 322 ≡ 1 (mod 23). Entonces
344 = 322 322 ≡ 1 (mod 23) y 347 = 344 33 ≡ 33 (mod 23) ≡ 4 (mod 23).
MATEMÁTICA DISCRETA I () 47Aritmética Modular F. Informática. UPM 14 / 30
 Congruencias en Z módulo m Ecuaciones de congruencias

Ecuaciones de congruencias
La ecuación de congruencias ax ≡ c (mod m) tiene solución en x si y solo
si existen x, y ∈ Z tales que ax = c + my , y esto es equivalente a que la
ecuación diofántica ax + my = c tenga solución. Este hecho justifica el
siguiente teorema.
Teorema
La ecuación de congruencias ax ≡ c (mod m) tiene solución en x si y solo
si d = mcd(a, m)|c en cuyo caso tiene exactamente d soluciones distintas
en Zm de la forma
mt
x = x1 + , t = 0, 1, 2, . . . , d − 1,
d
siendo x1 una solución particular de la ecuación diofántica ax + my = c.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 15 / 30

 Congruencias en Z módulo m Ecuaciones de congruencias

Ecuaciones de congruencias
Dem.
Por el teorema 2.4.10 y la observación anterior, las únicas soluciones
posibles son las de la forma x = x1 + mtd con t ∈ Z.
Vamos a ver primero que cualquier solución de éstas es congruente en
módulo m a una de las del enunciado. Por el teorema de la división se
tiene que t = qd + r con 0 ≤ r < d. Entonces mt rt
d = qm + d y por tanto
mt mr
x1 + ≡ x1 + (mod m).
d d
Veamos ahora que todas las soluciones del enunciado del teorema son
distintas. Supongamos que existen 0 ≤ t1 < t2 ≤ d − 1 tales que
x1 + mt mt2
d ≡ x1 + d (mod m). Entonces
1

 mt1   mt2 
x1 + − x1 + = qm.
d d
Luego m(t1 − t2 ) = qmd y por tanto t1 − t2 = qd y d|t1 − t2 con
0 ≤ t1 < t2 ≤ d − 1. Contradicción.
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 16 / 30
 Congruencias en Z módulo m Sistemas de congruencias

Sistemas de congruencias
Teorema (Teorema del resto chino)
El sistema de congruencias


 x ≡ c1 (mod m1 )
 x ≡ c2

(mod m2 )
..


 .
x ≡ cr (mod mr )


donde mcd(mi , mj ) = 1 para todo i 6= j, tiene solución única en Zm1 m2 ···mr .

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 17 / 30

 Congruencias en Z módulo m Sistemas de congruencias

Sistemas de congruencias
Dem.
hallar una solución del sistema consideramos, para i ∈ {1, 2, . . . , r },
Para Q
r
j=1 mj
ti = que cumplen mcd(mi , ti ) = 1. Entonces para todo
mi
i ∈ {1, 2, . . . , r } existe yi ∈ Z tal que ti yi ≡ 1 (mod mi ). Por otra parte,
como mj |ti para todo i 6= j se tiene que ti yi ≡ 0 (mod mj ). Entonces

ci ti yi ≡ ci (mod mi )
ci ti yj ≡ 0 (mod mj ) si j 6= i
X r
Sea x0 = ci ti yi . Entonces x0 es solución del sistema inicial.
i=1
Para hallar la solución general, observamos que si x1 es otra solución,
entonces x0 ≡ x1 (mod mi ) para todo i ∈ {1, 2, . . . , r } y por tanto
mi |x0 − x1 y, como mcd(mi , mj ) = 1 para todo i 6= j, entonces
m1 m2 · · · mr |x0 − x1 y por tanto x1 ≡ x0 (mod m1 m2 · · · mr ). Por tanto,
la solución general es x ≡ x0 (mod m1 m2 · · · mr ).
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 18 / 30
 Congruencias en Z módulo m Sistemas de congruencias

Sistemas de congruencias
Corolario
Sean x, y ∈ Z tales que

x ≡ y (mod m1 )
x ≡ y (mod m2 )
..
.
x ≡ y (mod mr )

donde mcd(mi , mj ) = 1 para todo i 6= j. Entonces x ≡ y

(mod m1 m2 · · · mr ).

Ejercicio
¿Qué entero al dividirlo por 2 da de resto 1 y al dividirlo por 3 da también
de resto 1?
Ejercicio
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 19 / 30
 Congruencias en Z módulo m Aritmética con números grandes

Aritmética con números grandes

Casi todos los procesadores trabajan mucho más rápido con números
pequeños que con números grandes. Este problema puede resolverse
utilizando congruencias. Para ello consideramos un conjunto
{m1 , m2 , . . . , mk } de números primos entre sı́ (esto es mcd(mi , mj ) = 1
para todo i 6= j). Entonces cualquier número positivo s menor que
m = m1 m2 · · · mk se puede expresar mediante una n-upla (r1 , r2 , . . . , rk )
(con 0 ≤ ri < mi para todo i ∈ {1, 2, . . . , k}) donde

 x ≡ r1 (mod m1 )

..
 .
x ≡ rk (mod mk )


Además, por el teorema del resto chino existe un único x ∈ {0, 1, 2, . . . , m}

satisfaciendo estas condiciones. Además, si
  0 0
 x ≡ r1 (mod m1 )
  x ≡ r1 (mod m1 )

.. y ..
. .
 0
x ≡ rk0 (mod mk )
 
x ≡ rk (mod mk )

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 20 / 30
 Congruencias en Z módulo m Aritmética con números grandes

Aritmética con números grandes

Por tanto, las operaciones aritméticas se pueden realizar entre las r -uplas
– cuyas coordenadas son todas menores o iguales que max1≤i≤r mi –,
pudiendose realizar estas operaciones en paralelo. Esto es, para sumar
n y n0 se suman los vectores asociados (r1 , r2 , . . . , rk ) y (r10 , r20 , . . . , rk0 ) y
para multiplicar n y n0 se multiplican escalarmente los vectores asociados.
Finalmente x + x 0 y xx 0 serán las soluciones (únicas en Zm ) de los sistemas
anteriores.
Por ejemplo se pueden considerar m1 = 99, m2 = 98, m3 = 97 y m4 =
95 para trabajar con números menores o iguales que m = m1 m2 m3 m4 =
89403930.
Otros enteros que pueden escogerse son los de la forma 2k − 1 con k ∈
N puesto que es relativamente fácil encontrar conjuntos de estos enteros
primos entre sı́ (mcd(2a − 1, 2b − 1) = 2mcd(a,b) − 1). Además con estos
enteros es fácil trabajar en base 2. Por ejemplo, 235 − 1, 234 − 1, 233 − 1,
231 − 1, 229 − 1 y 223 − 1 son primos entre sı́ y el producto de ellos es mayor
que 2184 .
MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 21 / 30
 Congruencias en Z módulo m Aritmética con números grandes

Aritmética con números grandes

Ejemplo
Si tomamos m1 = 3, m2 = 4 se tiene que

0 = (0, 0) 1 = (1, 1) 2 = (2, 2) 3 = (0, 3) 4 = (1, 0) 5 = (2, 1)

6 = (0, 2) 7 = (1, 3) 8 = (2, 0) 9 = (0, 1) 10 = (1, 2) 11 = (2, 3)

y 5 + 6 ≡ (2, 1) + (0, 2) = (2, 3) ≡ 11. Por otra parte y

2 · 3 ≡ (2, 2) · (0, 3) = (0, 6) ≡ (0, 2) ≡ 6. Sin embargo 5 · 6 no es
calculable, puesto que el resultado es mayor o igual que 12.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 22 / 30

 Congruencias en Z módulo m Criptografı́a

Criptografı́a
Una de las principales aplicaciones de las congruencias es la codificación
y decodificación de mensajes. La teorı́a de congruencias se utiliza de la
siguiente manera:
- A cada letra del alfabeto se le asigna el valor numérico (entre 01 y
27) de su posición.
- Se sustituye cada letra del mensaje por su correspondiente valor
numérico.
- El número resultante se cifra mediante una transformación numérica.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 23 / 30

 Congruencias en Z módulo m Criptografı́a

Criptografı́a
Código privado de César. Uno de los primeros métodos de codificación es
el llamado “Código privado de César”, utilizado por Julio César. Consta de
una sola clave para cifrar y descifrar que solo conocen el emisor y el receptor
de mensaje. Es por eso que estos métodos de codificación se conocen como
de clave privada. Para codificar el mensaje cifrado se toma una función
lineal del tipo f (x) = ax + b con mcd(a, 27) = 1 (César tomaba a = 1 y
b = 3) y se reemplaza cada par de cifras p del mensaje, empezando por la
derecha, por ap + b (mod 27).
Para decodificar el mensaje hay que calcular f −1 (q) = a−1 (q −b) (mod 27)
y por eso es necesario que mcd(a, 27) = 1.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 24 / 30

 Congruencias en Z módulo m Criptografı́a

Criptografı́a
Código Público. Existen otros métodos de codificación de “clave pública”.
Uno de ellos es el RSA, creado en 1976 en el M.I.T. Se diferencia del anterior
en que existen dos claves, una de cifrado que es pública y conocida por
cualquiera y una clave privada de descifrado. Está basado en exponenciación
modular módulo el producto de dos números primos grandes. La seguridad
de la codificación se basa en el hecho de que la factorización de números
grandes en sus factores primos (cuando estos factores son también grandes,
es practicamente imposible.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 25 / 30

 Congruencias en Z módulo m Criptografı́a

Criptografı́a
Para cifrar el mensaje consideramos dos números primos p y q
suficientemente grandes (de unas 200 cifras, por ejemplo) que serán
conocidos solamente por la persona que recibe el mensaje. Consideramos
n = pq y un exponente e primo con (p − 1)(q − 1). Ambos números podrán
ser conocidos por cualquiera. El mensaje M se codifica reemplazandolo por
C ≡ M e (mod n).
Para decodificar el mensaje, como mcd(e, (p−1)(q−1) = 1 existen d, k ∈ Z
tales que ed = 1 + k(p − 1)(q − 1). Entonces

C d = (M e )d = M ed = M 1+k(p−1)(q−1) = M(M p−1 )k(q−1) = M(M q−1 )k(p−1)

Pero en general se tendrá que mcd(M, p) = mcd(M, q) = 1 y, por el

Teorema de Fermat se tiene que M p−1 ≡ 1 (mod p) y M q−1 ≡ 1 (mod q).
Por tanto C d ≡ M (mod p) y C d ≡ M (mod q). Luego, por el Teorema
del resto chino, C d ≡ M (mod pq).

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 26 / 30

 Congruencias en Z módulo m Criptografı́a

Criptografı́a
El método del código público tiene la limitación de que el emisor de un
mensaje dado puede ser en principio cualquiera. Para que el emisor pueda
identificarse se utiliza el siguiente método. El emisor E del mensaje M
lo codifica primeramente usando su función de decodificación (privada) y
el mensaje resultante lo codifica nuevamente usando ahora la función de
codificación (pública) del futuro receptor R del mensaje. E envia el mensaje
final a R. Éste lo decodifica usando su función de decodificación (privada)
y el mensaje resultante lo codifica nuevamente usando ahora la función
de codificación (pública) de E . Si el mensaje resultante es un mensaje
comprensible, necesariamente habrá sido emitido por E . A todo este proceso
se le conoce como Firma Digital.

MATEMÁTICA DISCRETA I () Aritmética Modular F. Informática. UPM 27 / 30