Qual o resto da divisão de 7^56 por 17 ?
Resp: 1
Ensino Superior ⇒ Congruência modular Tópico resolvido
-
LostWalker
- Mensagens: 680
- Registrado em: 04 Mar 2019, 16:34
- Última visita: 10-04-24
- Agradeceu: 50 vezes
- Agradeceram: 119 vezes
Out 2023
18
13:39
Re: Congruência modular
O Pequeno Teorema de Fermat
[tex3]a^{p-1}=1~~(\mbox{mod p})[/tex3]
Sendo [tex3]p[/tex3] um primo e [tex3]\mbox{mdc}(a,p)=1[/tex3] .
Veja que essas são as condições do enunciado, então temos automaticamente que:
[tex3]7^{16}=1~~(\mbox{mod 17})[/tex3]
Perceba que podemos dizer que:
[tex3]7^{56}=7^{16\cdot3}\cdot7^8=({\color{Purple}7^{16}})^3\cdot7^8\equiv({\color{Purple}1})^3\cdot7^8\equiv7^8[/tex3]
Assim, vamos calcular diretamente o resto de [tex3]7^8[/tex3] por [tex3]17[/tex3] . Veja:
[tex3]\cases{7^1=7~~(\mbox{mod } 17)\\7^2=49\equiv49{\color{JungleGreen}\,-\,17\cdot3}\equiv-2~~(\mbox{mod } 17)\\7^4=7^2\cdot7^2\equiv7\cdot(-2)(-2)\equiv4~~(\mbox{mod } 17)\\7^8=7^4\cdot7^4\equiv4\cdot4\equiv16~~(\mbox{mod } 17)}[/tex3]
Dessa forma, o resto da divisão de [tex3]7^{56}[/tex3] por [tex3]17[/tex3] é [tex3]16[/tex3] .
Identificando o Ciclo dos Restos
Vamos também resolver a questão sem saber o Pequeno Teorema de Fermat. Na parte inicial, vamos verificar os restos das potências de [tex3]7[/tex3] até encontrar algum padrão:
[tex3]\cases{7^1=7~~(\mbox{mod } 17)\\7^2=49\equiv49{\color{JungleGreen}\,-\,17\cdot3}\equiv-2~~(\mbox{mod } 17)\\7^3=7^1\cdot7^2\equiv7\cdot(-2)\equiv-14{\color{JungleGreen}\,+\,17\cdot1}\equiv3~~(\mbox{mod } 17)\\7^4=7^1\cdot7^3\equiv7\cdot3\equiv21{\color{JungleGreen}\,-\,17\cdot1}\equiv4~~(\mbox{mod } 17)\\7^5=7^2\cdot7^3\equiv(-2)\cdot3\equiv-6~~(\mbox{mod } 17)\\7^6=7^3\cdot7^3\equiv3\cdot3\equiv9{\color{JungleGreen}\,-\,17\cdot1}\equiv-8~~(\mbox{mod } 17)\\7^7=7^3\cdot7^4\equiv3\cdot4\equiv12{\color{JungleGreen}\,-\,17\cdot1}\equiv-5~~(\mbox{mod } 17)\\7^8=7^4\cdot7^4\equiv4\cdot4\equiv16{\color{JungleGreen}\,-\,17\cdot1}\equiv-1~~(\mbox{mod } 17)}[/tex3]
Perceba que podemos reutilizar módulos que já calculamos buscando números pequenos para acelerar as contas e que chegamos num ótimo valor, [tex3]7^8=-1~~(\mbox{mod }17)[/tex3] , nisso, podemos definir, segundo o módulo de 17, todos os valores:
[tex3]\cases{7^1=+7~~(\mbox{mod } 17)\\7^2=-2~~(\mbox{mod } 17)\\7^3=+3~~(\mbox{mod } 17)\\7^4=+4~~(\mbox{mod } 17)\\7^5=+6~~(\mbox{mod } 17)\\7^6=-8~~(\mbox{mod } 17)\\7^7=-5~~(\mbox{mod } 17)\\7^8=-1~~(\mbox{mod } 17)\\7^9=-7~~(\mbox{mod } 17)\\7^{10}=+2~~(\mbox{mod } 17)\\7^{11}=-3~~(\mbox{mod } 17)\\7^{12}=-4~~(\mbox{mod } 17)\\7^{13}=-6~~(\mbox{mod } 17)\\7^{14}=+8~~(\mbox{mod } 17)\\7^{15}=+5~~(\mbox{mod } 17)\\7^{16}=+1~~(\mbox{mod } 17)}[/tex3]
Podemos simplificar a questão através do [tex3]7^{16}=1~~(\mbox{mod }17)[/tex3] , disso, a resolução segue igual a que utilizando com o Pequeno Teorema de Fermat, com a diferença que temos todos os valores de restos.
[tex3]a^{p-1}=1~~(\mbox{mod p})[/tex3]
Sendo [tex3]p[/tex3] um primo e [tex3]\mbox{mdc}(a,p)=1[/tex3] .
Veja que essas são as condições do enunciado, então temos automaticamente que:
[tex3]7^{16}=1~~(\mbox{mod 17})[/tex3]
Perceba que podemos dizer que:
[tex3]7^{56}=7^{16\cdot3}\cdot7^8=({\color{Purple}7^{16}})^3\cdot7^8\equiv({\color{Purple}1})^3\cdot7^8\equiv7^8[/tex3]
Assim, vamos calcular diretamente o resto de [tex3]7^8[/tex3] por [tex3]17[/tex3] . Veja:
[tex3]\cases{7^1=7~~(\mbox{mod } 17)\\7^2=49\equiv49{\color{JungleGreen}\,-\,17\cdot3}\equiv-2~~(\mbox{mod } 17)\\7^4=7^2\cdot7^2\equiv7\cdot(-2)(-2)\equiv4~~(\mbox{mod } 17)\\7^8=7^4\cdot7^4\equiv4\cdot4\equiv16~~(\mbox{mod } 17)}[/tex3]
Dessa forma, o resto da divisão de [tex3]7^{56}[/tex3] por [tex3]17[/tex3] é [tex3]16[/tex3] .
Identificando o Ciclo dos Restos
Vamos também resolver a questão sem saber o Pequeno Teorema de Fermat. Na parte inicial, vamos verificar os restos das potências de [tex3]7[/tex3] até encontrar algum padrão:
[tex3]\cases{7^1=7~~(\mbox{mod } 17)\\7^2=49\equiv49{\color{JungleGreen}\,-\,17\cdot3}\equiv-2~~(\mbox{mod } 17)\\7^3=7^1\cdot7^2\equiv7\cdot(-2)\equiv-14{\color{JungleGreen}\,+\,17\cdot1}\equiv3~~(\mbox{mod } 17)\\7^4=7^1\cdot7^3\equiv7\cdot3\equiv21{\color{JungleGreen}\,-\,17\cdot1}\equiv4~~(\mbox{mod } 17)\\7^5=7^2\cdot7^3\equiv(-2)\cdot3\equiv-6~~(\mbox{mod } 17)\\7^6=7^3\cdot7^3\equiv3\cdot3\equiv9{\color{JungleGreen}\,-\,17\cdot1}\equiv-8~~(\mbox{mod } 17)\\7^7=7^3\cdot7^4\equiv3\cdot4\equiv12{\color{JungleGreen}\,-\,17\cdot1}\equiv-5~~(\mbox{mod } 17)\\7^8=7^4\cdot7^4\equiv4\cdot4\equiv16{\color{JungleGreen}\,-\,17\cdot1}\equiv-1~~(\mbox{mod } 17)}[/tex3]
Perceba que podemos reutilizar módulos que já calculamos buscando números pequenos para acelerar as contas e que chegamos num ótimo valor, [tex3]7^8=-1~~(\mbox{mod }17)[/tex3] , nisso, podemos definir, segundo o módulo de 17, todos os valores:
[tex3]\cases{7^1=+7~~(\mbox{mod } 17)\\7^2=-2~~(\mbox{mod } 17)\\7^3=+3~~(\mbox{mod } 17)\\7^4=+4~~(\mbox{mod } 17)\\7^5=+6~~(\mbox{mod } 17)\\7^6=-8~~(\mbox{mod } 17)\\7^7=-5~~(\mbox{mod } 17)\\7^8=-1~~(\mbox{mod } 17)\\7^9=-7~~(\mbox{mod } 17)\\7^{10}=+2~~(\mbox{mod } 17)\\7^{11}=-3~~(\mbox{mod } 17)\\7^{12}=-4~~(\mbox{mod } 17)\\7^{13}=-6~~(\mbox{mod } 17)\\7^{14}=+8~~(\mbox{mod } 17)\\7^{15}=+5~~(\mbox{mod } 17)\\7^{16}=+1~~(\mbox{mod } 17)}[/tex3]
Podemos simplificar a questão através do [tex3]7^{16}=1~~(\mbox{mod }17)[/tex3] , disso, a resolução segue igual a que utilizando com o Pequeno Teorema de Fermat, com a diferença que temos todos os valores de restos.
"[...] Mas essa é a graça dos encontros e desencontros: a Coincidência e o Destino. Se pudesse resumir, diria: A causalidade é a Ironia do Universo."
-Melly
-Melly
-
παθμ
- Mensagens: 963
- Registrado em: 08 Abr 2023, 17:28
- Última visita: 09-06-24
- Localização: Evanston, IL
- Agradeceu: 2 vezes
- Agradeceram: 30 vezes
Out 2023
18
13:41
Re: Congruência modular
Felipe22,
[tex3]7^2 \equiv 49 \equiv 49-51 = -2 \pmod{17}.[/tex3]
[tex3]7^8 \equiv (-2)^4 =16 \equiv 16-17=-1 \pmod{17}[/tex3]
[tex3]7^{56} \equiv (-1)^ 7 \pmod{17} \Longrightarrow 7^{56} \equiv -1 \equiv -1+17=16 \pmod{17}[/tex3]
[tex3]\boxed{7^{56} \equiv 16 \pmod{17}}[/tex3]
A resposta é 16, seu gabarito está errado.
[tex3]7^2 \equiv 49 \equiv 49-51 = -2 \pmod{17}.[/tex3]
[tex3]7^8 \equiv (-2)^4 =16 \equiv 16-17=-1 \pmod{17}[/tex3]
[tex3]7^{56} \equiv (-1)^ 7 \pmod{17} \Longrightarrow 7^{56} \equiv -1 \equiv -1+17=16 \pmod{17}[/tex3]
[tex3]\boxed{7^{56} \equiv 16 \pmod{17}}[/tex3]
A resposta é 16, seu gabarito está errado.
Editado pela última vez por παθμ em 18 Out 2023, 13:43, em um total de 1 vez.
-
- Tópicos Semelhantes
- Resp.
- Exibições
- Últ. msg
-
- 1 Resp.
- 962 Exibições
-
Últ. msg por goncalves3718
-
- 1 Resp.
- 297 Exibições
-
Últ. msg por παθμ
-
- 1 Resp.
- 226 Exibições
-
Últ. msg por παθμ
-
- 3 Resp.
- 291 Exibições
-
Últ. msg por παθμ
