Tn4

TEORíA DE NÚMEROS. HOJA 4.
CONGRUENCIAS

1. Definición. Sea n ∈ N. Dos enteros a y b se dicen congruentes módulo n si n divide a a − b,
es decir, si existe k ∈ Z tal que a − b = kn. En este caso denotaremos a ≡ b (mod n).
2. Probar que todo entero es congruente módulo n con uno y sólo uno de los números 0, 1, 2, ...,
n − 1.
3. Definición. Se dice que un conjunto de n enteros {a1 ..., an } es unsistema completo de
residuos módulo n si todo entero es congruente módulo n a exactamente uno de los ai . Por
ejemplo, {−12, −4, 11, 13, 22, 82, 91} es un sistema completo de residuos módulo 7. El conjunto
{0, 1, ..., n − 1} se dice que es el menor sistema de residuos positivos módulo n.
4. Proposición. a ≡ b (mod n) si y sólo si a y b dejan el mismo resto positivo al dividirlos
por n.
5.Proposición. Sean n ∈ N, a, b, c, d ∈ Z. Se tiene:
1.
2.
3.
4.
5.
6.

a ≡ a (mod n)
a ≡ b (mod n)
a ≡ b (mod n),
a ≡ b (mod n),
a ≡ b (mod n)
a ≡ b (mod n)

⇐⇒ b ≡ a (mod n)
b ≡ c (mod n) =⇒ a ≡ c (mod n)
c ≡ d (mod n) =⇒ a + c ≡ b + d (mod n), y ac ≡ bd (mod n)
=⇒ a + c ≡ b + c (mod n), y ac ≡ bc (mod n)
=⇒ ak ≡ bk (mod n) ∀k ∈ N.

Las tres primeras propiedades nos dicen que la relación a ≡ b (mod n) es deequivalencia en
Z. El conjunto cociente de Z por esta relación de equivalencia se suele denotar Zn . Las demás
propiedades implican que la suma y el producto en Z inducen al pasar al cociente una suma y
un producto en Zn que dotan a este conjunto de una estructura de anillo conmutativo con n
elementos. Además, puede verse que Zn es un cuerpo si y sólo si n es primo.
6. Probar que 41 divide a 220− 1.
7. Teorema. Si ca ≡ cb (mod n) entonces a ≡ b (mod n/d), donde d = mcd(c, n).
8. Corolario. Si ca ≡ cb (mod n) y mcd(c, n) = 1 entonces a ≡ b (mod n).
9. Corolario. Si ca ≡ cb (mod p), p es primo y no divide a c, entonces a ≡ b (mod p).
10. Probar que en general el producto de dos enteros no congruentes con cero puede ser congruente con cero. Sin embargo, si p es primo y ab ≡ 0, probar que obien a o b son congruentes
con 0 (mod p).
11. Probar lo siguiente:

1.
2.
3.
4.
5.

a ≡ b (mod n),
a ≡ b (mod n),
a ≡ b (mod n),
a ≡ b (mod n)
a ≡ 1 (mod n)

m | n =⇒ a ≡ b (mod m)
c > 0 =⇒ ca ≡ cb (mod cn)
0 < d | a, b, n =⇒ a/d ≡ b/d (mod n/d).
=⇒ mcd(a, n) = mcd(b, n).
⇐⇒ mcd(a, n) = 1.

12. Hallar los restos de la división por 7 de 250 y de 4165 .
13. Hallar el resto de la división por 4 de 15+ 25 + 35 + ... + 995 + 1005 .
14. Probar que 53103 + 10353 es divisible por 39, y que 111333 + 333111 es divisible por 7.
15. Si p es primo y n < p < 2n, probar que
2n
n

≡ 0 (modp).

16. Si a1 , ..., an es un sistema completo de residuos módulo n y mcd(a, n) = 1, probar que
aa1 , ..., aan es también un sistema completo de residuos módulo n.
17. Probar lo siguiente:
1. Si mcd(a, n) = 1 entonceslos enteros
c, c + a, c + 2a, ..., c + (n − 1)a
forman un sistema completo de residuos módulo n, para cualquier c.
2. Cualesquiera n enteros consecutivos forman un sistema completo de residuos módulo n.
3. El producto de n enteros consecutivos es divisible por n.
18. Probar que si n1 , n2 son primos entre sí y a ≡ b (mod ni ), i = 1, 2, entonces a ≡ b (mod
n1 n2 ).
19. Probar que si ab ≡ cd (mod n)y b ≡ d (mod n), con mcd(b, n) = 1 entonces a ≡ c (mod
n).
20. Sea b ∈ N, b ≥ 2. Probar que todo número N ∈ N puede escribirse de manera única en
base b, es decir, existen números únicos ak ∈ {0, 1, ..., b − 1}, k = 0, 1, ..., m, tales que
N = am bm + am−1 bm−1 + ... + a1 b + a0 .
21. Escribir 79 en base 2.
k
22. Sea P (x) = m
k=0 ck x un polinomio con coeficientes enteros ck . Probar que si a ≡b (mod
n) entonces P (a) ≡ P (b) (mod n).

23. Si a es solución de la ecuación P (x) ≡ 0 (mod n) y a ≡ b (mod n), entonces b también es
solución de dicha ecuación.
24. Proposición. Sea N = am 10m + am−1 10m−1 + ... + a1 10 + a0 la expansión decimal de
N ∈ N, y sea S = a0 + a1 + ... + am . Entonces 9 | N si y sólo si 9 | S.
Indicación: usar que 10 ≡ 1 (mod 9).

25. Proposición. Sea N = am 10m...