Seja p um número primo, a e b inteiros quaisquer. Mostre que
(a) a^{p} \equiv a(\bmod p).
(b) (a+b)^{p} \equiv a^{p}+b^{p}(\bmod p).
(c) (a+b)^{p^{n}} \equiv a^{p^{n}}+b^{p^{n}}(\bmod p). (dica: indução em n )

Passo 1

O enunciado dá as seguintes informações e pede para mostrar três congruências:
  • p é um número primo.
  • a e b são inteiros quaisquer.
    As perguntas a provar são:
    (a) Mostrar que a^{p} \equiv a \pmod{p}.
    (b) Mostrar que (a+b)^{p} \equiv a^{p}+b^{p} \pmod{p}.
    (c) Mostrar que (a+b)^{p^{n}} \equiv a^{p^{n}}+b^{p^{n}} \pmod{p} para todo n\ge 1 (dica: indução em n).

Passo 2

Preparação: explico duas ferramentas que usarei e por que valem.
  1. Teorema do binômio (fórmula de Newton): para inteiros x,y e inteiro m\ge0,
(x+y)^m=\sum_{k=0}^{m}\binom{m}{k} x^{m-k}y^{k},
onde \displaystyle \binom{m}{k}=\frac{m!}{k!(m-k)!} é o coeficiente binomial.
  1. Um fato importante sobre coeficientes binomiais quando m=p é primo: para 1\le k\le p-1 vale
\binom{p}{k}\equiv 0\pmod{p}.
Justificativa simples: \binom{p}{k}=\dfrac{p\cdot (p-1)!}{k!(p-k)!}. Como p é primo, nenhum dos fatores em k! nem em (p-k)! é múltiplo de p, portanto o único fator p do numerador não é cancelado no denominador, o que implica que p divide \binom{p}{k}. Em linguagem congruencial, \binom{p}{k}\equiv 0\pmod p para 1\le k\le p-1.

Passo 3

Prova de (b) usando o binômio e o fato do passo anterior.
Aplicando o teorema do binômio com m=p a (a+b)^p temos:
(a+b)^p=\sum_{k=0}^{p}\binom{p}{k}a^{p-k}b^{k} = a^p + \sum_{k=1}^{p-1}\binom{p}{k}a^{p-k}b^{k} + b^p.
Pelo passo 2 sabemos que, para 1\le k\le p-1, \binom{p}{k} é múltiplo de p. Assim todos os termos da soma intermediária são múltiplos de p e desaparecem módulo p. Portanto
(a+b)^p\equiv a^p+b^p\pmod{p},
o que prova (b).

Passo 4

Observação útil que será usada para (a): colocando b=1 na identidade de (b) obtemos
(a+1)^p\equiv a^p+1\pmod{p}.
Essa relação vai permitir uma prova por indução sobre inteiros não-negativos.

Passo 5

Prova de (a) para inteiros não-negativos por indução.
  • Base: a=0. Temos 0^{p}=0, portanto 0^{p}\equiv 0\pmod{p}.
  • Passo indutivo: suponha que para algum inteiro k\ge 0 valha k^{p}\equiv k\pmod{p}. Então, usando a relação do passo 4,
(k+1)^p\equiv k^p+1\pmod{p}.
Pela hipótese indutiva k^p\equiv k, logo k^p+1\equiv k+1\pmod{p}. Assim (k+1)^p\equiv k+1\pmod{p}. Isso fecha a indução e mostra que para todo inteiro não-negativo n vale n^{p}\equiv n\pmod{p}.

Passo 6

Extensão para inteiros negativos (finalizando a prova de (a)).
Se a é negativo escreva a=-t com t\ge 0. Há dois casos:
  • Se p=2 então a congruência a^2\equiv a\pmod{2} é verdadeira para todo inteiro a (porque a^2 e a têm mesma paridade: a^2 é congruente a a módulo 2).
  • Se p é ímpar (qualquer primo ímpar), então
(-t)^p = -\,t^p.
Pela prova para não-negativos já temos t^p\equiv t\pmod{p}. Multiplicando a congruência por -1 obtemos -t^p\equiv -t\pmod{p}, isto é ( -t)^p\equiv -t\pmod{p}. Logo a congruência vale também para inteiros negativos.
Portanto (a) está provada para todo inteiro a: a^{p}\equiv a\pmod{p}.

Passo 7

Prova de (c) por indução em n.
  • Base n=1: (c) com n=1 é exatamente a parte (b), que já foi provada:
(a+b)^{p}\equiv a^{p}+b^{p}\pmod{p}.
  • Passo indutivo: suponha que para algum n\ge 1 já tenhamos
(a+b)^{p^{n}}\equiv a^{p^{n}}+b^{p^{n}}\pmod{p}.
Elevar ambos os lados à potência p (isto é, tomar p-ésima potência) e usar que se X\equiv Y\pmod{p} então X^{p}\equiv Y^{p}\pmod{p} (isso é permitido porque se X-Y é múltiplo de p então também é múltiplo de p toda potência, ou podemos aplicar a parte (b) ao par de inteiros cujas soma é X-Y — mais diretamente, a operação de elevar à p-ésima potência preserva congruências módulo p) dá
\big((a+b)^{p^{n}}\big)^{p} \equiv \big(a^{p^{n}}+b^{p^{n}}\big)^{p}\pmod{p}.
O lado esquerdo é (a+b)^{p^{n+1}}. Pelo caso (b) (aplicado aos inteiros a^{p^{n}} e b^{p^{n}}) o lado direito é congruente a
\big(a^{p^{n}}\big)^{p}+\big(b^{p^{n}}\big)^{p}=a^{p^{n+1}}+b^{p^{n+1}} \pmod{p}.
Assim obtemos
(a+b)^{p^{n+1}}\equiv a^{p^{n+1}}+b^{p^{n+1}}\pmod{p},
fechando a indução. Portanto (c) vale para todo n\ge 1.

Resposta

(a) \;a^{p}\equiv a\pmod{p}
(b) \;(a+b)^{p}\equiv a^{p}+b^{p}\pmod{p}
(c) \;(a+b)^{p^{n}}\equiv a^{p^{n}}+b^{p^{n}}\pmod{p}

Exercícios relacionados