Prove $4^k - 1$ is divisible by $3$ for $k = 1, 2, 3, \dots$

Question

For example:

$$\begin{align} 4^{1} - 1 \mod 3 &= \\ 4 -1 \mod 3 &= \\ 3 \mod 3 &= \\3*1 \mod 3 &=0 \\ \\ 4^{2} - 1 \mod 3 &= \\ 16 -1 \mod 3 &= \\ 15 \mod 3 &= \\3*5 \mod 3 &= 0 \\ \\ 4^{3} - 1 \mod 3 &= \\ 64 -1 \mod 3 &= \\ 21 \mod 3 &= \\3*7 \mod 3 &= 0\end{align} $$

Define $x = \frac{4^k - 1}{3}$. So far I have:

$$k_1 \to 1 \Longrightarrow x_1 \to 1 \\ k_2 \to 2 \Longrightarrow x_2 \to 5 \\ k_3 \to 3 \Longrightarrow x_3 \to 21 \\ k_4 \to 4 \Longrightarrow x_4 \to 85$$

But then it's evident that

$$4^{k_n} = x_{n+1} - x_n$$

I don't know if this helps, these are ideas floating in my head.

Answer 1

we know that $$4\equiv 1 \mod 3$$ and thus $$4^k\equiv 1^k\equiv 1 \mod 3$$

Answer 2

Hint:

$$4 \equiv 1 \mod 3 \Rightarrow 4^n \equiv 1^n \mod 3 \Rightarrow 4^n \equiv 1 \mod 3$$

Answer 3

4 is congruent to 1 modulo 3, so:

$$4^k - 1 \equiv 1^k - 1 \equiv 0 \mod{3}$$

Answer 4

You may also go about this easily with induction:

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

Answer 5

Another possible proof: Expand $4^k - 1 = (3 + 1)^k - 1$ using the Binomial Theorem.

Answer 6

$4^k-1=(4-1)(4^{k-1}+\cdots+4+1)$.

Answer 7

Use the remainder theorem in the following form :

$$4^k-1=(3+1)^k-1=3L+1^k-1=3L$$

where $L$ is an integer.

Hint:Expand $(3+1)^k$ using the binomial expansion.

Answer 8

Note that $x^k - y^k$ is always divisible by $x-y$. (In fact, $x^k - y^k = (x - y)(x^{k-1} + x^{k-2}y + x^{k-3}y^2 + \cdots + y^{k-1})$ Specialize for $x=4, y=1$.