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

-

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+⋯+$ab^{m−2}$+$b^{m−1}$) (and (8-1)=7), the result follows.

-
Oooooooooooooooooooooooohhh! Thank you! –  user13327 Feb 11 '12 at 22:24

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.

-