# Show that k is an odd integer, except when k=2

• Math100

#### Math100

Homework Statement
Another unproven conjecture is that there are an infinitude of primes that are ## 1 ## less than a power of ## 2 ##, such as ## 3=2^{2}-1 ##.
If ## p=2^{k}-1 ## is prime, show that ## k ## is an odd integer, except when ## k=2 ##.
Relevant Equations
None.
Proof:

Suppose for the sake of contradiction that ## p=2^{k}-1 ## is prime
but ## k ## is not an odd integer.
That is, ## k ## is an even integer.
Then we have ## k=2a ## for some ## a\in\mathbb{Z} ##.
Thus ## p=2^{k}-1
=2^{2a}-1
=4^{a}-1. ##
Note that ## 3\mid 4^{n}-1 ## for all ## n\geq1 ##.
This means ## 3 ## divides ## p ##,
and so ## p ## must be ## 3 ##,
because ## p ## is a prime number.
Now we have ## p=2^{k}-1
=3 ##,
which implies that ## 2^{k}=3+1=4 ##,
so ## k=2 ##.
Since ## k\neq2 ##,
it follows that ## p\neq3 ##.
This is a contradiction because p cannot be a composite,
given the fact that ## p=2^{k}-1 ## is prime.
Therefore, if ## p=2^{k}-1 ## is prime,
then ## k ## is an odd integer, except when ## k=2 ##.

You've got to tidy that up!

PeroK said:
You've got to tidy that up!
But how?

Math100 said:
But how?
Review and edit. It's something you need to learn to do.

Math100 said:
But how?
Rule of thumb: write it in a way that convinces yourself, then delete all but every third row Concentrate on the crucial lines:

E.g.: Assume ##p=2^k-1## is prime and assume ##k=2m >3.##

This gets you directly to your fifth line and everything is said, including the contradictional assumption.

Now you get ##p=4^m-1=(4-1)\cdot (\ldots) ## and so on.

You get the dots by using long division on ##(4^m-1):(4-1)## or in general ##(x^m-1):(x-1)## which is a valuable exercise anyway, since the formula is often used, and long division a method you should know.

• Math100
Math100 said:
Homework Statement:: Another unproven conjecture is that there are an infinitude of primes that are ## 1 ## less than a power of ## 2 ##, such as ## 3=2^{2}-1 ##.
If ## p=2^{k}-1 ## is prime, show that ## k ## is an odd integer, except when ## k=2 ##.
Relevant Equations:: None.

Proof:

Suppose for the sake of contradiction that ## p=2^{k}-1 ## is prime
but ## k ## is not an odd integer.
That is, ## k ## is an even integer.
Then we have ## k=2a ## for some ## a\in\mathbb{Z} ##.
Thus ## p=2^{k}-1
=2^{2a}-1
=4^{a}-1. ##

$2^{2a} - 1$ is a difference of squares. Do you recall that $x^2 - y^2 = (x+y)(x - y)$?

• Math100
pasmith said:
$2^{2a} - 1$ is a difference of squares. Do you recall that $x^2 - y^2 = (x+y)(x - y)$?
Yes.

fresh_42 said:
Rule of thumb: write it in a way that convinces yourself, then delete all but every third row Concentrate on the crucial lines:

E.g.: Assume ##p=2^k-1## is prime and assume ##k=2m >3.##

This gets you directly to your fifth line and everything is said, including the contradictional assumption.

Now you get ##p=4^m-1=(4-1)\cdot (\ldots) ## and so on.

You get the dots by using long division on ##(4^m-1):(4-1)## or in general ##(x^m-1):(x-1)## which is a valuable exercise anyway, since the formula is often used, and long division a method you should know.
So you're saying that after fifth line in my proof, I should revise it into another method?

I only said what I thought. It is a reflex if I see ##x^m -1.## It is the formula that is used for interest rates:
$$\sum_{k=0}^{m-1} r^k = \dfrac{r^m-1}{r-1}$$
As I said, this formula and the method of long division are valuable tools.

A faster method has been given to you in post #6.

Your method is the same, only that you did not provide evidence for ##3\,|\,4^m-1.## My method and the one in post #6 provide this evidence. Other methods are a proof by induction or modular arithmetics:
$$4^m-1 \mod 3 \equiv (4\mod 3)^m-1 =1^m-1=0 \Longrightarrow 3\,|\,4^m-1$$

Once you have ##3\,|\,p## you automatically have ##3=p## since ##p## is prime and so ##k=2##, contradicting the assumption.

All you have written can be compressed into that line.

• Math100
I wouldn't write this as a proof by contradiction. You derive a contradiction. It's a problem here because you want to derive a contradiction from:

Math100 said:
Suppose for the sake of contradiction that p=2k−1 is prime
but k is not an odd integer.
You never derive a contradiction to the complete statement.

It would be much simpler to start with "k is even and p = prime)" and derive k=2 from that.

• PeroK