Is this problem correct?

Question

I have found another problem in my book. I have to prove that

$$2^{70}+3^{70}$$ is divisible by 13. But I have proven that $2^{70}\equiv 12 (mod 13)$ and $3^{70}\equiv 3 (mod 13)$ so it is impossible!! What's wrong with my textbook??!

Answer 1

By Fermat's little theorem (let $(x,y)=(2^{70},3^{70})$, note $\gcd(4,13)=\gcd(9,13)=1$):

$$4x\equiv 2^{72}\equiv 2^{72\pmod{\! 12}}\equiv 2^{0}\equiv 1\pmod{\! 13}$$

$$4x\equiv -12\stackrel{:4}\iff x\equiv -3\equiv 10\pmod{\! 13}$$

$$9y\equiv 3^{72}\equiv 3^{72\pmod{\! 12}}\equiv 3^0\equiv 1\pmod{\! 13}$$

$$9y\equiv 27\stackrel{:9}\iff y\equiv 3\pmod{\! 13}$$

$$x+y\equiv 10+3\equiv 0\pmod{\! 13}$$

Your calculation of $2^{70}\bmod 13$ was incorrect.

Answer 2

$13$ is prime, so $2^{12} \equiv 1 $ mod $13$. Now $2^{10} \times 2^{2} \equiv 1$ mod $13$,this means that$2^{10} \equiv 10$ mod $13$, so $2^{70} \equiv 10$ mod $13$, as $70 =12 \times 5 + 10$.