The Question:
Evaluate $3^{123}\mod 100$
My Attempt
So initially I attempted to list the powers of 3 and find a pattern of the last two digits – which, despite much painful inspection did not yield an obvious useful pattern.
So I then attempted to simplify this and use Euler's Generalisation of Fermat's Theorem to solve this:
The theorem states: $a^{\phi(n)} \equiv 1 \pmod{n}$
So:
$3^{123}\mod 100$
= $3^{41^3}\mod 100$
= $(3^{40} \times 3^1)^3\mod 100$
I think I'm ok up to that point. Now, $\phi(100) = 40$
So am I right in the following?
$(3^{40} \times 3^1)^3\mod 100$ $\cong$ $(1 \times 3^1)^3\mod 100$
= $3^3\mod 100$
= 27.
Am I correct?
Thanks!
Best Answer
You are indeed correct. There is, however, one minor improvement. Using the Carmichael function, you can argue that a smaller power of $3$, namely $3^{\lambda(100)}=3^{20}\equiv 1\bmod 100$. The Carmichael function of divides half the Euler totient function when the argument is even and the Euler totient is a multiple of $4$, which is true for $\lambda(100)$; thus $3^{20}$ can replace $3^{40}$ in the argument.
At a more elementary level, you can render $3^4=80+1$ and raise both sides to the fifth power, thus $3^{20}\equiv1\bmod 100$ as the Binomial Theorem for $(80+1)^5$ gives multiples of $100$ plus $1$.