Ensino Médio ⇒ Divisão euclidiana Tópico resolvido

[Nh3noenem]

Qual é o resto da divisão de 2[^][2015 por 5?

[csmarceloMOD]

Existe um enunciado na aritmética modular que diz o seguinte:

Se [tex3]c\ |\ a-b[/tex3] e [tex3]a[/tex3] e [tex3]b[/tex3] possuem o mesmo sinal, então os restos de [tex3]\frac{a}{c}[/tex3] e [tex3]\frac{b}{c}[/tex3] são iguais.

[tex3]2^{n+k}-2^n=2^n(2^k-1)[/tex3], que será múltiplo de 5 quando [tex3]5\ |\ 2^k-1[/tex3], o que acontece quando [tex3]k=4[/tex3]. Portanto [tex3]\frac{2^n}{5}[/tex3] e [tex3]\frac{2^{n+4}}{5}[/tex3] possuem o mesmo resto.

Na verdade, [tex3]5\ |\ 2^k-1[/tex3] para todos os múltiplos de 4, mas, para identificar o padrão sem repetição, devemos utilizar o menor valor possível.

[tex3]2^0\mod5=1[/tex3]
[tex3]2^1\mod5=2[/tex3]
[tex3]2^2\mod5=4[/tex3]
[tex3]2^3\mod5=3[/tex3]

Logo,

[tex3]2^{4n}\mod5=1[/tex3]
[tex3]2^{4n+1}\mod5=2[/tex3]
[tex3]2^{4n+2}\mod5=4[/tex3]
[tex3]2^{4n+3}\mod5=3[/tex3]

Temos que

[tex3]2015=4\cdot503+3[/tex3]

Assim, o resto da divisão de [tex3]2^{2005}[/tex3] por 5 é igual a 3.