Doubt about divisibility in power of $2$ and $3$ I'm in doubt about this problem!
show that $2^{1002} + 3^{1002}$ is divisible by $13$. Find conditions on n (positive integer) so that  $2^n + 3^n$ is divisible by $13$.
In the first part I have no idea how to start!
In the second part I received the suggestion to use the following identity
$$a^m + b^m = (a+b)(a^{m-1} -a^{m-2}b + a^{m-3}b^{2} - ... + a^{2}b^{m-3} - ab^{m-2} + b^{m-1})$$
where $a, b$ are positive integers and $m$ is odd. But when I use it, I get to something that I don't know how to continue.
Can someone help me?
Thanks.
 A: If you calculate the remainder of $2^n+3^n$ when divided by ${13}$ for small values of $n$,
you will see that it is $0$ when $n=4k+2$.  This can be proved by induction.
Base case:  $2^2+3^2$ is divisible by $13$.
Induction step:  assume $2^{4k+2}+3^{4k+2}$ is divisible by $13$.
Then can you show that $2^{4k+6}+3^{4k+6}=16\times(2^{4k+2}+3^{4k+2})+65\times3^{4k+2}$ is divisible  by $13$?
A: hint
$$1002=83.12+6$$
By Fermat's little theorem,
$$2^{12}\equiv 1 \mod 13$$
$$2^{1002}\equiv 2^6\mod 13$$
$$2^6=64\equiv -1\mod 13$$
$$3^{1002}\equiv 3^6 \mod 13$$
$$3^3=27\equiv 1\mod 13$$
Thus
$$2^{1002}+3^{1002}\equiv -1+1\mod 13$$
Done.
A: By Fermat, $2^{12} \equiv 3^{12} \equiv1 \bmod 13$. Therefore $(2^n+3^n) \bmod 13$ is periodic of period at most $12$. In fact, the period is exactly $12$:
$$
2, 5, 0, 9, 6, 2, 0, 1, 5, 6, 0, 3, 2, 5, 0, \dots
$$
The zeros occur exactly when $n \equiv 2 \bmod 4$.
A: Hint for using the suggestion you received:
$4^{501}+9^{501}=(4+9)(4^{500}-4^{499}9+\cdots-4\cdot9^{499}+9^{500})$,
and a similar equality holds for odd exponents other than $501$.
A: A smidgeon of cleverness (aka experience) suggests multiplying $2^n+3^n$ by $7^n$:
$$\begin{align}
2^n+3^n\equiv0\mod13&\iff7^n(2^n+3^n)\equiv0\mod13\\
&\iff14^n+21^n\equiv0\mod13\\
&\iff1^n+8^n\equiv0\mod13\\
&\iff8^n\equiv-1\mod13
\end{align}$$
Now $8^2=64\equiv-1$ mod $13$, so $8^4\equiv1$ mod $13$, and thus
$$2^n+3^n\equiv0\mod13\iff8^n\equiv-1\mod13\iff n\equiv2\mod4$$
The "cleverness" amounted to knowing that it would be possible, and useful, to turn $2^n+3^n\equiv0$ into an equation of the form $a^n\equiv-1$, and that one straightforward way to do so is by multiplying by the $n$th power of $(13+1)/2$. Once you've got the value for $a$, it's just a matter of computing powers of $a$ mod $13$ until you get to $-1$; in this case, with $a=8$, we get lucky and it happens right away.
