Seja n>1 um inteiro.
a) Se a é raiz primitiva de n, mostre que os elementos de A=a, a^2, ldots, a^varphi(n) são mutuamente incôngruos, módulo n .
b) Se a1, a2, ldots, avarphi(n) indicam os inteiros positivos menores que n e primos com n , prove que todo elemento de A é côngruo, módulo n , a um único elemento ai.
Resolução de b): Dividamos a^i(1 <= i <= varphi(n)) por n: a^i=n cdot qi+ri (0 <= ri<n). Como mdc (a, n)=1, então mdc (a^i, n)=1 e portanto mdc(n, ri)=1. Logo ri é um dos elementos de a1, a2, ldots, avarphi(n). Como a^i equiv ri(bmod n), então cada a^i é côngruo, módulo n, a algum dos aj (1 <= j <= varphi(n)). Näo podemos ter a^i equiv ar(bmod n) e a^i equiv as(bmod n), 1 <= r, s <= varphi(n), pois isto obriga ar equiv a3(bmod n), o que não é possível, já que 0 <= ar, as<n.

Passo 1

Temos um inteiro n>1 e um gerador primitivo a módulo n, de modo que gcd(a,n)=1 e a ordem de a é varphi(n). Denotemos por
A=a^1,a^2,dots,a^varphi(n)
e por a1,a2,dots,avarphi(n) o conjunto dos inteiros positivos menores que n e coprimos com n. Queremos mostrar que, para cada iin1,2,dots,varphi(n), existe um único índice j tal que
a^i equiv aj pmod n

Passo 2

Aplique o algoritmo da divisão de Euclides a a^i dividindo por n. Obtemos inteiros qi e ri tais que
a^i = n,qi + ri, 0 <= ri < n
Pelo critério de congruência, isto significa
a^i equiv ri pmod n

Passo 3

Como gcd(a,n)=1, segue-se por propriedades do máximo divisor comum que
gcd(a^i,n)=1
Então
gcd(ri,n)=gcd(a^i - n,qi,n)=gcd(a^i,n)=1
Logo cada resto ri é um inteiro entre 0 e n-1 e coprimo com n, isto é,
riina1,a2,dots,avarphi(n)
Portanto cada a^i é congruente, módulo n, a algum elemento aj.

Passo 4

Falta ver unicidade. Se por acaso tivéssemos
a^i equiv ar pmod n e a^i equiv as pmod n
com 1<= r<s<=varphi(n), então arequiv aspmod n. Mas 0<ar<as<n e ambos coprimos com n, logo não podem ser congruentes não triviais. Assim não há como dois índices distintos darem o mesmo resto.

Resposta

Cada a^i ( 1<= i<=varphi(n)) deixa resto ri em [0,n) com gcd(ri,n)=1, portanto ri é um e somente um dos aj. Dessa forma todo elemento de A é congruente, módulo n, a um único elemento de a1,dots,avarphi(n).

Exercícios de Livros Relacionados