Sejam p, q primos distintos e positivos tais que (p-1) \mid(q-1). Mostre que se \operatorname{mdc}(a, p q)=1, então a^{q-1} \equiv 1(\bmod p q).

Passo 1

O enunciado fornece as seguintes informações e pede uma conclusão clara.
  • p e q são primos distintos e positivos.
  • (p-1)\mid(q-1).
  • \gcd(a,pq)=1.
O que se pede: mostrar que
a^{q-1}\equiv 1 \pmod{pq}.

Passo 2

Primeiras observações úteis extraídas das hipóteses.
  • Como \gcd(a,pq)=1, necessariamente \gcd(a,p)=1 e \gcd(a,q)=1.
  • Da divisibilidade (p-1)\mid(q-1) existe um inteiro k\ge 1 tal que
q-1 = k(p-1).

Passo 3

Enunciado e prova do lema principal que vamos usar (Pequeno Teorema de Fermat), explicada de forma elementar.
Lema (Pequeno Teorema de Fermat): se r é primo e \gcd(a,r)=1, então
a^{r-1}\equiv 1 \pmod r.
Prova elementar do lema: considere os números 1,2,\dots,r-1 módulo r. Multiplicar cada um deles por a (com \gcd(a,r)=1) apenas permuta esses resíduos não nulos, ou seja, os produtos a\cdot1, a\cdot2,\dots,a\cdot(r-1) representam os mesmos r-1 resíduos não nulos em ordem permutada. Então, tomando o produto dos r-1 números em cada lista, obtemos a congruência
a^{r-1}\,(r-1)!\equiv (r-1)! \pmod r.
Como r não divide (r-1)! (nenhum dos fatores 1,\dots,r-1 é múltiplo de r), o número (r-1)! tem inverso multiplicativo modulo r; portanto podemos “cancelar” (r-1)! na congruência e obter
a^{r-1}\equiv 1 \pmod r,
o que prova o lema.

Passo 4

Aplicação do lema ao primo p.
Como \gcd(a,p)=1, pelo lema temos
a^{p-1}\equiv 1 \pmod p.
Elevando essa congruência à potência k (multiplicando expoentes), obtemos
a^{k(p-1)}\equiv 1^k \equiv 1 \pmod p.
Recordando que k(p-1)=q-1, segue
a^{q-1}\equiv 1 \pmod p.

Passo 5

Aplicação do lema ao primo q.
Como \gcd(a,q)=1, pelo lema também
a^{q-1}\equiv 1 \pmod q.

Passo 6

Conclusão combinando as congruências.
Dos Passos 4 e 5 temos que a^{q-1}-1 é múltiplo de p e também múltiplo de q. Como p e q são primos distintos, \gcd(p,q)=1; portanto um inteiro que é múltiplo de p e de q é múltiplo de pq. Logo
a^{q-1}-1 \equiv 0 \pmod{pq},
ou seja
a^{q-1}\equiv 1 \pmod{pq}.

Resposta

a^{q-1}\equiv 1 \pmod{pq}

Exercícios relacionados