Question

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


# Cálculo e explicação pvf #

Answer 1

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! :-)