Apuntes De Aritmetica Modular

Aritm´
etica Modular
Muchos de los problemas que involucran enteros muy grandes pueden simplificarse con aritm´
etica
modular, en la que se utilizan congruencia en vez de ecuaciones. La idea b´asica es elegir un determinado
entero n, llamado m´
odulo y sustituir cualquier entero por el resto de su divisi´on entre n. En general, los
restos son peque˜
nos y, por tanto, m´
as f´
acil de trabajar conellos.
Ejemplo 0.1. Si contamos 9378 d´ıas a partir de hoy (suponer que hoy es jueves), ¿en qu´e d´ıa de la
semana caer´
a? Podemos resolverlo tomando un calendario y comenzar a contar, pero esto resulta muy
tedioso. Si nos damos cuenta los d´ıas de la semana se repiten cada 7 d´ıas, as´ı nuestro n es 7. Por tanto
9378 = 1339 · 7 + 5, el resto resulta ser 5, es as´ı que en 9378 d´ıas m´as el d´ıaser´a Martes.
Definici´
on 0.1. Sea n un entero positivo y sean a y b dos enteros cualesquiera. Se dice que a es congruente
con b m´
odulo n y lo denotamos por:
a≡b

(m´od n)

Usaremos el algoritmo de la divisi´
on para expresar a = q · n + r con 0 ≤ r < n y b = q · n + r con
0 ≤ r < n, diremos que a ≡ b (m´
od n) si y s´olo si r = r . As´ı, 100 ≡ 2 (m´od 7) (100 = 14 · 7 + 2 ∧
2 = 0 · 7 + 2,ambos con resto 2).
Lema 0.1. Para cualquier entero dado n ≥ 1 se tiene que a ≡ b

(m´od n) si y s´olo si, n|(a − b)

Demostraci´
on. Sea n ∈ Z+ y sean a, b ∈ Z
(⇒) Si a ≡ b (m´
od n), entonces n|(a − b) Expresando a = q · n + r y b = q · n + r , tenemos que
a − b = (q − q ) · n + (r − r ) con −n < r − r < n. Si a ≡ b (m´od n) entonces r = r , por lo que
r − r = 0 y a − b = (q − q ) · n, por lo quees divisible por n
(⇐) Si n|(a−b), entonces a ≡ b (m´
od n) Si n divide a (a−b) entonces divide a (a−b)−(q−q )·n = r−r ,
como el u
´nico entero estrictamente contenido entre −n y n es 0, se tiene que r − r = 0, de donde
r = r y, por tanto, a ≡ b (m´
od n).

Lema 0.2. Para cualquier entero fijo n ≥ 1 se verifican las siguientes propiedades:
(a) Reflexiva: a ≡ a (m´
od n) para cualquier entero a.
(b)Sim´etrica: a ≡ b

(m´
od n) =⇒ b ≡ a (m´od n)

a ≡ b (m´
od n)
(c) Transitiva:
b ≡ c (m´
od n)

➟

⇒ a ≡ c (m´od n)

Demostraci´
on. Sea n ∈ Z+ y sean a, b ∈ Z.
(a) Se verifica que n|(a − a) para cualquiera sea a.
(b) Si n|(a − b) entonces n|(b − a).
(c) Si n|(a − b) y n|(b − c) entonces n|(a − b) + (b − c) = a − c.

Estas tres propiedades definen una relaci´on de equivalencia, por lo que ellema 0.2 prueba que, para
cada entero n la congruencia de m´
odulo n es una relaci´on de equivalencia en Z.
[a] = {a, b ∈ Z : a ≡ b (m´
od n))} = {...., a − 2n, a − n, a, a + n, a + 2n, ....}

Cada clase corresponde a uno de los n posibles restos r = 0, 1, ...., n − 1 de la divisi´on entre n, por lo
que existen n clases de congruencia. Estas son:
[0] =

{...., −2n, −n, 0, n, 2n, ....}

[1] =
..
.{...., 1 − 2n, 1 − n, 1, 1 + n, 1 + 2n, ....}

[n − 1]

= {...., n − 1 − 2n, n − 1 − n, n − 1, n + 1n, n − 1 + 2n, ....}

[n − 1]

= {...., −n − 1, −1, n − 1, 2n − 1, 3n − 1, ....}

No existen m´
as clases de equivalencias, as´ı, por ejemplo
[n] = {...., −2n, −n, 0, n, 2n, ....} = [0]
De forma m´
as general, se tiene que
[a] = [b] si y s´olo si a ≡ b

(m´od n)

Cuando n = 1 todos los enteros soncongruentes, y esta clase es todo Z, si n = 2 tenemos dos clases,
[0] y [1] ambas con modulo 2, as´ı tenemos los enteros pares e impares, respectivamente.
Para cada n ≥ 1, el conjunto de las n clases de congruencia de m´odulo n lo denotamos por Zn .
Si [a] y [b] son elementos de Zn (clases de congruencias m´odulo n) definimos la suma, diferencia y producto
como las clases:
[a] + [b]

= [a + b]

[a]− [b]

= [a − b]

[a][b]

= [ab]

que contienen a los enteros a + b, a − b y ab, respectivamente.
Lema 0.3. Para cualquier entero n ≥ 1, si a ≡ a (m´od n) y b ≡ b (m´od n), entonces
a + b ≡ a + b (m´
od n), a − b ≡ a − b (m´od n) y a b ≡ ab (m´od n)
Demostraci´
on. Si a ≡ a (m´
od n), entonces a = a + kn para alg´
un k ∈ Z y an´alogamente
b ≡ b (m´
od n), entonces b = b + ln para alg´
un l ∈ Z;...