Finding the last two digits of $6543^{210}$

I have to find the last two digits of $6543^{210}$, my strategy is to use the Euler theorem and then some algebra to reduce this to $6543^{10}$, however I can't think of any easy way to proceed after this, any ideas?

-
$43^8 \equiv 1 \bmod(100)$. I just found this by trial though. Hence, $6543^{210} \equiv 43^{210} \bmod(100) \equiv 43^{2} \bmod(100) \equiv 49 \bmod(100)$ – user17762 Nov 27 '11 at 19:28
– barto Aug 20 at 11:48

One can use the binomial theorem (thrice). To do so, write $h$ for everything that is a multiple of $100$, possibly varying from line to line.

Since $6543=43+h$, one knows that $$6543^{210}=(43+h)^{210}=43^{210}+h.$$ Now, $$43^{210}=(3+40)^{210}=3^{210}+210\cdot3^{209}\cdot40+h=3^{210}+h.$$ Finally, $$3^{210}=9^{105}=(-1+10)^{105}=-1+105\cdot10+h=1049+h=49+h,$$ that is, $6543^{210}=49+$ some multiple of $100$.

-
+1 for the nice little trick to evaluate $3^{210} \bmod 100$. – user17762 Nov 27 '11 at 19:35
@Sivaram, yes, like a toddler anxiously clutching its parent's hand, I put as many powers of 10 in the picture as I could. – Did Nov 27 '11 at 19:43
who is toddler ? why is he/she anxious? – VelvetThunder Nov 27 '11 at 19:47
Because it is afraid of falling on the ground/failing to find the last two digits of $6543^{210}$. (And we are all toddlers in the realm of la mathématique, aren't we?) – Did Nov 27 '11 at 19:58
well,I am just an infant :) – VelvetThunder Nov 27 '11 at 21:29

This might be the fastest way: For the last two digits, you want to look modulo $100$. Notice that your number is relatively prime to $100$, and that $\phi(100)=40$. Hence $$6543^{210}\equiv 6543^{10}\equiv 43^{10}\pmod{100}.$$ Here we can try using repeated squaring. $$43^2\equiv 49\pmod{100}.$$ $$43^4\equiv 49^2\equiv 1\pmod{100}.$$ Since $43^4\equiv 1$, we see that $$43^{10}\equiv 43^2\equiv 49\pmod{100}.$$

-
I knew this,this is rather the straight forward approach, but don't you think it's cumbersome for a 1 mint rule problem. – VelvetThunder Nov 27 '11 at 19:35
@MaX: Not really, repeated squaring is the fastest algorithmic way to do it. – Eric Naslund Nov 27 '11 at 19:39
I was commenting on the CRT approach you posted before. – VelvetThunder Nov 27 '11 at 19:45
@MaX O ya good point, that is why I changed it! – Eric Naslund Nov 27 '11 at 19:57
@MaX Because $6543=6500+43=65*100+43\equiv 43\pmod{100}$. – Eric Naslund Nov 28 '11 at 4:56

By the Binomial Theorem, $\rm\ mod\ 100\!:\ (-7+50)^{2+4\:n}\equiv (-7)^{2+4\:n} \equiv 7^2\$ by $\ 7^4 \equiv (50-1)^2\equiv 1$

-
this is brilliant! – pad May 12 '13 at 16:10