4
$\begingroup$

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?

  • 0
    Thank you all, I believe I understand it now :)2012-02-11

7 Answers 7

4

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.

  • 0
    I think I understand now. She was wrapping all of the remaining stuff as "k" Thank you very much!2012-02-11
1

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.

  • 1
    Observe that $7| 8 - 1.$2012-02-11
1

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

1

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

  • 0
    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.2015-10-16
1

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.

  • 0
    No mathematical induction whatsoever is needed here.2012-02-11
1

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.

-1

\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*}

  • 0
    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.2015-10-16