Sejam p, q \in \mathbb{P}, p \neq q. Encontre o número de geradores de \mathbb{Z}_{p q}.

Passo 1

O enunciado dá que p,q\in\mathbb{P} (primos) e p\neq q. Pede: encontrar o número de geradores de \mathbb{Z}_{p q}.
Informações relevantes do enunciado:
  • p e q são primos distintos.
  • O grupo considerado é \mathbb{Z}_{p q} (o grupo cíclico finito de ordem pq).
  • A pergunta é: quantos elementos de \mathbb{Z}_{p q} são geradores (ou seja, geram o grupo inteiro)?

Passo 2

O que significa “ser gerador” em \mathbb{Z}_n?
  • Em \mathbb{Z}_n (grupo aditivo cíclico de ordem n) um elemento representado por [k] gera todo o grupo se o subgrupo gerado por [k] tiver ordem n.
  • A ordem do elemento [k] em \mathbb{Z}_n é o menor inteiro positivo t tal que t\cdot[k]=[0], ou seja, t k \equiv 0 \pmod{n}.
Agora vamos achar uma fórmula para essa ordem. Seja d=\gcd(n,k). Escrevendo n=d\cdot n' e k=d\cdot k' com \gcd(n',k')=1, temos
t k \equiv 0\pmod{n}
se e somente se n divide t k, isto é, d n' divide t d k', ou seja, n' divide t k'. Como \gcd(n',k')=1, isto ocorre exatamente quando n' divide t. Portanto o menor t possível é t=n'. Como n'=n/d, obtemos a fórmula:
\text{ord}([k])=\frac{n}{\gcd(n,k)}.

Passo 3

Com a fórmula da ordem, caracterizamos os geradores: [k] é gerador de \mathbb{Z}_n se e somente se \text{ord}([k])=n. Pela fórmula isso equivale a
\frac{n}{\gcd(n,k)}=n \quad\Longleftrightarrow\quad \gcd(n,k)=1.
Portanto os geradores de \mathbb{Z}_n são exatamente os elementos [k] com 0\le k\le n-1 tais que \gcd(n,k)=1. O número desses inteiros é a função totiente de Euler \varphi(n).

Passo 4

Aplicando ao caso n=pq com p,q primos distintos, precisamos calcular \varphi(pq). Podemos fazer por contagem direta (inclusão-exclusão):
  • Entre os pq inteiros 0,1,\dots,pq-1, os que NÃO são coprimos com pq são exatamente aqueles que são múltiplos de p ou múltiplos de q.
  • q múltiplos de p no intervalo 0,\dots,pq-1 (pois p\cdot 0,p\cdot1,\dots,p\cdot(q-1)) e há p múltiplos de q. Mas os múltiplos de p e de q simultaneamente (múltiplos de pq) foram contados duas vezes; há exatamente 1 deles no intervalo (o 0 ou o múltiplo pq, dependendo da contagem, mas em contagens padrão entre 1 e pq há um múltiplo comum por bloco).
  • Pelo princípio da inclusão-exclusão, o número de inteiros entre 1 e pq que NÃO são coprimos é q+p-1. Assim o número de inteiros entre 1 e pq coprimos com pq é
pq - (p+q-1) = pq - p - q + 1 = (p-1)(q-1).
Observação alternativa (fórmula multiplicativa): como \varphi é multiplicativa para inteiros coprimos, \varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1), porque \varphi(p)=p-1 para p primo.

Passo 5

Concluímos que o número de geradores de \mathbb{Z}_{pq} é
\varphi(pq)=(p-1)(q-1).
Exemplo rápido para fixar: se p=2 e q=3 então (p-1)(q-1)=1\cdot2=2. Os geradores de \mathbb{Z}_6 são as classes [1] e [5], de fato duas.

Resposta

(p-1)(q-1)

Exercícios relacionados