(Aritmética: Números naturais – Princípio da Indução Finita – Números primos – divisibilidade – congruência modular – Pequeno Teorema de Fermat)
Seja [tex]p[/tex] um número natural primo. Usando o Princípio da Indução Finita, mostre que
[tex]n^p\equiv n~\pmod{p}[/tex]
para todo [tex]n\in\mathbb{N}.[/tex]
─────
Dica: Verifique que [tex]p[/tex] divide [tex]\dbinom{p}{k}[/tex] para todo [tex]k\in\{1,\,2,\,\ldots,\,p-1\}.[/tex]
Seja [tex]p[/tex] um número natural primo. Usando o Princípio da Indução Finita, mostre que
[tex]n^p\equiv n~\pmod{p}[/tex]
para todo [tex]n\in\mathbb{N}.[/tex]
─────
Dica: Verifique que [tex]p[/tex] divide [tex]\dbinom{p}{k}[/tex] para todo [tex]k\in\{1,\,2,\,\ldots,\,p-1\}.[/tex]
More Questions From This User See All
Lista de comentários
Verified answer
Primeiramente, será demonstrado que [tex]p \mid \dbinom{p}{k} \forall k \in \{1,2,\dots,p-1\}[/tex].
Como [tex]p[/tex] é primo, este não pode ser escrito como produto de outros fatores primos, e como [tex]k < p[/tex] (e consequentemente todos os elementos de [tex]k![/tex] são, individualmente, menores que p) então se pode concluir que nenhum fator de [tex]k![/tex] tem [tex]p[/tex] como um de seus fatores na decomposição por primos (e, em conta de [tex]p[/tex] ser primo, tampouco há nenhuma combinação dos fatores de [tex]k![/tex] que resulte em [tex]p[/tex]). Como [tex]C(p,k)[/tex] sempre resulta em um natural, e, como dito acima, nenhuma combinação de fatores do denominador divide [tex]p[/tex], então pode se isolar [tex]p[/tex] da expressão sem nenhum prejuízo para a divisão:
[tex]\dbinom{p}{k}\\\\= \cfrac{p!}{k!(p-k)!} \\\\= p \cdot\cfrac{(p-1)!}{k!(p-k)!}[/tex]
Portanto [tex]p \mid C(p,k)[/tex], para o intervalo de [tex]k[/tex] mencionado.
Comecemos agora com o Princípio da Indução Finita:
Caso base [tex]n = 1[/tex]:
[tex]1^p \equiv 1 \equiv n \pmod p[/tex]
A proposição é válida.
Suponhamos que dado um [tex]n[/tex] qualquer, a seguinte expressão é válida (a tal da hipótese de indução):
[tex]n^p \equiv n \pmod p[/tex]
Verifiquemos se a validade da proposição com [tex]n[/tex] implica na validade da proposição com [tex]n+1[/tex] :
[tex](n+1)^p[/tex]
Conforme demonstrado nesse link*, podemos reescrever a expressão acima como:
[tex]\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)[/tex]
Como visto anteriormente, [tex]p \mid \dbinom{p}{k}[/tex] para todos os valores do somatório em (i), exceto com [tex]k=0[/tex] e [tex]k=p[/tex]. Em congruência módulo [tex]p[/tex], podemos descartar todos os múltiplos de [tex]p[/tex] de um lado só da congruência sem alterar sua validade. Façamos isso:
[tex]\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[/tex]
Utilizando a hipótese de indução:
[tex]\equiv n + 1 \pmod p[/tex]
Atingindo o resultado desejado.
Como o elemento mínimo dos naturais é válido, e [tex]p(n) \Longrightarrow p(n+1)[/tex], se pode afirmar que a proposição é válida [tex]\forall n \in \mathbb{N}[/tex].
* https://brainly.com.br/tarefa/53332076