Se p e q são primos distintos tais que
a^p equiv a(bmod q) e a^q equiv a(bmod p)
então prove que a^p q equiv a(bmod p q).

Passo 1

O enunciado diz que p e q são primos distintos tais que
a^p equiv a pmod q e a^q equiv a pmod p
Queremos provar que
a^pq equiv a pmodpq
Vamos usar congruências em módulo primo, o Pequeno Teorema de Fermat e, por fim, o Teorema Chinês do Resto.

Passo 2

Mostramos primeiro que
a^pqequiv apmod p
Como a^qequiv apmod p, elevamos essa congruência a p:
(a^q)^p equiv a^p pmod p Longrightarrow a^pq equiv a^p pmod p
Pelo Pequeno Teorema de Fermat, para todo inteiro a,
a^p equiv a pmod p
(se pmid a então ambos são 0 módulo p, e se gcd(a,p)=1 vale a versão usual). Logo
a^pq equiv a pmod p

Passo 3

De modo análogo, mostramos que
a^pqequiv apmod q
Partimos de a^pequiv apmod q e elevamos a q:
(a^p)^q equiv a^q pmod q Longrightarrow a^pq equiv a^q pmod q
Pelo Pequeno Teorema de Fermat (agora para o primo q) tem-se
a^q equiv a pmod q,
e portanto
a^pq equiv a pmod q

Passo 4

Como p e q são primos distintos, gcd(p,q)=1. O Teorema Chinês do Resto diz que se
a^pqequiv apmod p e a^pqequiv apmod q,
então
a^pqequiv apmodpq

Resposta

a^pq equiv a pmodpq

Exercícios relacionados