congruencia de modulo m

Apuntes de Matem´tica Discreta
a
13. Clases de Restos M´dulo m
o

Francisco Jos´ Gonz´lez Guti´rrez
e
a
e
C´diz, Octubre de 2004
a

Universidad de C´diz
a

Departamento de Matem´ticas
a

ii

Lecci´n 13
o

Clases de restos m´dulo m
o
Contenido
13.1 Conceptos B´sicos . . . . . . . . . . . . . . . .
a
13.1.1 Definici´n . . . . . . . . . . . . . . . . . . . .
o
13.1.2Teorema . . . . . . . . . . . . . . . . . . . . .
13.2 Propiedades . . . . . . . . . . . . . . . . . . . .
13.2.1 Teorema . . . . . . . . . . . . . . . . . . . . .
13.2.2 Teorema . . . . . . . . . . . . . . . . . . . . .
13.2.3 Corolario . . . . . . . . . . . . . . . . . . . .
13.3 Conjunto de las Clases de Restos M´dulo m
o
13.3.1 Relaci´n de Equivalencia . . . . . . . . . . .
o
13.3.2Clases de Equivalencia . . . . . . . . . . . . .
13.3.3 Conjunto Cociente . . . . . . . . . . . . . . .
13.4 Aritm´tica en Zm . . . . . . . . . . . . . . . .
e
13.4.1 Suma . . . . . . . . . . . . . . . . . . . . . .
13.4.2 Bien Definida . . . . . . . . . . . . . . . . . .
13.4.3 Elemento Neutro para la Suma . . . . . . . .
13.4.4 Elemento Opuesto . . . . . . . . . . . . . . .
13.4.5 Producto. . . . . . . . . . . . . . . . . . . .
13.4.6 Bien Definido . . . . . . . . . . . . . . . . . .
13.4.7 Elemento Neutro para el Producto . . . . . .
13.4.8 Elemento Inverso . . . . . . . . . . . . . . . .
13.5 Euler, Fermat y Wilson . . . . . . . . . . . . .
13.5.1 Funci´n φ de Euler . . . . . . . . . . . . . . .
o
13.5.2 Teorema de Euler . . . . . . . . . . . . . . . .
13.5.3 Corolario(Fermat) . . . . . . . . . . . . . . .
13.5.4 Teorema de Wilson . . . . . . . . . . . . . . .
13.6 Teorema Chino del Resto . . . . . . . . . . .
13.6.1 Teorema . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . .. .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .

356
356
356
359
359
359
361
366
367
367
368
369
369
370
370
370
371
371
371
371
383
383
384
385389
390
391

En su obra Disquisitiones Arithmeticae, publicada en 1801, Gauss introdujo en las Matem´ticas el cona
cepto de congruencia. Dada la analog´ que exist´ entre ella y la igualdad algebraica, Gauss adopto el
ıa
ıa
s´
ımbolo ≡, notaci´n que a´n se utiliza para la congruencia.
o
u
la relaci´n de congruencia ha proporcionado las herramientas con las cuales se han demostradoimporo
tantes hechos en la Teor´ de N´meros, de hecho ha sido un instrumento de vital importancia para el
ıa
u
estudio de la divisibilidad en Z.
355

Universidad de C´diz
a

Departamento de Matem´ticas
a

Muchos problemas de C´lculo con enteros muy grandes pueden reducirse a problemas equivalentes usando
a
enteros peque˜os mediante el uso de las congruencias.
n

13.1

Conceptos...