Prove $4^n-1$ is divisible by $3$, for all $n\in\Bbb N$?

Question

Prove $4^n-1$ is divisible by $3$, for all $n\in\Bbb N$?

I started by assuming there exists some $k\in\Bbb N$ s.t. $4^n-1=3k\iff \dfrac{4^n}3-\dfrac 13=k$, so for $k$ to be a natural number, $4^n\equiv 1\mod 3$ must be true, but this tells us no new information, and I don't know how to follow from there. Any help would be appreciated.

Answer 1

With only middle school tools: $$4^n-1=4^n-1^n=(\underbrace{4-1}_{\textstyle 3})(4^{n-1}+4^{n-2}+\dots +4+1).$$

Answer 2

Note that

$$4^n-1\equiv(1)^n-1\equiv 0 \mod 3$$

Answer 3

Or

$$ 4^n-1 = (4-1)(4^{n-1}+4^{n-2}+...+4^2+4+1)$$

or

$$4^n-1 = (3+1)^n-1 = \underbrace{{n\choose 0}3^n+ {n\choose 1}3^{n-1}+...+{n\choose n-1}3}_{3k}+ 1-1$$

Answer 4

The simples way is using modular arithmetic, under which

$$4^n-1\equiv 1^n-1\equiv 1-1\equiv 0\mod 3$$

---

Another way is to write

$$4^n = (3+1)^n$$

and use the binomial formula to get

$$(3+1)^n = 3^n +{n\choose 1} 3^{n-1} + \cdots + {n\choose n-1} 3^1 + 1\\=3\left(3^{n-1} +{n\choose 1} 3^{n-2} + \cdots + {n\choose n-1} 3^0 \right) + 1$$

---

A third way would be to use induction. The step $n=1$ is simple, as $4^n-1=4-1=3$ is clearly divisible by $3$.

The induction step uses the fac that since $4^n-1$ is divisible by $3$, there exists some $k$ such that $4^n-1=3k$, therefore $4^n=3k+1$ and

$$4^{n+1} - 1=4\cdot 4^n - 1 = 4\cdot (3\cdot k + 1) - 1 = 12 k + 3 = 3(4k+1)$$

which is divisible by $3$.

Answer 5

$$4=3+1\implies 4^n \equiv 1^n \pmod 3$$

Answer 6

$$4^n-1=(2^n)^2-1=(2^n+1)(2^n-1)$$
One of $2^n+1,2^n-1$ must be divisible by $3$, because the contrary implies that $2^n$ is divisible by $3$.

Answer 7

Alternatively, with induction: assuming $4^n-1\equiv 0 \mod 3$ is true, we will show for $n+1$: $$4^{n+1}-1=4\cdot (4^n-1)+4-1\equiv 0 \mod 3.$$