Seja
um inteiro. Se
, prove que
formam um sistema completo de restos módulo m, para qualquer inteiro c.
Passo 1
O enunciado pede para mostrar que, dados um inteiro
e um inteiro
com
, a sequência de
inteiros
é um sistema completo de restos módulo
. O conteúdo usado será teoria de congruências e o fato de que
implica que
é invertível em
.
Passo 2
Primeiro mostramos que todos os termos são distintos entre si módulo
. Suponha que para dois índices
valha
Subtraindo
de ambos os lados,
Como
, segue que
possui inverso multiplicativo módulo
. Multiplicando a congruência pelo inverso de
deduzimos
Mas
e
estão entre
e
, logo a diferença
está entre
e
. A única forma de
ser múltiplo de
nesse intervalo é
. Portanto
. Concluímos que não há repetições: os
termos são todos distintos em
.
Passo 3
Qualquer coleção de
inteiros que sejam todos distintos módulo
forma um sistema completo de restos módulo
. Já que mostramos que a sequência
tem exatamente
resíduos distintos em
, segue que ela exaure todas as classes de equivalência módulo
.
Resposta
Os inteiros
formam um sistema completo de restos módulo
.