Seja m>1 um inteiro. Se a in Z e m d c(a, m)=1, prove que
c, c+a, c+2 a, ldots, c+(m-1) a
formam um sistema completo de restos módulo m, para qualquer inteiro c.

Passo 1

O enunciado pede para mostrar que, dados um inteiro m>1 e um inteiro a com gcd(a,m)=1, a sequência de m inteiros
c,;c+a,;c+2a,;dots,;c+(m-1)a
é um sistema completo de restos módulo m. O conteúdo usado será teoria de congruências e o fato de que gcd(a,m)=1 implica que a é invertível em Z/mZ.

Passo 2

Primeiro mostramos que todos os termos são distintos entre si módulo m. Suponha que para dois índices k,lin0,1,dots,m-1 valha
c + ka equiv c + la pmodm
Subtraindo c de ambos os lados,
ka equiv la pmodm Longrightarrow a,(k-l)equiv 0 pmodm
Como gcd(a,m)=1, segue que a possui inverso multiplicativo módulo m. Multiplicando a congruência pelo inverso de a deduzimos
k-lequiv 0 pmodm
Mas k e l estão entre 0 e m-1, logo a diferença k-l está entre -(m-1) e m-1. A única forma de k-l ser múltiplo de m nesse intervalo é k-l=0. Portanto k=l. Concluímos que não há repetições: os m termos são todos distintos em Z/mZ.

Passo 3

Qualquer coleção de m inteiros que sejam todos distintos módulo m forma um sistema completo de restos módulo m. Já que mostramos que a sequência c+kak=0^m-1 tem exatamente m resíduos distintos em Z/mZ, segue que ela exaure todas as classes de equivalência módulo m.

Resposta

Os inteiros
c,;c+a,;c+2a,;dots,;c+(m-1)a
formam um sistema completo de restos módulo m.

Exercícios de Livros Relacionados