$123^{561}$ find last $2$ digits Modular Exponentiation mod $100$?

Question

$123^{561}$ Find the last $2$ digits

Can't I work this out using modular exponentiation working mod $100$?

$123^2 = 29\pmod{100}$

$123^4 = (123^2)^2 = 41\pmod{100}$

$123^8 = (123^4)^2 = 81\pmod{100}$

$123^{16} = (123^8)^2 = 61\pmod{100}$

$123^{32} = (123^16)^2 = 21\pmod{100}$

$123^{64} = (123^32)^2 = 41\pmod{100}$

$123^{128} = (123^64)^2 = 81\pmod{100}$

$123^{256} = (123^128)^2 = 61\pmod{100}$

$123^{512} = (123^256)^2 = 21\pmod{100}$

Then $561 = 512 \cdot 32 \cdot 16 \cdot 1$

so $21 \cdot 21 \cdot 61 \cdot 29 = 29\pmod{100}$

The answer is meant to be $21$!

What am I doing wrong? Do I have to use Eulers?

Answer 1

While dealing with modulo of composite number, Carmichael function is general more, if not equally efficient than Euler's Totient Theorem .

Here $\lambda(100)=$lcm$(\lambda(5^2),\lambda(2^2))=$lcm$(20,4)=20$

$\implies a^{20}\equiv1\pmod{100}\ \ \ \ (1)$ if $(a,100)=1\iff (a,10)=1$

whereas $\phi(10^2)=10\cdot\phi(10)=40$

$\implies a^{40}\equiv1\pmod{100} \ \ \ \ (2)$ if $(a,100)=1\iff (a,10)=1$

Now using $(1),$ as $561\equiv1\pmod{20}, a^{561}\equiv a\pmod{100}$

Using $(2),$ as $561\equiv1\pmod{40}, a^{561}\equiv a\pmod{100}$

Answer 2

$123^1$ is $23$, not $29$ mod $100$. Your solution is otherwise correct, although Euler's theorem would be more efficient.