Seja dado um número natural m=p1 ^alpha 1 1 ldots pr^alpha r decomposto em fatores irredutíveis. Seja n um número natural tal que phi(pi^ai) divide n , para todo i=1, . . . , r. Mostre que m divide a^n-1 para todo número natural a primo com m .

Passo 1

O enunciado pede para mostrar que, dado um número natural decomposto em fatores primos
m = p1^alpha1cdots pr^alphar
e um natural n tal que varphi(pi^alphai) divide n para todo i, vale
que m divide a^n - 1 sempre que gcd(a,m)=1. O conteúdo principal é usar o Teorema de Euler em cada fator primo e depois combinar os resultados.

Passo 2

Primeiro aplicamos o Teorema de Euler em cada primo: como gcd(a,pi^alphai)=1, vale
a^varphi(pi^alphai)equiv 1 pmodpi^alphai

Passo 3

Como por hipótese varphi(pi^alphai) divide n, existe inteiro ki tal que n = ki,varphi(pi^alphai). Então elevando à potência ki temos
a^n = l(a^varphi(pi^alphai)r)^ki equiv 1^ki equiv 1 pmodpi^alphai

Passo 4

A congruência acima mostra que para cada i
pi^alphai mid a^n - 1

Passo 5

Como os pi^alphai são primos distintos, seus produtos são coprimos dois a dois. Daí, pelo princípio de divisão em fatores primos (ou CRT), o produto
m = p1^alpha1cdots pr^alphar divide a^n-1.

Resposta

m \mid a^n - 1

Exercícios relacionados