Congruencias y clases de restos
Clase n. 2
Sitio web con el Magma Calculator:
[Link]
1 / 12
Congruencias y clases de restos
Relaciones de equivalencia
Definición 2.1. Dado un conjunto S, una relación de equivalen-
cia en S es un subconjunto R ⊂ S × S que tiene las siguientes
propiedades:
1. (x, x) ∈ R para cada x ∈ S;
2. si (x, y) ∈ R, luego (y, x) ∈ R;
3. si (x, y) ∈ R y (y, z) ∈ R, luego (x, z) ∈ R.
Escribiremos x ∼ y si (x, y) ∈ R. En este caso diremos que x es
R-equivalente, o semplicemente equivalente a y.
2 / 12
Congruencias y clases de restos
Relaciones de equivalencia
Definición 2.2. Dada una relación de equivalencia R en un con-
junto S y un elemento x ∈ S, su clase de equivalencia es:
[x]R = {y ∈ S : y ∼ x}.
A veces denotaremos [x]R semplicemente con [x].
3 / 12
Congruencias y clases de restos
Congruencias
Definición 2.3. Sea n un entero positivo. Consideramos la relación
de equivalencia en Z definida por
a ∼ b ⇐⇒ n | (a − b).
Ocuparemos la siguiente notación para decir que a es equivalente
con b
a ≡ b (mód n)
y diremos que a es congruente a b módulo n.
4 / 12
Congruencias y clases de restos
Clases de resto
Denotamos la clase de equivalencia de un entero a módulo n con
[a]n .
Proposición 2.4. Las clases de equivalencia de la congruencia
módulo n son [0]n , [1]n , . . . , [n − 1]n .
Denotaremos el conjunto de las clases de equivalencia con
Z/nZ := {[0]n , [1]n , . . . , [n − 1]n }.
5 / 12
Congruencias y clases de restos
Clases de restos
Ejemplo 2.5. Las siguientes son ciertas.
I [0]2 = numeros pares, [1]2 = numeros impares.
I · · · = [−3]3 = [0]3 = [3]3 = [6]3 = · · · .
I · · · = [−2]3 = [1]3 = [4]3 = [7]3 = · · · .
I · · · = [−1]3 = [2]3 = [5]3 = [8]3 = · · · .
I Z/3Z = {[0]3 , [1]3 , [2]3 }.
6 / 12
Congruencias y clases de restos
Clases de restos
Definición 2.6. Definimos la suma y el producto de dos clases [a]n ,
[b]n de la forma siguiente:
[a]n + [b]n := [a + b]n [a]n · [b]n := [ab]n .
7 / 12
Congruencias y clases de restos
Clases de restos
Teorema 2.7. La suma y el producto de clases de restos están bien
definidas.
Dem. Sean a0 ∈ [a]n y b0 ∈ [b]n . Tenemos que mostrar que a0 + b0
pertenece a [a+b]n y a0 b0 pertenece a [ab]n . Por definición existen
dos enteros p, q tales que a0 = pn + a, b0 = qn + b. Entonces las
siguientes son ciertas:
a0 + b0 = (q + p)n + a + b ∈ [a + b]n
0 0
a b = (qpn + pb + qa)n + ab ∈ [ab]n .
8 / 12
Congruencias y clases de restos
Clases de restos
Aplicación 2.8. Probamos el criterio de divisibilidad por 3: un
número entero positivo se divide por 3 si y sólo si la suma de sus
cifras se divide por 3.
Observamos que para cada número entero i ≥ 0 se cumple
10i ≡ 1 (mód 3).
Entonces si escribimosPun número entero positivo r como su ex-
n i
pansión decimal r = i=0 ai 10 con 0 ≤ ai ≤ 9 para cada i,
luego
Xn X n
r= ai 10i ≡ ai (mód 3).
i=0 i=0
Pn
En particular r ≡ 0 (mód 3) si y sólo si i=0 ai ≡ 0 (mód 3).
9 / 12
Congruencias y clases de restos
Clases de restos
Ejemplo 2.9. Para encontrar el resto de la división de 5322 por 3
razonamos de la manera siguiente:
5322 ≡ 5 · 1000 + 3 · 100 + 2 · 10 + 2 (mód 3)
≡5+3+2+2 (mód 3)
≡ 12 (mód 3)
≡0 (mód 3).
10 / 12
Congruencias y clases de restos
Clases de restos
Teorema 2.10. Una clase [a]n tiene inverso multiplicativo si y sólo
si Mcd(a, n) = 1.
Dem. Si Mcd(a, n) = d > 1 luego a = dp y n = dq con p, q
enteros. Luego
[a]n · [q]n = [aq]n = [dpq]n = [pn]n = [0]n .
Si el producto de dos clases no nulas es la clase nula, como en
la ecuación anterior, luego ninguna de las dos clases puede tener
inverso multiplicativo. En caso contrario, si por ejemplo existiera
[b]n tal que [a]n · [b]n = [1]n entonces
[0]n = [b]n · [a]n · [q]n = [q]n
nos darı́a una contradicción.
11 / 12
Congruencias y clases de restos
Clases de restos
Supongamos ahora que Mcd(a, n) = 1. Por la Proposición 1.3
existen dos enteros x, y tales que ax + ny = 1. Entonces
[a]n · [x]n = [1]n ,
ası́ que el inverso multiplicativo de [a]n es [x]n .
12 / 12