Seja a1, ldots, aPhi(m) um sistema reduzido de resíduos módulo m. Mostre que se cdot(a, m)=1, então a cdot a1, ldots, a cdot aPhi(m) é 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 m . Isso significa que temos um conjunto de números que são coprimos com m e que representam todos os possíveis resíduos quando divididos por m . A gente precisa mostrar que, se pegarmos cada número desse conjunto e multiplicarmos por um número a que também é coprimo com m , o novo conjunto ainda será um sistema reduzido de resíduos módulo m . 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 m . Um conjunto a1, a2, ldots, avarphi(m) é um sistema reduzido de resíduos módulo m se:
  1. Cada ai é coprimo com m (ou seja, gcd(ai, m) = 1 ).
  2. Todos os ai são distintos entre si quando considerados módulo m .
Aqui, varphi(m) é a função de Euler, que conta quantos números são coprimos com m e menores que m .

Passo 3

Agora, vamos considerar o número a tal que gcd(a, m) = 1 . Queremos mostrar que o conjunto a cdot a1, a cdot a2, ldots, a cdot avarphi(m) também é um sistema reduzido de resíduos módulo m . Para isso, precisamos verificar duas coisas:
  1. Cada a cdot ai é coprimo com m .
  2. Todos os a cdot ai são distintos módulo m .

Passo 4

Primeiro, vamos mostrar que cada a cdot ai é coprimo com m . Sabemos que gcd(a, m) = 1 e gcd(ai, m) = 1 para todo i . Pela propriedade dos números coprimos, se gcd(a, m) = 1 e gcd(ai, m) = 1 , então gcd(a cdot ai, m) = 1 . Portanto, cada elemento do novo conjunto também é coprimo com m .

Passo 5

Agora, vamos verificar se todos os a cdot ai são distintos módulo m . Suponha que existam i e j tais que a cdot ai equiv a cdot aj pmodm . Isso implica que:
a cdot (ai - aj) equiv 0 pmodm
Como gcd(a, m) = 1 , podemos cancelar a de ambos os lados, ficando:
ai - aj equiv 0 pmodm Rightarrow ai equiv aj pmodm
Mas, como o conjunto a1, a2, ldots, avarphi(m) é um sistema reduzido de resíduos, sabemos que todos os ai são distintos módulo m . Então, a única possibilidade é que i = j . Isso mostra que não há repetições no novo conjunto.

Resposta

Assim, mostramos que a cdot a1, ldots, a cdot aPhi(m) é um sistema reduzido de resíduos módulo m .

Exercícios relacionados