Se
e
são primos distintos tais que
então prove que
.
Passo 1
O enunciado diz que
e
são primos distintos tais que
Queremos provar que
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
Como
, elevamos essa congruência a
:
Pelo Pequeno Teorema de Fermat, para todo inteiro
,
(se
então ambos são
módulo
, e se
vale a versão usual). Logo
Passo 3
De modo análogo, mostramos que
Partimos de
e elevamos a
:
Pelo Pequeno Teorema de Fermat (agora para o primo
) tem-se
e portanto
Passo 4
Como
e
são primos distintos,
. O Teorema Chinês do Resto diz que se
então