# Prove that $4^n+ 1$ is not divisible by $3$

For all integers $n \ge 0$, prove that the value $4^n + 1$ is not divisible by 3.

I need to use Proof by Induction to solve this problem. The base case is obviously 0, so I solved $4^0 + 1 = 2$. 2 is not divisible by 3.

I just need help proving the inductive step. I was trying to use proof by contradiction by saying that $4^n + 1 = 4m - 1$ for some integer $m$ and then disproving it. But I'd rather use proof by induction to solve this question. Thanks so much.

I think that if you need to use induction, instead of proving "$4^n+1$ is not divisible by $3$", you should prove the more specific "$4^n+1$ has remainder $2$ when divide by $3$".

$$4^n+1=3k+2\implies4^n=3k+1\implies4^{n+1}=12k+4$$ $$\implies4^{n+1}+1=12k+5\implies4^{n+1}+1=3(4k+1)+2$$

Induction step:

$$4^{n+1}+1=3\cdot 4^n+4^n+1\equiv4^n+1\mod 3$$

By the way, by recurrence,

$$4^n\equiv1\mod3,$$ $$4^n+1\equiv2\mod3,$$ $$4^n+2\equiv0\mod3.$$

• Inductive step* – user236182 Aug 31 '16 at 19:02

The statement is true for $n=0$. Now, let it be true for $n=k$. Also, if possible, let it be false for $n=k+1$. Then, $4^{k+1} \equiv -1 \pmod{3} \implies 4 \cdot 4^k \equiv -1 \pmod{3} \implies 4^k \equiv -4 \pmod{3} \equiv -1 \pmod{3}$ (since $4^{-1} \equiv 4 \pmod{3}$). So, $3 \mid 4^k+1$, a contradiction. Hence, it's true for $n=k+1$. Hence the proof.

Hint: Suppose $3$ does not divide $4^{n}+1$ for some $n\in\{0,1,\ldots\}$. If $3$ divides $4^{n+1}+1$, $$0\equiv4^{n+1}+1\equiv4^{n}4+1\equiv \text{ } ?\text{ (mod }3\text{)}.$$ (I have left out a step which you should fill in to arrive at a contradiction)

Your induction step could look like this:

Suppose $4^n + 1 \equiv 1\pmod{3}$, then $4^n \equiv 0\pmod{3}$, so $$4^{n+1} + 1 \equiv 4(4^n) + 1 \equiv 1\pmod{3}$$ and if $4^n+1 \equiv 2\pmod{3}$, then $4^n \equiv 1\pmod{3}$, so $$4^{n+1} +1 \equiv 4+1\pmod{3} = 2\pmod{3}$$

• Inductive step* – user236182 Aug 31 '16 at 19:04

Hint: $4^n-1=4^n-1^n$ is divisible by $3$ (why?).

• Because $$4^n-1^n=(4-1)\left(4^{n-1}+4^{n-2}+\cdots+4^0\right)$$ More generally, for $a,b\in\mathbb R$, $n\in\mathbb Z^+$ we have $$a^n-b^n=(a-b)\left(a^{n-1}b^0+a^{n-2}b^1+\cdots+a^0 b^{n-1}\right)$$ It's not obvious that the OP knows this fact and knowing this would be useful for the OP in the future. There are other reasons this is true of course, e.g. the factor theorem, the binomial theorem, etc. – user236182 Aug 31 '16 at 18:54

I can see a superset proof: If you transform it into $2^{2n} + 1$, it's a well known proof that shows it's not divisible by 3. (maybe the original answer gave it away too much...)

$$4\equiv1\pmod3$$

$$\implies4^n\equiv1^n\pmod3$$

Also,$1\equiv1\pmod3$

Adding,$$4^n+1\equiv2\pmod3$$

Hint $\ \ f_n =\, 4^n\!+1\ \Rightarrow\,\ f_{n+1}\!-f_n =\! \overbrace{\color{#c00}3\cdot 4^n}^{\large 4^{\Large n+1}-4^{\Large n} }\!$ so $\,\ \color{#c00}3\mid f_{n+1}\!\iff \color{#c00}3\mid f_n$

Remark  Said $\,{\rm mod}\ 3\!:\ f_{n+1}\equiv f_n\$ so by induction $\,f_n\equiv f_0 \equiv 2,\$ so $\ f_n\not\equiv 0$

But using congruences it is clearer to prove by induction $\,4\equiv 1\,\Rightarrow\, 4^n\equiv 1^n\equiv 1\,$ (special case of Congruence Power Rule).  Then $\,f_n = 4^n+1\equiv 1+1\equiv 2\,$ by the Congruence Sum Rule.