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

Question

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.

Answer 1

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)

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

$$4\equiv1\pmod3$$

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

Also,$1\equiv1\pmod3$

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