Seja
um número primo,
e
inteiros quaisquer. Mostre que
(a)
.
(b)
.
(c)
. (dica: indução em
)
(a)
(b)
(c)
Passo 1
O enunciado dá as seguintes informações e pede para mostrar três congruências:
-
é um número primo. -
e são inteiros quaisquer.
As perguntas a provar são:
(a) Mostrar que.
(b) Mostrar que.
(c) Mostrar quepara todo (dica: indução em ).
Passo 2
Preparação: explico duas ferramentas que usarei e por que valem.
- Teorema do binômio (fórmula de Newton): para inteiros
e inteiro ,
onde
é o coeficiente binomial.
- Um fato importante sobre coeficientes binomiais quando
é primo: para vale
Justificativa simples:
. Como
é primo, nenhum dos fatores em
nem em
é múltiplo de
, portanto o único fator
do numerador não é cancelado no denominador, o que implica que
divide
. Em linguagem congruencial,
para
.
Passo 3
Prova de (b) usando o binômio e o fato do passo anterior.
Aplicando o teorema do binômio com
a
temos:
Pelo passo 2 sabemos que, para
,
é múltiplo de
. Assim todos os termos da soma intermediária são múltiplos de
e desaparecem módulo
. Portanto
o que prova (b).
Passo 4
Observação útil que será usada para (a): colocando
na identidade de (b) obtemos
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:
. Temos , portanto . -
Passo indutivo: suponha que para algum inteiro
valha . Então, usando a relação do passo 4,
Pela hipótese indutiva
, logo
. Assim
. Isso fecha a indução e mostra que para todo inteiro não-negativo
vale
.
Passo 6
Extensão para inteiros negativos (finalizando a prova de (a)).
Se
é negativo escreva
com
. Há dois casos:
-
Se
então a congruência é verdadeira para todo inteiro (porque e têm mesma paridade: é congruente a módulo ). -
Se
é ímpar (qualquer primo ímpar), então
Pela prova para não-negativos já temos
. Multiplicando a congruência por
obtemos
, isto é
. Logo a congruência vale também para inteiros negativos.
Portanto (a) está provada para todo inteiro
:
.
Passo 7
Prova de (c) por indução em
.
- Base
: (c) com é exatamente a parte (b), que já foi provada:
- Passo indutivo: suponha que para algum
já tenhamos
Elevar ambos os lados à potência
(isto é, tomar
-ésima potência) e usar que se
então
(isso é permitido porque se
é múltiplo de
então também é múltiplo de
toda potência, ou podemos aplicar a parte (b) ao par de inteiros cujas soma é
— mais diretamente, a operação de elevar à
-ésima potência preserva congruências módulo
) dá
O lado esquerdo é
. Pelo caso (b) (aplicado aos inteiros
e
) o lado direito é congruente a
Assim obtemos
fechando a indução. Portanto (c) vale para todo
.
Resposta
(a)
(b)
(c)
(b)
(c)