# The last two digits of $13^{1010}$.

$13^{1010}$

$13^{\phi(100)} \equiv 1 \mod 100$

$13^{40} \equiv 1 \mod 100$

$(13^{40})^{25} \equiv 1^{25} \mod 100$

$13^{1000} \equiv 1 \mod 100$

$13^{1010} \equiv 13^{10} \mod 100$

That's all I got. I don't know how to proceed from there. I tried with $\phi (200)$ but it doesn't help at all.

• I think you really need to calculate $13^{10}$, which is $69^5$, which is $61\times 61 \times 69 \mod 100$ – k99731 Mar 7 '16 at 19:54
• That works. Thanks. – abuchay Mar 7 '16 at 19:57
• That's where you grab your pocket calculator. Or use a spreadsheet. Or pen and paper. Depends on which power you were left with. – gnasher729 Mar 8 '16 at 15:14

You may compute this by exponentation by squaring.

So $13^2 = 169 \equiv 69 \equiv -31 \mod 100$.

So $13^4 \equiv (-31)^2=961 \equiv -39 \mod 100$.

So $13^8 \equiv (-39)^2=1521 \equiv 21 \mod 100$.

Hence $13^{10} = 13^8 \cdot 13^2 \equiv 69 \cdot 21 = 1449 \equiv 49 \mod 100$

Hence the last digits are a 4 and a 9.

As $1010\equiv2\pmod4,$ let $4n+2=1010\iff n=252$

As $13^2=170-1=-1+170$

Using Binomial Theorem, $$13^{4n+2}=(-1+170)^{2n+1}\equiv(-1)^{2n+1}+\binom{2n+1}1(-1)^{2n}170^1\pmod{100}\equiv170(2n+1)-1\equiv40n+69$$

Now, $n=252\implies252\cdot4\equiv8\pmod{10}$

$\implies252\cdot40\equiv8\cdot10\pmod{10\cdot10}$

Can you take it from here?

Use repeated squaring to evaluate $13^{8}\pmod{100}$. $$13^2\equiv 69 \pmod{100}$$ $$13^4=(13^2)^2\equiv(69)^2\equiv 61 \pmod{100}$$ $$13^8=(13^4)^2\equiv(61)^2\equiv 21 \pmod{100}$$ $$13^{10}=(13^8)\cdot(18^2)\equiv69\cdot21\equiv 49 \pmod{100}$$