Show that 13 divides $2^{70}+3^{70}$ 
Show that $13$ divides $2^{70} + 3^{70}$.

My main problem here is trying to figure out how to separate the two elements in the sum, and then use Fermat's little theorem. So how can I separate the two?
Thanks!
 A: $2^{12} \equiv 1 \pmod{13}$ and $3^{12} \equiv 1 \pmod{13}$ by Fermat's Little Theorem.
Hence, $2^{72} \equiv 1 \pmod{13}$ and $3^{72} \equiv 1 \pmod{13}$
$2^{72} \equiv 1 \pmod{13} \Rightarrow 2^{72} \equiv 40 \pmod{13} \Rightarrow 2^{70} \equiv 10 \pmod{13}$
$3^{72} \equiv 1 \pmod{13} \Rightarrow 3^{72} \equiv 27 \pmod{13} \Rightarrow 3^{70} \equiv 3 \pmod{13}$
Hence, you get the result.
A: HINT $\rm\: $ Little Fermat shows $\rm\ mod\ 13:\ \ 2^{70} + 3^{70}\ \equiv\ 2^{-2} + 3^{-2}\ \equiv\ 1/4+1/9\ \equiv 13/36\ \equiv\ 0$
NOTE $\ $ For a slight generalization see here.
A: The "quick" way to do this is as follows:
$2^{6}=64=-1$(mod 13), $3^{3}=1$ (mod 13)
Hence you have $2^{70}=(2^{6})^{11}*2^{4}=(-1)*(3)=-3$ (mod 13)
And $3^{70}=(3^{3})^{13}*3=3$ (mod 13)
Therefore the result is $-3+3=0$ (mod 13). 
Fermat's little theorem implies $a^{p-1}\cong 1$ (mod p), but this may be more slick, I am not sure. Mind that Fermat's little theorem is not optimal in many cases. 
The "ultra quick" way may be $2^{70}+3^{70}=3^{70}*(1+(2/3)^{70})$. Now notice $2/3=2*9=5$. And $5^2=-1$, hence $(1+(5^{2})^{25})=1+-1=0$. Therefore $2^{70}+3^{70}=0$. 
A: Okay, I'm on a little different wavelength so I'll turn my comment into an answer.. if $n$ is odd the polynomial $x + y$ divides $x^n + y^n$. So letting $x = 2^2, y = 3^2,$ and $n = 35$ you get that $13 = 2^2 + 3^2$ divides $2^{70} + 3^{70}$. 
A: Compute $2^{70}$ and $3^{70}$ modulo $13$ separately (e.g., using Fermat's Little Theorem). If $2^{70}\equiv a\pmod{13}$ and $3^{70}\equiv b\pmod{13}$, then what is $2^{70}+3^{70}$ congruent to modulo 13?
A: So by FlT, you know that $2^{12}\equiv 1\pmod{13}$ and $3^{12}\equiv 1\pmod{13}$. So 
$$
2^{70}+3^{70}\equiv (2^{12})^5\cdot 2^{10}+(3^{12})^5\cdot 3^{10}\equiv 2^{10}+3^{10}\pmod{13}.
$$
However, again by FlT, 
$$
2^{12}\equiv 2^{10}\cdot 2^{2}\equiv 1\pmod{13}\implies 2^{10}\equiv 2^{-2}\pmod{13}.
$$
That is to say, $2^{10}$ is congruent to the multiplicative inverse of $4$ modulo $13$. You can do the same for $3^{10}$, except you will need to find the multiplicative inverse to $9$ modulo $13$. You'll see that the sum of these inverses is $0$ modulo $13$, to get your answer.
A: The sequence $a_n=2^n+3^n \bmod 13$ is periodic of period $12$
$$
2,5,0,9,6,2,0,1,5,6,0,3,\color{red}{2,5,0,9,6,2,0,1,5,6,0,3},\dots
$$
Therefore, $a_{n} = 0$ iff $n \equiv 2 \bmod 4$, which holds for $n=70$.
