Qual é o resto da divisão de 2^334 por 23?A 2B 4C 8D 16E 20
#ENADE
Soluções para a tarefa
Alternativa A!
1) Para responder o problema proposto, primeiramente devemos ter em mente que o resto de uma divisão trata-se da sobra de uma divisão entre números inteiros. Por exeplo a figura em anexo.
2) Assim, resolvendo a divisão proposta pelo problema, teremos:
Total = 2^334 / 23
Total = 3.4996E+100 / 23
Total = 1.5216E+99
3) Por fim, o número inteiro como resultado da divisão corresponde a 1E+99
, enquanto que a parte não inteira corresponde a 0,5216E+99
. Assim, o valor mais proximo do resto será 2, alternativa A.
Resposta:
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)}np≡n(mod p)
isto é
\mathsf{n^p-n}np−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)}np−1≡1(mod p)
isto é
\mathsf{n^{p-1}-1}np−1−1 é múltiplo de p;
ou equivalentemente
\mathsf{n^{p-1}}np−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
\begin{gathered}\mathsf{2^{23-1}\equiv 1\quad(mod~23)}\\\\ \mathsf{2^{22}\equiv 1\quad(mod~23)}\end{gathered}223−1≡1(mod 23)222≡1(mod 23)
Como o expoente é 334, e
\mathsf{334=22\cdot 15+4}334=22⋅15+4
eleve os dois lados da congruência a 15:
\begin{gathered}\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)}\end{gathered}(222)15≡115(mod 23)222⋅15≡115(mod 23)2330≡1(mod 23)
Multiplique os dois lados por \mathsf{2^4}:24:
\begin{gathered}\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)}\end{gathered}2330⋅24≡1⋅24(mod 23)2330+4≡24(mod 23)2334≡16(mod 23)
isto é
\mathsf{2^{334}-16}2334−16 é múltiplo de 23.
Como 0 ≤ 16 < 23, o resto da divisão é 16.