Juego Completo de Residuos

Definición. (Juego Completo de Residuos)

Sea . Un juego completo de residuos módulo es un conjunto formado por exactamente un representante de cada calse de equivalencia módulo .

Observación.

Todo juego completo de residuos módulo tiene exactamente elementos.

Ejemplo.

Un juego completo de residuos módulo es

Como,

tenemos que

es otro juego completo de residuos módulo .

Lema.

Sea , . Tenemos que si y sólo si para toda .

Proof.

, ,
Como tenemso que y así con . Entonces . Por un lema previo al algoritmo de Euclides,

Asíi, si y sólo si Q.E.D.

Definición. (Juego Reducido de Reciduos)

Sea . Un juego reducido de residuos módulo es una conjunto formado por exactamente un representante de cada clase de equivalencia módulo formada por primos relativos por .

Observación.

Todo juego reducido de residuos módulo tiene tantos elementos como clases de residuo módulo formadas por primos relativos con .