Seja a1, ldots, am um sistema completo de resíduos módulo m.
Mostre que se (r, m)=1, então a, a+r, ldots, a+(m-1) r é um sistema completo de resíduos módulo m.

Passo 1

Beleza, vamos lá! O exercício fala sobre sistemas completos de resíduos módulo m . Basicamente, um sistema completo de resíduos módulo m é um conjunto de m números que, quando divididos por m , dão todos os possíveis restos de 0 até m-1 . Aqui, a gente precisa mostrar que, se r e m são números que não têm nenhum divisor em comum além de 1 (ou seja, gcd(r, m) = 1 ), então o conjunto a, a + r, ldots, a + (m-1)r também forma um sistema completo de resíduos módulo m . Para isso, vamos usar conceitos de aritmética modular e propriedades de números coprimos.

Passo 2

Primeiro, vamos entender o que significa gcd(r, m) = 1 . Isso quer dizer que r e m são coprimos, ou seja, não têm nenhum divisor comum além de 1. Essa propriedade é importante porque implica que r tem um inverso multiplicativo módulo m , o que nos ajuda a garantir que as múltiplas de r se comportam de maneira “uniforme” quando olhamos os resíduos módulo m .

Passo 3

Agora, vamos considerar o conjunto a, a + r, a + 2r, ldots, a + (m-1)r . Queremos mostrar que, quando pegamos cada um desses termos módulo m , obtemos todos os resíduos possíveis de 0 até m-1 , sem repetições.
Para isso, vamos supor que existem dois termos distintos nesse conjunto que são congruentes módulo m . Ou seja, suponha que existam i e j com 0 <= i < j <= m-1 tais que:
a + ir equiv a + jr pmodm

Passo 4

Subtraindo a de ambos os lados, temos:
ir equiv jr pmodm
Isso implica que:
(r)(i - j) equiv 0 pmodm
Como gcd(r, m) = 1 , podemos “cancelar” o r dessa congruência. Na aritmética modular, se gcd(r, m) = 1 e r cdot x equiv 0 pmodm , então necessariamente x equiv 0 pmodm . Então, temos:
i - j equiv 0 pmodm
Mas i e j são inteiros que satisfazem 0 <= i < j <= m-1 , o que significa que i - j está entre -m + 1 e m - 1 . A única maneira de i - j ser equivalente a 0 módulo m dentro desse intervalo é se i = j , o que contraria nossa suposição inicial de que i e j são distintos.

Passo 5

Portanto, nossa suposição de que existem dois termos distintos no conjunto que são congruentes módulo m leva a uma contradição. Isso significa que todos os termos do conjunto a, a + r, ldots, a + (m-1)r são distintos quando vistos módulo m .
Além disso, como temos exatamente m termos distintos e há apenas m possíveis resíduos módulo m , isso garante que o conjunto de fato contém todos os resíduos possíveis de 0 até m-1 .

Resposta

Assim, mostramos que se gcd(r, m) = 1 , então o conjunto a, a + r, ldots, a + (m-1)r é realmente um sistema completo de resíduos módulo m .

Exercícios relacionados