Using congruence modulo to find last two digits of a number

Question

Consider $29≡29\pmod {100}$ and $29^2 ≡ 41 \pmod {100}$

I understand that $\varphi(100)= 40$ and therefore $29^ {40} ≡ 1 \pmod{100}$. But how do I find this for smaller powers of $29$ i.e. powers below $40$?

Answer 1

For smaller powers you just compute. If you just want one, you can use repeated squaring to do fewer multiplies. A spreadsheet with $40$ lines and =mod(up*29,100) makes it easy. Copy down is your friend.

You could do $\pmod 4$ and $\pmod {25}$ and combine the results with the Chinese remainder theorem, but for numbers this small that is too much work.

Answer 2

$(30-1)^n\equiv(-1)^n+\binom n1(-1)^{n-1}30\pmod{10^2}$