Seja
um inteiro.
a) Se a é raiz primitiva de
, mostre que os elementos de
são mutuamente incôngruos, módulo n .
b) Se
indicam os inteiros positivos menores que
e primos com n , prove que todo elemento de A é côngruo, módulo n , a um único elemento
.
Resolução de b): Dividamos
por
. Como mdc
, então mdc
e portanto
. Logo
é um dos elementos de
. Como
, então cada
é côngruo, módulo
, a algum dos
. Näo podemos ter
,
, pois isto obriga
, o que não é possível, já que
.
a) Se a é raiz primitiva de
b) Se
Passo 1
Temos um inteiro
e um gerador primitivo
módulo
, de modo que
e a ordem de
é
. Denotemos por
e por
o conjunto dos inteiros positivos menores que
e coprimos com
. Queremos mostrar que, para cada
, existe um único índice
tal que
Passo 2
Aplique o algoritmo da divisão de Euclides a
dividindo por
. Obtemos inteiros
e
tais que
Pelo critério de congruência, isto significa
Passo 3
Como
, segue-se por propriedades do máximo divisor comum que
Então
Logo cada resto
é um inteiro entre
e
e coprimo com
, isto é,
Portanto cada
é congruente, módulo
, a algum elemento
.
Passo 4
Falta ver unicidade. Se por acaso tivéssemos
com
, então
. Mas
e ambos coprimos com
, logo não podem ser congruentes não triviais. Assim não há como dois índices distintos darem o mesmo resto.
Resposta
Cada
(
) deixa resto
em
com
, portanto
é um e somente um dos
. Dessa forma todo elemento de
é congruente, módulo
, a um único elemento de
.