Question is to find last two digits of $9^{1500}$ (No Euler totient theorem please)
What i have done so far is :
$9^2\equiv 81\pmod{100}$
$9^4 \equiv 61\pmod{100}$
$9^8\equiv 21\pmod{100}$
$9^{16} \equiv 41\pmod{100}$
$9^{32} \equiv 81\pmod{100}$
higher powers of $9$ namely $64,128,256,512,1024$ will be in repeated pattern as above.
$9^{64} \equiv 61\pmod{100}$
$9^{128} \equiv 21\pmod{100}$
$9^{256} \equiv 41\pmod{100}$
$9^{512} \equiv 81\pmod{100}$
$9^{1024} \equiv 61\pmod{100}$
Now,I want to split power of $9$ i.e., $1500$ to powers which i have noted down above. i.e,
$9^{1500}=9^{1024}.9^{476}$
$9^{1500}=9^{1024}.9^{256}.9^{220}$
$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{92}$
$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{28}$
$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{16}.9^{12}$
$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{16}.9^{8}.9^4$
When you multiply two positive integers, the last digit in the product depends on those two integers only through their last digits.
So, I will look only for last two digits of $9$ in above powers.
$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{16}.9^{8}.9^4$
$\equiv 61.41.21.61.41.21.61 \pmod{100} $
$\equiv (61.61).(21.21).(41.41).61\pmod{100}$
(we have already seen above $61.61\equiv 21 \text{mod}100$ and similarly for other cases). So, we would be left with :
$\equiv (21).(41).(81).(61)\pmod{100}$
$\equiv (61)(41)\pmod{100}$
$\equiv (01) \pmod{100}$
I would be happy if someone can verify the procedure I have done and I would be thankful if some one can help me to make this less laborious and more efficient.
Best Answer
You have seen that $9^2 \equiv 9^{32} \equiv 81$ mod $100$. As gcd$(81,100) = 1$, this implies $9^{30} \equiv \frac{9^{32}}{9^2} \equiv \frac{81}{81} \equiv 1$, and thus $9^{1500} = (9^{30})^{50} \equiv 1$.
Your method also works, but it is longer.