Sejam
. Encontre o número de geradores de
.
Passo 1
O enunciado dá que
(primos) e
. Pede: encontrar o número de geradores de
.
Informações relevantes do enunciado:
Informações relevantes do enunciado:
-
e são primos distintos. - O grupo considerado é
(o grupo cíclico finito de ordem ). - A pergunta é: quantos elementos de
são geradores (ou seja, geram o grupo inteiro)?
Passo 2
O que significa “ser gerador” em
?
- Em
(grupo aditivo cíclico de ordem ) um elemento representado por gera todo o grupo se o subgrupo gerado por tiver ordem . - A ordem do elemento
em é o menor inteiro positivo tal que , ou seja, .
Agora vamos achar uma fórmula para essa ordem. Seja
. Escrevendo
e
com
, temos
se e somente se
divide
, isto é,
divide
, ou seja,
divide
. Como
, isto ocorre exatamente quando
divide
. Portanto o menor
possível é
. Como
, obtemos a fórmula:
Passo 3
Com a fórmula da ordem, caracterizamos os geradores:
é gerador de
se e somente se
. Pela fórmula isso equivale a
Portanto os geradores de
são exatamente os elementos
com
tais que
. O número desses inteiros é a função totiente de Euler
.
Passo 4
Aplicando ao caso
com
primos distintos, precisamos calcular
. Podemos fazer por contagem direta (inclusão-exclusão):
- Entre os
inteiros , os que NÃO são coprimos com são exatamente aqueles que são múltiplos de ou múltiplos de . - Há
múltiplos de no intervalo (pois ) e há múltiplos de . Mas os múltiplos de e de simultaneamente (múltiplos de ) foram contados duas vezes; há exatamente deles no intervalo (o ou o múltiplo , dependendo da contagem, mas em contagens padrão entre e há um múltiplo comum por bloco). - Pelo princípio da inclusão-exclusão, o número de inteiros entre
e que NÃO são coprimos é . Assim o número de inteiros entre e coprimos com é
Observação alternativa (fórmula multiplicativa): como
é multiplicativa para inteiros coprimos,
, porque
para
primo.
Passo 5
Concluímos que o número de geradores de
é
Exemplo rápido para fixar: se
e
então
. Os geradores de
são as classes
e
, de fato duas.