Se
formam um sistemá completo de restos módulo
, mostre que o mesmo se pode dizer de
para todo a
.
Passo 1
O enunciado diz que
é um sistema completo de restos módulo
. Isso significa duas coisas:
- Os
são todos distintos entre si módulo , isto é, se então
- Para todo inteiro
, existe algum tal que
O que precisamos mostrar é que, dado qualquer
, o conjunto
também satisfaz essas duas propriedades, e portanto é outro sistema completo de restos módulo
.
Passo 2
(Provar que os elementos são todos distintos módulo
).
Suponha, por absurdo, que para dois índices tivéssemos
Suponha, por absurdo, que para dois índices
Subtraindo
de ambos os lados, obtemos
o que contradiz a hipótese de que os
originais são todos distintos módulo
. Logo cada
é incongruente a todo
com
.
Passo 3
(Provar que representam todas as classes módulo
).
Seja um inteiro qualquer. Como
é completo, existe algum
tal que
Seja
Adicionando
a ambos os lados, segue
Isto mostra que todo
é congruente a algum elemento do conjunto
.
Resposta
Portanto, para qualquer
, o conjunto
é também um sistema completo de restos módulo
.