Seja
um sistema completo de resíduos módulo
.
Mostre que se
, então
é um sistema completo de resíduos módulo
.
Mostre que se
Passo 1
Beleza, vamos lá! O exercício fala sobre sistemas completos de resíduos módulo
. Basicamente, um sistema completo de resíduos módulo
é um conjunto de
números que, quando divididos por
, dão todos os possíveis restos de 0 até
. Aqui, a gente precisa mostrar que, se
e
são números que não têm nenhum divisor em comum além de 1 (ou seja,
), então o conjunto
também forma um sistema completo de resíduos módulo
. Para isso, vamos usar conceitos de aritmética modular e propriedades de números coprimos.
Passo 2
Primeiro, vamos entender o que significa
. Isso quer dizer que
e
são coprimos, ou seja, não têm nenhum divisor comum além de 1. Essa propriedade é importante porque implica que
tem um inverso multiplicativo módulo
, o que nos ajuda a garantir que as múltiplas de
se comportam de maneira “uniforme” quando olhamos os resíduos módulo
.
Passo 3
Agora, vamos considerar o conjunto
. Queremos mostrar que, quando pegamos cada um desses termos módulo
, obtemos todos os resíduos possíveis de 0 até
, sem repetições.
Para isso, vamos supor que existem dois termos distintos nesse conjunto que são congruentes módulo
. Ou seja, suponha que existam
e
com
tais que:
Passo 4
Subtraindo
de ambos os lados, temos:
Isso implica que:
Como
, podemos “cancelar” o
dessa congruência. Na aritmética modular, se
e
, então necessariamente
. Então, temos:
Mas
e
são inteiros que satisfazem
, o que significa que
está entre
e
. A única maneira de
ser equivalente a 0 módulo
dentro desse intervalo é se
, o que contraria nossa suposição inicial de que
e
são distintos.
Passo 5
Portanto, nossa suposição de que existem dois termos distintos no conjunto que são congruentes módulo
leva a uma contradição. Isso significa que todos os termos do conjunto
são distintos quando vistos módulo
.
Além disso, como temos exatamente
termos distintos e há apenas
possíveis resíduos módulo
, isso garante que o conjunto de fato contém todos os resíduos possíveis de 0 até
.
Resposta
Assim, mostramos que se
, então o conjunto
é realmente um sistema completo de resíduos módulo
.