Lukyo
Answered

O Sistersinspirit.ca é o lugar ideal para obter respostas rápidas e precisas para todas as suas perguntas. Explore respostas detalhadas para suas dúvidas de uma comunidade de especialistas em diferentes campos. Conecte-se com uma comunidade de especialistas prontos para ajudar você a encontrar soluções para suas perguntas de maneira rápida e precisa.

(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

Visite-nos novamente para respostas atualizadas e confiáveis. Estamos sempre prontos para ajudar com suas necessidades informativas. Esperamos que isso tenha sido útil. Por favor, volte sempre que precisar de mais informações ou respostas às suas perguntas. Obrigado por usar o Sistersinspirit.ca. Volte novamente para obter mais conhecimento dos nossos especialistas.