Show that $1+2^n+2^{2n}$ is divisible by $7$, when $n$ is not a multiple of $3$

Question

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck.

Show that $1+2^n+2^{2n}$ is divisible by $7$, when $n$ is not a multiple of 3.

Answer 1

$n=3k+1$, $1+2^{3k+1}+2^{2(3k+1)}$, $2^3=1$ mod $7$ implies that

$1+2^{3k+1}+2^{2(3k+1)}=1+2+4$ mod $7$.

$n=3k+2$, $1+2^{3k+2}+2^{2(3k+2)}=1+4+16$ mod $7$ and $1+4+16=0$ mod $7$.

Answer 2

To prove it by mathematical induction, show that it's true for $n=1$ and $n=2$,

and also if it's true for $n=k$ then it's true for $n=k+3$,

because $1+2^{k+3}+4^{k+3}=1+8\times2^k+64\times4^k=1+2^k+4^k+7(2^k+9\times4^k)$.

Answer 3

Whenever a number is not divisible by 3, it leaves remainder as 1 or 2. So, any number which is not divisible by 3 is of the form $n=3l+1$ or $n=3l+2$.

Now, when $n=3l+1$, we have $1+2^{3l+1}+2^{2(3l+1)}=1+2+4$ mod $7$.

and when $n=3l+2$, we have $1+2^{3l+2}+2^{2(3l+2)}=1+4+16$ mod $7$ and $1+4+16=0$ mod $7$.

Answer 4

Since in the fraction $1+2^n+4^n=\frac{8^n-1}{2^n-1}$ the numerator is always a multiple of $7$ by induction, we just need to check $3\nmid n\implies7\nmid 2^n-1$. Indeed $2^{n+3}-1-(2^n-1)=7\times 2^n$, so we only need to check the case $n\in\{1,\,2\}$.

Answer 5

A bit longer:

---

Assume $\tau(n)=\top,n\equiv 1\pmod{3}$ $$1+2^n+2^{2n}=7k\implies 2^{2n}=7k-2^n-1,\;k\in\mathbb Z$$

$\tau(n+1)=\top\implies\;n+1\equiv 2\pmod{3}$ $$1+2^{n+1}+2^{2(n+1)}=1+2\cdot 2^{n}+4\cdot2^{2n}=1+2\cdot2^n+4(7k-2^n-1)\\=28k-2\cdot2^n-3=28k-(2^{n+1}+3)$$ $$7\mid2^{n+1}+3\implies7\mid 2\cdot2^n-4=2(2^n-2)\iff 7\mid2^n-2=2(2^{n-1}-1)\\\iff 7\mid 2^{2n-1}-1$$ $$2^6\equiv 1\pmod{7}\implies 2^{6m}\equiv 1\pmod{7},\;m\in\mathbb N$$ $2n-1=6m\implies 3\mid 2n-1\implies 3\mid 2n+2\implies n\equiv 1\pmod{3}$