# Simple proof; Show that $(4^n - 1)$ is divisible by 3 (Guided proof task)

• First part of the task is just to show that $(4^n-1)$ actually is divisible by 3 for n=1,2,3,4. No problem.
• Second step: is to show that $(4^n -1) = (2^n-1)(2^n+1)$ No problem, just algebra.

• Third step is to explain that $(2^n-1)$,$2^n$,$(2^n+1)$ is three consecutive numbers. And that only one is divisible by three.
$2^n$ has two as a factor and is not divisible by 3. It can't be even. That leaves $(2^n-1)$ and $(2^n+1)$. The one with 3 as a factor seems to be random dependent on n.

• Fourth step, tie it all together.
Now, I'm not sure if I'm suppose to dig deeper into which of them is actually divisible by 3. Or has 3 as a factor. But knowing that one of them at the time (dependent on n) has indeed 3 as a factor implies that, in respect to the second step, 3 is a factor of $(4^n -1)$.

Is this all there is to it? Keep in mind that this is a really beginners proof task, not very formal. It's slightly funny going back to high school math after being scared to death by logic and descrete math at university-level. I just expect everything thing to be super complex.

-
$4^2-1=16-1=15$, unless you are talking about something else – Amr Nov 22 '12 at 15:23
@Amr yes, 15 is divisible by 3. – Algific Nov 22 '12 at 15:24
Yeap, that is all there is to it, your proof is complete. In the third step, you don't have to dig deeper into which of them is divisible by 3, it is enough to show that $2^n$ is not divisible by 3. However, if you are interested then for $n$ odd : $2^n + 1 = (2 + 1)(2^{n - 1} - \ldots + 1)$ and hence divisible by 3. For $n$ even($n = 2k$), $2^n - 1 = 4^k - 1 = (4 - 1)(4^{k - 1} + \ldots + 1)$ and hence divisible by 3. – TenaliRaman Nov 22 '12 at 15:29
@Algific I would suggest that you add your proof as an answer to this post. Be as complete as possible. – TenaliRaman Nov 22 '12 at 15:35

Once you have show that $4^n-1=(2^n+1)(2^n-1)$, and one of the two factors is divisible by three, you have got that $3$ divides $4^n-1$.

If $2^n-1$ is divisible by three, write it as $3k$ then $4^n-1=3k(2^n+1)$ and therefore it is divisible by three (you should figure out how to write the argument in full).

The other case, where $2^n+1$ is the one divisible by three is symmetric, but you should write the details for that case as well, to practice your writing.

-
+1, if for nothing else but for making to me a rather good point in the above answer's comments. – DonAntonio Nov 22 '12 at 16:39
This is closest to what is required as an answer. This is an exam task, and I found the guide used by teacher when reviewing the exam. And this is more than good enough. – Algific Nov 23 '12 at 18:20
@Algific: Wait, you want to tell me that you asked here a question from a home exam?? – Asaf Karagila Nov 23 '12 at 19:24

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

-
Waaaaaaaay easier. +1 – DonAntonio Nov 22 '12 at 15:25
@DonAntonio: Way easier, yes. But the question has a guided proof. Usually when a teacher chooses a certain method to guide the student through it is because of a certain idea behind the method. Finding a shorter proof is always fun, but not always pedagogically correct. In some sense, this does not even answer the question. – Asaf Karagila Nov 22 '12 at 15:53
@AsafKaragila, I agree with you that a guided question must be answered....following the guide, for whatever purposes the teacher may have. OTOH, giving different ways to prove something can help, and it usually does, to put things into perspective and/or look differently to things. Finally, I don't agree with you that Amr's answers doesn't even answer the question "in some sense" (which one?): it very precisely, formally and exactly does. – DonAntonio Nov 22 '12 at 15:56
@DonAntonio: No, the question asks for help with the guidance, and Amr's sleek and almost obvious argument has nothing to do with the guidance. All that this answer does is to reassure that the claim we want to prove is correct. Just like if you ask me to pass the bread and I will give you soup, because "soup is good food". :-) – Asaf Karagila Nov 22 '12 at 16:34
I agree with Asaf. Actually I only had a very quick look at the question and I thought that this was his own attempt to prove that $3|4^n-1$. – Amr Nov 22 '12 at 16:38

If $n$ is a positive integer,

using congruence formula, $4\equiv 1\pmod 3\implies 4^n\equiv 1^n\pmod 3\implies 4^n-1\equiv1-1\pmod 3$

Alternatively using binomial expansion, $4^n- 1=(1+3)^n-1$ $=(1+\binom n13+\binom n23^2+\cdots+\binom n{n-1}3^{n-1}+3^n)-1$ $=\sum_{1\le r\le n}3^r$ is clearly divisible by $3$

-

One of any three consecutive numbers is divisible by $3$. Now, $2^n-1$, $2^n$, and $2^n+1$ are consecutive, and $3$ can't divide $2^n$, so it must divide one of the others and hence their product.

-
More generally, if x divides y, then x divides the product of y and anything else. – Doug Spoonwood Nov 23 '12 at 3:03

we can prove that $$3|(4^n-1),n\geq 1$$ using mathematical induction, for $n=1$ $$3|(4^1-1)$$ the statement is true. Suppose that statement is true for $n=k$ i.e $$3|(4^k-1)$$ now we prove for $n=k+1$ $$4^{k+1}-1=4^k4-1=3\times 4^k+(4^k-1)=$$ obviousley $3\times 4^k$ can be divided by $3$ and $4^k-1$ is divisible by $3$ by assumption.

-

You can prove it very quickly by induction

1. the expression is true for $n=0$, $n=1$, $n=2$ (you can check by hand)
2. if the expression is true for $n$, then the expression is true for $n+1$.

Proof : $4^{(n+1)}-1 = 4\cdot (4^n-1)+3$, the first term is divisble by $3$ (step 2) and the second ($3$) also.

-
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Nov 22 '12 at 16:25