Seja a1, ldots, am um sistema completo de resíduos módulo m.
Se (a, m)=1, então a cdot a1, ldots, a cdot am é um sistema completo de resíduos módulo m. Mostre que vale a recíproca;

Passo 1

Beleza! Vamos resolver esse exercício juntos. A questão fala sobre sistemas completos de resíduos módulo m . A ideia central é entender como multiplicar cada elemento desse sistema por um número a que é coprimo com m (ou seja, (a, m) = 1 ) e ver se o resultado ainda forma um sistema completo de resíduos. Precisamos mostrar que, se ao multiplicar cada elemento por a ainda temos um sistema completo, então necessariamente a e m são coprimos.

Passo 2

Primeiro, vamos lembrar o que é um sistema completo de resíduos módulo m . É um conjunto de m números inteiros onde cada inteiro de 0 a m-1 aparece exatamente uma vez quando consideramos os resíduos desses números em relação a m .
Por exemplo, se m = 5 , um sistema completo de resíduos seria 0, 1, 2, 3, 4 ou qualquer permutação desses números.

Passo 3

Agora, sabemos que a1, a2, ldots, am é um sistema completo de resíduos módulo m . Queremos multiplicar cada elemento por a para formar a cdot a1, a cdot a2, ldots, a cdot am e garantir que esse novo conjunto também seja um sistema completo.

Passo 4

A condição dada é que (a, m) = 1 , ou seja, a e m são coprimos. Isso é importante porque, se dois números são coprimos, então a tem um inverso multiplicativo módulo m . Isso significa que existe algum número b tal que a cdot b equiv 1 mod m .

Passo 5

Agora, queremos mostrar a recíproca: se a cdot a1, a cdot a2, ldots, a cdot am é um sistema completo de resíduos módulo m , então (a, m) = 1 .
Vamos supor que (a, m) neq 1 . Isso significa que a e m têm algum divisor comum d > 1 .

Passo 6

Se d > 1 divide tanto a quanto m , então para qualquer ai , temos a cdot ai equiv 0 mod d . Isso implica que todos os a cdot ai são múltiplos de d .

Passo 7

Mas se todos os a cdot ai são múltiplos de d , então ao considerar módulo m , não conseguimos obter todos os resíduos possíveis de 0 a m-1 , já que estamos limitados aos múltiplos de d . Ou seja, o conjunto a cdot a1, a cdot a2, ldots, a cdot am não consegue cobrir todos os resíduos distintos módulo m .

Passo 8

Isso contraria a suposição de que a cdot a1, a cdot a2, ldots, a cdot am é um sistema completo de resíduos módulo m . Portanto, nossa suposição inicial de que (a, m) neq 1 está errada.

Resposta

Conseguimos provar que, se a cdot a1, a cdot a2, ldots, a cdot am é um sistema completo de resíduos módulo m , então necessariamente (a, m) = 1 .

Exercícios relacionados