0
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.