(a) n^13 equiv n bmod p, para p=2,3,5,7 e 13 , e para todo n in Z.
(b) Se mdc(n, p)=1, mostre que n^12 equiv 1 bmod p, para p=2,3,5,7 e 13 .

Passo 1

O enunciado pede para provar duas coisas envolvendo congruências módulo p, com p variando entre os primos 2,3,5,7,13.
(a) Mostrar que para todo ninZ vale
n^13equiv npmod p
(b) Sob a hipótese gcd(n,p)=1, mostrar que
n^12equiv1pmod p
O conteúdo principal a usar é o Pequeno Teorema de Fermat, que diz que, para todo primo p,
  1. se gcd(n,p)=1, então n^p-1equiv1pmod p,
  2. e mais ainda, valendo para todo n, n^pequiv npmod p

Passo 2

Como os módulos p são primos, podemos aplicar o Pequeno Teorema de Fermat. Em particular:
  • Se gcd(n,p)=1, então ;n^p-1equiv1pmod p.
  • Se pmid n, então nequiv0pmod p e assim n^pequiv0equiv npmod p.
    Logo em ambos os casos ( gcd(n,p)=1 ou pmid n) vale
n^pequiv npmod p

Passo 3

Para cada primo pin2,3,5,7,13 note que p-1 divide 12. Mais precisamente existe um inteiro k tal que
13 = (p-1),k + 1
De fato:
  • p=2implies p-1=1,;13=1cdot12+1.
  • p=3implies p-1=2,;13=2cdot6+1.
  • p=5implies p-1=4,;13=4cdot3+1.
  • p=7implies p-1=6,;13=6cdot2+1.
  • p=13implies p-1=12,;13=12cdot1+1.

Passo 4

Usando a divisão acima, escrevemos
n^13 = n^(p-1)k + 1 = l(n^p-1r)^k ,n
Pelo Pequeno Teorema de Fermat, ;n^p-1equiv1pmod p quando gcd(n,p)=1, e mesmo se pmid n ambas as partes ficam 0. Logo
n^13equiv1^kcdot n=npmod p,
provando o item (a) para todo n.

Passo 5

Sob a hipótese gcd(n,p)=1, o Pequeno Teorema já garante
n^p-1equiv1pmod p
Como vimos, p-1 divide 12, isto é, existe m tal que
12 = (p-1),m
Então
n^12 = l(n^p-1r)^m equiv1^m = 1pmod p,
o que comprova o item (b).

Resposta

(a) Para cada primo pin2,3,5,7,13 vale ;n^13equiv npmod p.
(b) Se gcd(n,p)=1, então para esses mesmos p vale ;n^12equiv1pmod p.

Exercícios relacionados