Sejam a e n inteiros maiores que 1 e tais que mdc(a, n) simeq =mdc(a-1, n)=1. Prove que: 1+a+a^2+ldots+a^varphi(n)-1 cong 0(bmod n)

Passo 1

O enunciado diz que a e n são inteiros maiores que 1 tais que
gcd(a,n)=1 e gcd(a-1,n)=1, e pede para provar que
1 + a + a^2 + cdots + a^varphi(n)-1 equiv 0 pmodn
O conteúdo principal que vamos usar é o Teorema de Euler (ou Euler–Fermat) e a soma de uma progressão geométrica em aritmética modular.

Passo 2

Como gcd(a,n)=1, pelo Teorema de Euler temos
a^varphi(n) equiv 1 pmodn
Isso significa que a^varphi(n) - 1 é divisível por n.

Passo 3

Considere a soma
S = 1 + a + a^2 + cdots + a^varphi(n)-1
Na aritmética usual essa soma satisfaz a fórmula da progressão geométrica:
(a-1),S = a^varphi(n) - 1
Como gcd(a-1,n)=1, o elemento a-1 é invertível em Z/nZ. Logo podemos interpretar a igualdade acima módulo n:
(a-1),S equiv a^varphi(n) - 1 pmodn
Mas já vimos que a^varphi(n) - 1equiv 0pmodn. Portanto
(a-1),S equiv 0 pmodn

Passo 4

Como gcd(a-1,n)=1, existe (a-1)^-1 em Z/nZ. Multiplicando a congruência anterior por (a-1)^-1, obtemos
S equiv 0 pmodn

Resposta

1 + a + a^2 + cdots + a^varphi(n)-1 equiv 0 pmodn

Exercícios de Livros Relacionados