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.

Ok , so the question is to find the last three digits of $2013^{2012}$. After some reduction using Euler's Theorem I got $13^{12}$(mod 1000). I tried dividing it in 8 and 125 and later use the CRT , but this didn't help (or maybe I did it wrong) . What is the shortest way to get the answer ? (ofc. without using very big numbers)

share|improve this question
    
add comment

4 Answers 4

up vote 1 down vote accepted

${\rm mod}\ \ \ \ \ 8\!:\ 13^{12}\equiv (-3)^{12}\!\equiv 9^6\equiv 1^6\equiv \color{#c00}1\ \ \ \ $ [All arithmetic in this answer can be done mentally] ${\rm mod}\ 125\!:\ 13^{12}\!\equiv 44^6 \equiv 4^6 11^6 \equiv 2^{12} (-4)^3\equiv -2^{18}\overset{\large 2^7\,\equiv\ \color{#c0f}3\ }\equiv\!\! -\color{#c0f}3^2(2^4)\equiv\, \color{#0a0}{-19}$

By Easy CRT: ${\ \ 13^{12} \equiv\, \color{#0a0}{{-}19} + 125\underbrace{\left[\dfrac{\color{#c00}1+\color{#0a0}{19}}{125}\ {\rm mod}\ 8\right]}_{\large \equiv\, 20/5\,\equiv\, 4\qquad}\equiv\, {-}19+125(4) \equiv 481\pmod{1000}}$

Remark $\ $ I'd choose the binomial theorem method if I were evaluating it, but it's worth emphasis that CRT is only slightly more work (and good CRT practice). With a little practice one can tackle such small CRT problems with only mental arithmetic of small numbers (as I did above).

share|improve this answer
add comment

$$13^{12}=(13^2)^6=(170-1)^6\equiv1-\binom61170+\binom62(170)^2\pmod{1000}$$

$$\implies13^{12}\equiv1-6\cdot170+\frac{6\cdot5}2\cdot289\cdot100\pmod{1000}$$

Now $\displaystyle \frac{6\cdot5}2\cdot 289=15\cdot289\equiv5\pmod{10}$

Using $\displaystyle a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c},$ (where $a,b,c,m$ are integers) $\displaystyle\implies\frac{6\cdot5}2\cdot289\cdot100\equiv5\cdot100\pmod{10\cdot100} $

$\displaystyle\implies13^{12}\equiv1-1020+500\equiv501-20\pmod{1000}$

This method can be applied for any number co-prime with $10$(hence with $10^k$)

as we know, any number co-prime with $10$(hence with $10^k$) must end with $1,3,7,9$

and $7^2=49=5\cdot10-1$ and $3^2=9=10-1$

share|improve this answer
add comment

HINT:

$$13^{12}=(10+3)^{12}=3^{12}+12\cdot3^{11}10+\binom{12}2\cdot3^{10}10^2\pmod{1000}$$

Now, $\displaystyle3^{10}=9^5\equiv(-1)^5\pmod{10}\equiv-1$

$\displaystyle\implies\binom{12}2\cdot3^{10}10^2\equiv\binom{12}2\cdot(-1)10^2\pmod{100}$

and $\displaystyle3^{11}=3\cdot9^5=3(10-1)^5\equiv3(-1+\binom51\cdot10^1)\pmod{100}$

Finally, $3^{12}=(3^2)^6=9^6=(10-1)^6=1-\binom6110+\binom6210^2\pmod{1000}$

share|improve this answer
add comment

Even without binomial tricks, this isn't too bad; just remember to produce intermediate results. $13^2=169$ and $13^3$ $=13\cdot 169$ $= 1690+507$ $\equiv 197$ are more or less immediate, and then this just needs to be squared twice. At this point you can either do it 'by hand' or go with $197=200-3$ to get $13^6$ $\equiv 197^2$ $= 200^2-2\cdot3\cdot200+9$ $\equiv 9-200$ $\equiv 809$ and $13^{12}$ $\equiv 809^2$ $= (800+9)^2$ $= 800^2+2\cdot 9\cdot 800 + 9^2$ $\equiv 481$.

share|improve this answer
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.