Calculating 2 rightmost decimal digits of large number (modular exponentiation)

Question

I'm asked to calculate 2 rightmost decimal digits of large number, e.g. 3^2005. The hint is to use some modular trick (probably Euler phi function). Can anyone show me how to reduce the exponent?

Answer 1

Start with a really really easy question: what are the two rightmost digits of $1234567$?

Obviously, $67$. Next question: what does this have to do with modular arithmetic? Answer: it's really just another way of saying that $$1234567\equiv67\pmod{100}\ .$$ So, you need to simplify $3^{2005}$ modulo $100$. BTW, this question is "obviously" about 9 years old ;-)

Using Euler's function as you suggest is a good start - can you find an exponent $m$ such that $3^m$ is very simple modulo $100$? Then can you find a higher value of $m$ with the same property? And another? And one which is very close to $2005$?

Answer 2

Hint $\ $ Euler $\,\phi(100) = 40,\,$ so $\rm\,{\rm mod}\ 100\!:\ \color{#c00}{3^{\large 40}\equiv 1}\,\Rightarrow\,3^{\large 40J+\color{#0a0}K}\equiv (\color{#c00}{3^{\large 40}})^J 3^{\large K}\equiv \color{#c00}1^{\large J}3^{\large K}\equiv 3^{\large\color{#0a0}K}$

In your case $\ 2005\ =\ 40\cdot 50 + \color{#0a0}5,\ $ so applying the above yields$\ \ldots$

Answer 3

I pulled out the calculator on Windows and multiplied $3$ by itself repeatedly until I got $01$ for the rightmost two digits: $3^{20} = 3,486,784,401.$

So $3^0 \equiv 3^{20} \equiv 3^{40} \equiv ... \equiv 3^{2000} \equiv 1$ (mod 100).

Likewise $3^{2005} \equiv 3^{5} \equiv 43$ (mod 100).