IME / ITA ⇒ Resto da Divisão Tópico resolvido

[lecko]

Ache o resto da divisão de [tex3]35^{36^{37}}[/tex3] por [tex3]11[/tex3]:

Resposta

---

R: 9

[lftm]

35 é primo com 11. Assim, pelo pequeno teorema de Fermat, [tex3]35^{10} = 1 \bmod{11}[/tex3]. É conveniente saber o menor número inteiro positivo k tal que [tex3]35^k = 1 \bmod{11}[/tex3]. Pela igualdade anterior, esse número deve ser um divisor de 10, logo só precisamos testar 1,2 e 5.
[tex3]35 = 2 \bmod{11}[/tex3]
[tex3]35^2 = 4 \bmod{11}[/tex3]
[tex3]35^5 = 35^2 \cdot 35^2 \cdot 35 = 4 \cdot 4 \cdot 2 = 32 = 10 \bmod{11}[/tex3]
como nenhum deles funcionou, o menor k vale 10.

Note agora que, para calcular [tex3]35^n[/tex3], basta saber o resto de n por 10. No problema, [tex3]n=36^{37}[/tex3]. Agora 36 não é primo com 10, mas se soubermos seu resto por 2 e por 5, poderemos determinar o resto por 10 usando o teorema chinês do resto. Note que [tex3]36^n[/tex3] é sempre par e, ainda, como [tex3]36 = 1 \bmod{5}[/tex3], [tex3]36^n = 1 \bmod{5}[/tex3] para todo n, inclusive 37. Logo, concluímos que [tex3]36^{37} = 6 \bmod{10}[/tex3]. Assim:

[tex3]35^{36^{37}} = 35^{10q + 6} = (35^10)^q \cdot 35^6 = 35^6 = 35^5 \cdot 35 = 10 \cdot 2 = 20 = 9 \bmod{11}[/tex3]

[lecko]

Bom, depois de rever meus cálculos consegui achar meu erro:
Pelo teorema do resto chinês temos:

Verificação dos restos da divisão:
[tex3]35^{1}[/tex3] [tex3]Resto 2[/tex3]
[tex3]35^{2}[/tex3] [tex3]Resto 4[/tex3]
[tex3]35^{3}[/tex3] [tex3]Resto 8[/tex3]
[tex3]35^{4}[/tex3] [tex3]Resto 5[/tex3]
[tex3]35^{5}[/tex3] [tex3]Resto 10[/tex3]
[tex3]35^{6}[/tex3] [tex3]Resto 9[/tex3]
[tex3]35^{7}[/tex3] [tex3]Resto 7[/tex3]
[tex3]35^{8}[/tex3] [tex3]Resto 3[/tex3]
[tex3]35^{9}[/tex3] [tex3]Resto 6[/tex3]
[tex3]35^{10}[/tex3] [tex3]Resto 1[/tex3]

Bom como deu um não precisa continuar a verificação, sempre que der [tex3]1[/tex3] ou [tex3]0[/tex3] podemos parar e verificar que os demais restos seguirão uma cadeia começando do topo.

Agora basta pegar o expoente e dividir pelo número do expoente do último resto que foi verificado: [tex3]35^{10}[/tex3] no caso então é o número [tex3]10[/tex3]:

o expoente de [tex3]35^{36^{37}}[/tex3] é [tex3]36^{37}[/tex3]

então basta [tex3]\frac{36^{37}}{10}[/tex3] :
Verificando o resto por [tex3]10[/tex3]

[tex3]36^{1}[/tex3] [tex3]Resto 6[/tex3]
[tex3]36^{2}[/tex3] [tex3]Resto[/tex3][tex3]6[/tex3] OBS:este segundo será desconsiderado, pois se continuarmos a verificar veremos que sempre dará resto [tex3]6[/tex3].

Quando o resto repetir também devemos parar e desconsiderar o repetente, então no caso pegaremos somente o primeiro. Isso significa que [tex3]36[/tex3] elevado a qualquer expoente na divisão por [tex3]10[/tex3] deixará sempre resto [tex3]6[/tex3].
Agora que achamos o resto do expoente pela quantidade de restos do número basta pegar o resto e ver qual expoente na primeira verificação irá bater que no caso é [tex3]36^{6}[/tex3]. OBS: veja que o número do expoente é o mesmo que encontramos agora a pouco.
Então o resto correspondente a [tex3]36^{6}[/tex3] é [tex3]9[/tex3], e que será o resto de toda a divisão.

[tex3]Resposta[/tex3] [tex3]=[/tex3] [tex3]9[/tex3]