Seja
um sistema reduzido de resíduos módulo m. Mostre que se
, então
é um sistema reduzido de resíduos módulo m:
Passo 1
Beleza, vamos lá! O enunciado fala sobre sistemas reduzidos de resíduos módulo
. Isso significa que temos um conjunto de números que são coprimos com
e que representam todos os possíveis resíduos quando divididos por
. A gente precisa mostrar que, se pegarmos cada número desse conjunto e multiplicarmos por um número
que também é coprimo com
, o novo conjunto ainda será um sistema reduzido de resíduos módulo
. Para resolver isso, vamos usar conceitos de aritmética modular e propriedades de números coprimos.
Passo 2
Primeiro, vamos lembrar o que significa ser um sistema reduzido de resíduos módulo
. Um conjunto
é um sistema reduzido de resíduos módulo
se:
- Cada
é coprimo com (ou seja, ). - Todos os
são distintos entre si quando considerados módulo .
Aqui,
é a função de Euler, que conta quantos números são coprimos com
e menores que
.
Passo 3
Agora, vamos considerar o número
tal que
. Queremos mostrar que o conjunto
também é um sistema reduzido de resíduos módulo
. Para isso, precisamos verificar duas coisas:
- Cada
é coprimo com . - Todos os
são distintos módulo .
Passo 4
Primeiro, vamos mostrar que cada
é coprimo com
. Sabemos que
e
para todo
. Pela propriedade dos números coprimos, se
e
, então
. Portanto, cada elemento do novo conjunto também é coprimo com
.
Passo 5
Agora, vamos verificar se todos os
são distintos módulo
. Suponha que existam
e
tais que
. Isso implica que:
Como
, podemos cancelar
de ambos os lados, ficando:
Mas, como o conjunto
é um sistema reduzido de resíduos, sabemos que todos os
são distintos módulo
. Então, a única possibilidade é que
. Isso mostra que não há repetições no novo conjunto.
Resposta
Assim, mostramos que
é um sistema reduzido de resíduos módulo
.