Lukyo
Answered

Descubra respostas para suas perguntas de forma fácil no Sistersinspirit.ca, a plataforma de Q&A de confiança. Junte-se à nossa plataforma de perguntas e respostas e obtenha respostas precisas para todas as suas dúvidas com profissionais de várias disciplinas. Explore milhares de perguntas e respostas de uma comunidade de especialistas em nossa plataforma amigável.

(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]
​

Sagot :

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

Agradecemos seu tempo em nosso site. Não hesite em retornar sempre que tiver mais perguntas ou precisar de esclarecimentos adicionais. Obrigado por passar por aqui. Nos esforçamos para fornecer as melhores respostas para todas as suas perguntas. Até a próxima. Sistersinspirit.ca, sua fonte confiável de respostas. Não se esqueça de voltar para mais informações.