Question

Determine o resto da divisão de 3^100000 por 35.

Answer 1

Olá Cesar.



Organizando e encontrando o resto da potência por 35.

$\mathsf{35=7\cdot5}\\\\\\\mathsf{N\equiv3^{100.000}~(mod~7)}\\\\\mathsf{N\equiv (3^3)^{33.333}\cdot 3~(mod~7)}\\\\\mathsf{N\equiv (27)^{33.333}\cdot3~(mod~7)}\\\\\mathsf{N\equiv (-1)^{33.333}\cdot3~(mod~7)}\\\\\mathsf{N\equiv-3~(mod~7)}\\\\\mathsf{N\equiv 4~(mod~7)}\\\\\\\mathsf{3^{100.000}=7k+4~(i)}\\\\\\\mathsf{N\equiv3^{100.000}~(mod~5)}\\\\\mathsf{N\equiv(-2)^{100.000}~(mod~5)}\\\\\mathsf{N\equiv(-2^4)^{25.000}~(mod~5)}\\\\\mathsf{N\equiv16^{25.000}~(mod~5)}\\\\\mathsf{N\equiv 1^{25.000}~(mod~5)}$

$\mathsf{3^{100.000}=5k'+1~(ii)}\\\\\\\mathsf{(i)~\cdot5~\Rightarrow~5\cdot3^{100.000}=35k+20}\\\\\\\mathsf{(ii)~\cdot7~\Rightarrow~7\cdot3^{100.000}=35k'+7}\\\\\\\mathsf{3^{100.000}=A}\\\\\\\\\mathsf{5A\equiv20~(mod~35)}\\\\\mathsf{7A\equiv7~(mod~35)}\\\\\mathsf{7A-5A\equiv7-20~(mod~35)}\\\\\mathsf{2A\equiv-13~(mod~35)}\\\\\mathsf{18\cdot 2A\equiv-234~(mod~35)}\\\\\mathsf{A\equiv-24~(mod~35)}\\\\\boxed{\mathsf{A\equiv11~(mod~35)}}$

Resto será 11.


Dúvidas? comente.