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?
 A: 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.
A: 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.
A: $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$
A: $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.
A: 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.
A: 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.
A: \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*}
