# How can I prove that $3| (4^n - 1)$

How can I prove that $$3| (4^n - 1)$$ or 3 divides $$4^n - 1$$?

I have started it by induction, so the basis works and I assumed the induction hypothesis $$3| (4^n - 1)$$ but do not know how to use it to simplify $$3| (4^{(n + 1)} - 1)$$. could anyone help me to show this?

• $4^n-1=(4-1)(4^{n-1}+4^{n-2}+...+4+1)$ – logarithm May 13 at 11:08

To prove by that the next term in the sequence $$4^{n+1}-1$$ is also divisible by $$3$$, it makes sense to prove that the difference is divisible by $$3$$. The difference between two consecutive terms is $$(4^{n+1}-1)-(4^n-1)=4^{n+1}-4^n=4^n(4-1).$$

Use the identity $$q^{n+1}-1 = (1+q+\ldots+q^n)(q-1)$$.

For $$q=4$$, we get $$4^{n+1}-1 = a\cdot (4-1)=3a$$ for some number $$a$$.

To prove by induction you can do this: $$4^{n+1}-1=4^{n+1}-4+4-1=4(4^n-1)+3.$$ Hence, $$3\lvert 4^{n+1}-1$$.

$$n=0$$√, let $$n \ge 1$$.

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

$$\sum_{k=0}^{n}\binom{n}{k}3^{n-k}1^k-1=$$

$$\sum_{k=0}^{n-1}\binom{n}{k}3^{n-k} +1-1$$;

The binomial expression is divisible by $$3$$.

$$4=3+1$$ So: $$4^n-1=(3+1)^n-1$$ Which by FOIL, has all but one term of the power expansion divisible by 3, leaving $$1^n=1$$ and $$1-1=0$$ This shows regardless of natural number n, $$3\mid 4^n-1$$