Question

(Aritmética: Números naturais – Princípio da Indução Finita – Números primos – divisibilidade – congruência modular – Pequeno Teorema de Fermat)

Seja $p$ um número natural primo. Usando o Princípio da Indução Finita, mostre que

     $n^p\equiv n~\pmod{p}$

para todo $n\in\mathbb{N}.$

─────

Dica: Verifique que $p$ divide $\dbinom{p}{k}$ para todo $k\in\{1,\,2,\,\ldots,\,p-1\}.$
​

Answer 1

Primeiramente, será demonstrado que $p \mid \dbinom{p}{k} \forall k \in \{1,2,\dots,p-1\}$.

Como $p$ é primo, este não pode ser escrito como produto de outros fatores primos, e como $k < p$ (e consequentemente todos os elementos de $k!$ são, individualmente, menores que p) então se pode concluir que nenhum fator de $k!$ tem $p$ como um de seus fatores na decomposição por primos (e, em conta de $p$ ser primo, tampouco há nenhuma combinação dos fatores de $k!$ que resulte em $p$). Como $C(p,k)$ sempre resulta em um natural, e, como dito acima, nenhuma combinação de fatores do denominador divide $p$, então pode se isolar $p$ da expressão sem nenhum prejuízo para a divisão:
$\dbinom{p}{k}\\\\= \cfrac{p!}{k!(p-k)!} \\\\= p \cdot\cfrac{(p-1)!}{k!(p-k)!}$

Portanto $p \mid C(p,k)$, para o intervalo de $k$ mencionado.

Comecemos agora com o Princípio da Indução Finita:

Caso base $n = 1$:

$1^p \equiv 1 \equiv n \pmod p$
A proposição é válida.

Suponhamos que dado um $n$ qualquer, a seguinte expressão é válida (a tal da hipótese de indução):

$n^p \equiv n \pmod p$

Verifiquemos se a validade da proposição com $n$ implica na validade da proposição com $n+1$ :

$(n+1)^p$

Conforme demonstrado nesse link*, podemos reescrever a expressão acima como:

$\sum\limits^{p}_{k=0}\dbinom{p}{k}n^{p-k}1^k\\\\= \sum\limits^{p}_{k=0}\dbinom{p}{k}n^{p-k}\:\:\:(i)$

Como visto anteriormente, $p \mid \dbinom{p}{k}$ para todos os valores do somatório em (i), exceto com $k=0$ e $k=p$. Em congruência módulo $p$, podemos descartar todos os múltiplos de $p$ de um lado só da congruência sem alterar sua validade. Façamos isso:
$\sum\limits^{p}_{k=0}\dbinom{p}{k}n^{p-k}\\\\\\\equiv \dbinom{p}{0}n^{p-0} + \dbinom{p}{p}n^{p-p}\\\\\\\equiv \cfrac{p!}{0! \cdot p!} \cdot n^p + \cfrac{p!}{p! \cdot 0!} \cdot n^0\\\\\\\equiv n^p + 1 \pmod p$

Utilizando a hipótese de indução:
$\equiv n + 1 \pmod p$

Atingindo o resultado desejado.

Como o elemento mínimo dos naturais é válido, e $p(n) \Longrightarrow p(n+1)$, se pode afirmar que a proposição é válida $\forall n \in \mathbb{N}$.

* https://brainly.com.br/tarefa/53332076