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

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

 

[PeroK]

You've got to tidy that up!

 

[Math100]

You've got to tidy that up!

But how?

 

[PeroK]

But how?

Review and edit. It's something you need to learn to do.

 

[fresh_42]

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.

 

[pasmith]

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]

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

Yes.

 

[Math100]

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?

 

[fresh_42]

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.

 

[willem2]

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:

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.