Find Remainder with Fermat's Theorem

[jeedoubts]

How to use fermit's thereom in finding remainder of a number when divided by another number ?

(eg remainder of 5²⁰⁰⁵ when divided by 4010 ?)

 

[robert Ihnot]

How did you arrive at such a problem? Fermat's (little) theorem deals prime powers.

 

[rasmhop]

I'm assuming you don't know or don't want to use Euler's theorem.

Note 4010 = 2*5*401.

Can you find integers a,b,c such that
$$\begin{align*}<br /> 5^{2005} &\equiv a \pmod 2 \\<br /> 5^{2005} &\equiv b \pmod 5 \\<br /> 5^{2005} &\equiv c \pmod {401}<br /> \end{align*}$$
? (perhaps using Fermat's little theorem)

If you can, then you can use these results and the Chinese remainder theorem to find 5^2005 modulo 2*5*401.