Doubt about divisibility in power of $2$ and $3$

Question

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.

Answer 1

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$?

Answer 2

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.

Answer 3

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$.

Answer 4

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$.

Answer 5

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.