# Use mathematical induction to prove that for all integers $n \ge 2$, $2^{3n}-1$ is not prime

I had a homework due yesterday with this problem.

The TA did the problem last week in discussion but I didn't understand it.

She pulled out a $7k$ almost immediately, and I have no idea from where.

It was like, it wasn't prime if $2^{3n}-1$ was 7 times some constant. I understand that that would make $2^{3n}-1$ not prime, but I don't understand how she just used "7".

Where did she get that from? I was thinking, maybe it was like $2^3 \cdot 2^n-1$... which is $8 \cdot 2^n-1$... but you can't just do $8-1$. How?

-
Remember that $a^m - b^m = (a - b)(a^{m - 1} + a^{m - 2}b + \cdots + ab^{m - 2} + b^{m -1})$. Here $m$ should probably be $n + 1$. What are $a$ and $b$? – Dylan Moreland Feb 11 '12 at 19:04
Hint: $7$ divides $8^n-1$ for the same reason $10$ divides $11^n - 1$, i.e. by casting nines (here sevens) or the Factor Theorem, or modular arithmetic, etc. – Math Gems Feb 11 '12 at 19:17
Thank you all, I believe I understand it now :) – user13327 Feb 11 '12 at 22:26

I’m sure that she used the following factorization

\begin{align*} 2^{3n}-1&=(2^3)^n-1\\ &=8^n-1^n\\ &=(8-1)(8^{n-1}\cdot 1^0+8^{n-2}\cdot 1^1+\dots+8^2\cdot 1^{n-3}+8^1\cdot 1^{n-2}+8^0\cdot 1^{n-1}\\ &=7(8^{n-1}+8^{n-2}+\dots+8^2+8+1)\\ &=7\sum_{k=0}^{n-1}8^k\;, \end{align*}

which as Dylan Moreland pointed out is a special case of \begin{align*}a^n-b^n&=(a-b)(a^{n-1}b^0+a^{n-1}b^1+\dots+a^1b^{n-2}+a^0b^{n-1})\\ &=(a-b)\sum_{k=0}^{n-1}a^kb^{n-1-k}\end{align*}\;.

This is really just the formula for the sum of a finite geometric series in disguise:

\begin{align*} \sum_{k=0}^{n-1}a^kb^{n-1-k}&=b^{n-1}\sum_{k=0}^{n-1}\left(\frac{a}b\right)^k\\ &=b^{n-1}\frac{\left(\frac{a}b\right)^n-1}{\frac{a}b-1}\\ &=\frac{\frac{a^n}b-b^{n-1}}{\frac{a-b}b}\\ &=\frac{a^n-b^n}{a-b}\;, \end{align*}

and multiplying through by $a-b$ yields the factorization formula.

-
I think I understand now. She was wrapping all of the remaining stuff as "k" Thank you very much! – user13327 Feb 11 '12 at 22:26

We know that $$8\equiv 1 {\rm mod}\, 7.$$ The properties of modular arithmetic tell you that if you have a nonnegative integer $n$, $$8^n\equiv 1^n\, {\rm mod}\, 7.$$ consequently we have for any nonnegative integer, $$8^n\equiv 1 {\rm mod}\, 7, \qquad n\ge 0.$$

EDIT: I can add an even easier induction argument. We know that $7| 8^0 - 1$. Now assume that $8^n = 7Q + 1$, where $Q$ is a nonnegative integer. Then $$8^{n+1} = 8\cdot 8^n = 8(7Q + 1) = 7(8Q + 1) + 1.$$ Since $8Q + 1$ is an integer, we have established our claim.

-
I'm sorry for being so dense, but I don't see how 8≡1mod7. Wouldn't 1 mod 7 be what's remaining after you have clean divisions of 7, which is 1? Maybe I'm not understanding how mod works. I thought I did... – user13327 Feb 11 '12 at 22:22
Observe that $7| 8 - 1.$ – ncmathsadist Feb 11 '12 at 23:53

$1.~$ $n=2 \Rightarrow 2^6-1=63$ , so it isn't prime

$2.~$ suppose that $~2^{3n}-1~$ isn't prime

$3.~$ $2^{3(n+1)}-1=2^3\cdot 2^{3n}-1=7\cdot 2^{3n}+2^{3n}-1=7\cdot 2^{3n}+(2^3)^n-1$

Note that : $a^n-1=(a-1)(a^{n-1}+a^{n-2}+\cdots +1)$ , so :

$2^{3(n+1)}-1=7\cdot 2^{3n}+(2^3-1)((2^3)^{n-1}+(2^3)^{n-2}+\cdots +1)=$

$=7\cdot(2^{3n}+(2^3)^{n-1}+(2^3)^{n-2}+\cdots +1)$ , therefore :

$2^{3(n+1)}-1~$ is a composite number , so it follows that :

$2^{3n}-1$ is composite for all $n\geq 2$

-

Note that $2^{3n}$ is not $2^3\cdot2^n$ but $(2^3)^n=8^n$, hence your TA applied the polynomial identity $x^n-1=(x-1)(x^{n-1}+\cdots+x+1)$ to $x=8$, and deduced that $2^{3n}-1=7k$ with $k=x^{n-1}+\cdots+x+1$ and $x=8$.

To deduce from this that $2^{3n}-1$ is composite, one still must check that $7$ and $k$ are not trivial factors, that is, that $k\ne1$. But for every $n\geqslant2$, $k\geqslant x+1=9\gt1$, hence the proof is over.

-
No mathematical induction whatsoever is needed here. – Did Feb 11 '12 at 19:30

Suppose that we are really going to do it by induction, perhaps because a homework exercise specifies that we must. There are quite a few better ways than induction for solving this problem, most of which you will learn from the other answers. But let's do induction.

We experiment a bit. Start say at $n=1$, or even that mathematicians' favourite, $n=0$.

If $n=1$, then $2^{3n}=7$. Let $n=2$. Then $2^{3n}=63$. Note that $63$ is divisible by the primes $3$ and $7$. Let $n=3$. Then $2^{3n}-1=511$. But $511=7\times 73$. All our numbers so far are divisible by $7$. Let $n=4$. Then $2^{3n}-1=4095$. Is it divisible by $7$? The calculator says yes.

So maybe all of our numbers are divisible by $7$. Since all the numbers for $n\ge 2$ are $>7$, this will show that if $n\ge 2$, then $2^{3n}-1$ is composite. So we try to prove, by induction on $n$, that $7$ divides $2^{3n}-1$ for every positive integer $n$.

Certainly it is true at $n=1$. Suppose that we know that for a particular $k$, $2^{3k}-1$ is divisible by $7$. Can we prove that $2^{3(k+1)}-1$ is divisible by $7$?

Note that $$2^{3(k+1)}-1=(2^{3k}-1)+(2^{3(k+1)} -2^{3k}).$$

By the induction hypothesis, $2^{3k}-1$ is divisible by $7$. If we can prove that $2^{3(k+1)} -2^{3k}$ is divisible by $7$, we will be finished.

Note that $$2^{3(k+1)} -2^{3k}=2^{3k+3}-2^{3k}=2^{3k}(2^3-1)=7(2^{3k}),$$ so we are finished.

-

$2^{3n}=(2^{3})^{n}$, not $8$ times $2^{n}$. So, $2^{3n}-1=(8^{n}-1)$.

$(8^{n}-1)=(8^{n}-1^{n})$. Then since $a^{m}−b^{m}=(a−b)(a^{m−1}+a^{m−2}b+ \cdots + ab^{m−2}+ b^{m−1})$ (and $(8-1)=7$), the result follows.

-
Oooooooooooooooooooooooohhh! Thank you! – user13327 Feb 11 '12 at 22:24
To write $2^{3n} = (2^3)n$, write the entire expression 2^{3n} = (2^3)^n between dollar signs. If you right click on an equation, then select Show Math As LaTeX Commands, you can see how I edited your equations. – N. F. Taussig Oct 16 '15 at 9:53

\begin{align*} 2^{3n}−1 & =(2^3)^n−1\\ & =8^n−1^n\\ & =(8−1)(8^{n−1} \cdot 1^0+8^{n−2} \cdot 1^1+⋯+8^2 \cdot 1^{n−3}+8^1 \cdot 1^{n−2}+8^0 \cdot 1^{n−1})\\ & =7\sum(8^{n−1}+8^{n−2}+⋯+8^2+8+1)\\ & =7\sum_{k=0}^{n−1} 8^k \end{align*}

\begin{align*} 2^{3n}−1 & =(2^3)^n−1\\ & = 8^n−1^n\\ & = (8−1)(8^{n−1} \cdot 1^0+8^{n−2}\cdot 1^1+ \cdots +8^2⋅1^{n−3}+ 8^1 \cdot 1^{n−2}+ 8^0⋅1^{n−1})\\ & = 7(8^{n−1}+8^{n−2} + \cdots +8^2+8+1)\\ & = 7\sum_{k=0}^{n−1}8^k \end{align*}

-
Welcome to Maths SE. 2 things: I have reformatted your post but the input interpretation may be wrong so in future use this to learn how to format via $LaTeX$ and secondly, if someone gives an answer to a question that you ask that is useful to you, don't forget to tick it. All the best. – BLAZE Oct 16 '15 at 8:59
Please check my edits to see if I captured what you intended to write. Your unformatted work was difficult to interpret. You can make edits by clicking on edit. Consulting the tutorial to which BLAZE linked will help you understand the formatting. – N. F. Taussig Oct 16 '15 at 9:36