casa

426 Ap´endice B. Complementos sobre aritm´etica
Teorema (Euclides) Hay infinitos numer ´ os primos.
Demostracion: ´
Dado cualquier numero ´ natural n, consideremos n!, es
decir, el producto detodos los numeros ´ menores o iguales que n. Sea p un
divisor primo de n!+1. Si fuera p ≤ n tendr´ıamos que p | n! y p | n!+1, luego
p | 1, lo cual es absurdo. Consecuentemente p > n. Hemos probadoque hay
primos arbitrariamente grandes, luego hay infinitos.
B.3 Congruencias
Diremos que dos numeros ´ naturales m y n son congruentes m´odulo un tercer
numero ´ d, y lo representaremos m ≡ n (m´odd) si su diferencia m −n o n− m
es multiplo ´ de d.
Se cumple:
a) m ≡ m (m´od d).
b) Si m ≡ n (m´od d), entonces n ≡ m (m´od d).
c) Si m ≡ n (m´od d) y n ≡ r (m´od d), entonces m ≡ r (m´od d).d) Dados m y d 6= 0, existe un unico ´ natural r < d tal que m ≡ r (m´od d).
Las pruebas de estos resultados se hallan (formalizadas en una teor´ıa aritm´etica arbitraria) en el cap´ıtulo VI.
N´oteseque dados m, n y d 6= 0, si m = dc+r y n = dc0
+r
0
con r, r
0
< d,
entonces se cumple que m ≡ r (m´od d) y n ≡ c
0
(m´od d), luego se tendr´a que
m ≡ n (m´od d) si y s´olo si r ≡ r
0(m´od d), pero, por la unicidad, esto es si y
s´olo si r = r
0
. Hemos probado, pues, que dos numeros ´ son congruentes m´odulo
d si y s´olo si el resto al dividirlos por d es el mismo.
Una ultima ´propiedad:
Si m ≡ m0
(m´od d) y n ≡ n
0
(m´od d), entonces
m+n ≡ m0
+n
0
(m´od d) y mn ≡ m0
n
0
(m´od d).
En efecto: Podemos suponer d 6= 0, o si no es evidente. Sea m = dc + r,
n = dc0+s, m0
= de+r, n
0
= de0
+s, con r, s < d. Veamos el caso del producto.
El de la suma es m´as simple. Tenemos que mn = d(cdc0
+cs+rc
0
)+rs, luego
mn ≡ rs (m´od d) e igualmente m0
n
0
≡ rs(m’do d), de donde concluimos que
Mn ≡ m0
N
0
(m´od d).
Vamos a probar un resultado cl´asico sobre congruencias, conocido como
teorema chino del resto. Para ello necesitamos un resultado...