Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$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
add comment

3 Answers

up vote 10 down vote accepted

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$.

share|improve this answer
1  
+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? –  Quixotic Nov 27 '11 at 19:47
2  
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 :) –  Quixotic Nov 27 '11 at 21:29
add comment

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}.$$

share|improve this answer
    
I knew this,this is rather the straight forward approach, but don't you think it's cumbersome for a 1 mint rule problem. –  Quixotic 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. –  Quixotic Nov 27 '11 at 19:45
1  
@MaX O ya good point, that is why I changed it! –  Eric Naslund Nov 27 '11 at 19:57
1  
@MaX Because $6543=6500+43=65*100+43\equiv 43\pmod{100}$. –  Eric Naslund Nov 28 '11 at 4:56
show 3 more comments

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$

share|improve this answer
    
this is brilliant! –  pad May 12 '13 at 16:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.