Matemática, perguntado por Usuário anônimo, 1 ano atrás

Qual o Resto da divisão de
 {2}^{334} \: por \: 23?


# Cálculo e explicação pvf #

Soluções para a tarefa

Respondido por Lukyo
7


Como  23  é primo, e  2  não é múltiplo de  23,  podemos usar o Pequeno Teorema de Fermat:

     •  Teorema:  Dados dois naturais  p, n,  sendo  p  primo, temos que

     \mathsf{n^p\equiv n\quad(mod~p)}


isto é

     \mathsf{n^p-n}  é múltiplo de  p.

Em particular, se  n  não é múltiplo de  p,  e  n ≥ 1,  vale também que

     \mathsf{n^{p-1}\equiv 1\quad(mod~p)}


isto é

     \mathsf{n^{p-1}-1}  é múltiplo de  p;


ou equivalentemente

     \mathsf{n^{p-1}}  deixa resto  1  na divisão por  p.

—————

Nesta tarefa, temos

     •  p = 23,  que é primo;

     •  n = 2,  que não é múltiplo de 23.


Aplicando o teorema, temos que

     \mathsf{2^{23-1}\equiv 1\quad(mod~23)}\\\\ \mathsf{2^{22}\equiv 1\quad(mod~23)}


Como o expoente é  334,  e

     \mathsf{334=22\cdot 15+4}


eleve os dois lados da congruência a  15:

     \mathsf{(2^{22})^{15}\equiv 1^{15}\quad(mod~23)}\\\\ \mathsf{2^{22\,\cdot\,15}\equiv 1^{15}\quad(mod~23)}\\\\ \mathsf{2^{330}\equiv 1\quad(mod~23)}


Multiplique os dois lados por  \mathsf{2^4}:

     \mathsf{2^{330}\cdot 2^4\equiv 1\cdot 2^4\quad(mod~23)}\\\\ \mathsf{2^{330+4}\equiv 2^4\quad(mod~23)}\\\\ \mathsf{2^{334}\equiv 16\quad(mod~23)}


isto é

     \mathsf{2^{334}-16}  é múltiplo de  23.


Como  0 ≤ 16 < 23,  o resto da divisão é  16.


Bons estudos! :-)


Lukyo: Está no início da resposta.
Lukyo: Sim, é a notação para congruência modular.
Lukyo: Dois números naturais n, m são congruentes módulo p se ambos deixam o mesmo resto na divisão por p.
Lukyo: Vale também que (n - m) é múltiplo de p.
Perguntas interessantes