Olimpíadas ⇒ Teoria dos Números
Moderador: [ Moderadores TTB ]
Nov 2017
24
20:53
Teoria dos Números
Qual o resto da divisão de [tex3]2011^{2011^{2011^{2011^{2011}}}}[/tex3]
por 19
Jan 2018
11
22:51
Re: Teoria dos Números
Primeiramente temos que:
[tex3]2011\equiv-3 \text{ (mod 19)}[/tex3]
Pelo pequeno teorema de Fermat:
[tex3]3^{19}\equiv3\text{ (mod 19)}\Rightarrow (-3)^{19}\equiv-3\text{ (mod 19)}\Rightarrow(-3)^{18}\equiv1\text{ (mod 19)}[/tex3]
O que implica em:
[tex3]2011^{18}\equiv1 \text{ (mod 19)}\Rightarrow(2011^{18})^{111}\equiv1^{111} \text{ (mod 19)}\Rightarrow2011^{1998}\equiv1 \text{ (mod 19)}[/tex3]
Falta multiplicarmos por [tex3]2011^{13}[/tex3] para chegarmos no resto da divisão por [tex3]2011^{2011}[/tex3] . Note que:
[tex3]2011^4\equiv5 \text{ (mod 19)}\Rightarrow(2011^4)^3\equiv-8 \text{ (mod 19)}\Rightarrow2011^{12}\cdot2011\equiv5 \text{ (mod 19)}[/tex3] Então:
[tex3]2011^{1998}\cdot2011^{13}\equiv1\cdot5 \text{ (mod 19)}\Rightarrow2011^{2011}\equiv5 \text{ (mod 19)}[/tex3]
Utilizando o mesmo raciocínio, chegamos que:
[tex3]2011^{2011^{1998}}\equiv1 \text{ (mod 19)}\Rightarrow2011^{2011^{1998}}\cdot2011^{2011^{3^{4}}}\equiv1\cdot (-8)^4\equiv1\cdot(7)^2\equiv-8 \text{ (mod 19)}[/tex3]
Logo:
[tex3]2011^{2011^{2010}}\cdot2011^{2011}\equiv-8\cdot5\text{ (mod 19)}\Rightarrow2011^{2011^{2011}}\equiv-2\text{ (mod 19)}[/tex3]
Por preguiça de escrever, considere [tex3]2011^{2011^{2011}}=k[/tex3] . Então:
[tex3]k^{1998}\cdot k^{5^{2}}\equiv1\cdot6\text{ (mod 19)}\Rightarrow k^{2008}\cdot k^3\equiv6\cdot-8\equiv9\text{ (mod 19)}[/tex3]
Essa questão não acaba nunca...
[tex3]k^{2011^{1998}}\cdot k^{2011^{2^{2^3}}}\equiv1\cdot(5)^{2^3}\equiv6^3\equiv-2\cdot 6\equiv-12\equiv7\text{ (mod 19)}[/tex3]
[tex3]k^{2011^{2010}}\cdot k^{2011}\equiv7\cdot9\equiv6\text{ (mod 19)}[/tex3]
Ou seja, [tex3]2011^{2011^{2011^{2011^{2011}}}}[/tex3] deixa resto [tex3]6[/tex3] quando divisível por [tex3]19[/tex3] .
[tex3]2011\equiv-3 \text{ (mod 19)}[/tex3]
Pelo pequeno teorema de Fermat:
[tex3]3^{19}\equiv3\text{ (mod 19)}\Rightarrow (-3)^{19}\equiv-3\text{ (mod 19)}\Rightarrow(-3)^{18}\equiv1\text{ (mod 19)}[/tex3]
O que implica em:
[tex3]2011^{18}\equiv1 \text{ (mod 19)}\Rightarrow(2011^{18})^{111}\equiv1^{111} \text{ (mod 19)}\Rightarrow2011^{1998}\equiv1 \text{ (mod 19)}[/tex3]
Falta multiplicarmos por [tex3]2011^{13}[/tex3] para chegarmos no resto da divisão por [tex3]2011^{2011}[/tex3] . Note que:
[tex3]2011^4\equiv5 \text{ (mod 19)}\Rightarrow(2011^4)^3\equiv-8 \text{ (mod 19)}\Rightarrow2011^{12}\cdot2011\equiv5 \text{ (mod 19)}[/tex3] Então:
[tex3]2011^{1998}\cdot2011^{13}\equiv1\cdot5 \text{ (mod 19)}\Rightarrow2011^{2011}\equiv5 \text{ (mod 19)}[/tex3]
Utilizando o mesmo raciocínio, chegamos que:
[tex3]2011^{2011^{1998}}\equiv1 \text{ (mod 19)}\Rightarrow2011^{2011^{1998}}\cdot2011^{2011^{3^{4}}}\equiv1\cdot (-8)^4\equiv1\cdot(7)^2\equiv-8 \text{ (mod 19)}[/tex3]
Logo:
[tex3]2011^{2011^{2010}}\cdot2011^{2011}\equiv-8\cdot5\text{ (mod 19)}\Rightarrow2011^{2011^{2011}}\equiv-2\text{ (mod 19)}[/tex3]
Por preguiça de escrever, considere [tex3]2011^{2011^{2011}}=k[/tex3] . Então:
[tex3]k^{1998}\cdot k^{5^{2}}\equiv1\cdot6\text{ (mod 19)}\Rightarrow k^{2008}\cdot k^3\equiv6\cdot-8\equiv9\text{ (mod 19)}[/tex3]
Essa questão não acaba nunca...
[tex3]k^{2011^{1998}}\cdot k^{2011^{2^{2^3}}}\equiv1\cdot(5)^{2^3}\equiv6^3\equiv-2\cdot 6\equiv-12\equiv7\text{ (mod 19)}[/tex3]
[tex3]k^{2011^{2010}}\cdot k^{2011}\equiv7\cdot9\equiv6\text{ (mod 19)}[/tex3]
Ou seja, [tex3]2011^{2011^{2011^{2011^{2011}}}}[/tex3] deixa resto [tex3]6[/tex3] quando divisível por [tex3]19[/tex3] .
Última edição: Lonel (Qui 11 Jan, 2018 23:35). Total de 3 vezes.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 2 Respostas
- 558 Exibições
-
Última msg por Ornitologo
-
- 1 Respostas
- 198 Exibições
-
Última msg por Ittalo25
-
- 4 Respostas
- 497 Exibições
-
Última msg por Lliw
-
- 1 Respostas
- 263 Exibições
-
Última msg por FelipeMartin