Prove that ## n ## must be a power of ## 2 ##

[Math100]

Homework Statement

Prove that if $2^{n}+1$ is prime, then $n$ must be a power of $2$.

Relevant Equations

None.

Proof:

Suppose for the sake of contradiction that $2^{n}+1$ is prime but $n$ is not a power of $2$.
Then $n=ks$ for some $k\in\mathbb{Z}$ where $1\leq k<n$ and $s$ is an odd prime factor.
This means $(a-b)\mid (a^{q}-b^{q})$.
Let $a=2^{k}, b=-1$ and $q=s$.
Observe that $(2^{k}+1)\mid (2^{ks}+1)\implies (2^{k}+1)\mid (2^{n}+1)$.
Since $k<n$, it follows that $2^{n}+1$ is not prime, which is a contradiction.
Therefore, if $2^{n}+1$ is prime, then $n$ must be a power of $2$.

 

[fresh_42]

Homework Statement:: Prove that if $2^{n}+1$ is prime, then $n$ must be a power of $2$.
Relevant Equations:: None.

Proof:

Suppose for the sake of contradiction that $2^{n}+1$ is prime but $n$ is not a power of $2$.
Then $n=ks$ for some $k\in\mathbb{Z}$ where $1\leq k<n$ and $s$ is an odd prime factor.
This means $(a-b)\mid (a^{q}-b^{q})$.
Let $a=2^{k}, b=-1$ and $q=s$.
Observe that $(2^{k}+1)\mid (2^{ks}+1)\implies (2^{k}+1)\mid (2^{n}+1)$.
Since $k<n$, it follows that $2^{n}+1$ is not prime, which is a contradiction.
Therefore, if $2^{n}+1$ is prime, then $n$ must be a power of $2$.

Looks good.

I wouldn't say "this means" if you say something that is simply always true. It doesn't come from another truth that "this means" suggests. And you should write $p$ instead of $s.$ Without any reason. It is just so that $p,q,r$ are primes and $s,t,u,v$ ordinary integers - mostly.

From $(2^{k}+1)\mid (2^{n}+1)$ and $2^{n}+1$ prime, we can conclude that either $k=n$ which contradicts $s>2$ or $k=0$ which also contradicts $s>2.$

Can you tell where the proof would go wrong if $s=2^r$ were a power of $2?$

 

[Math100]

Looks good.

I wouldn't say "this means" if you say something that is simply always true. It doesn't come from another truth that "this means" suggests. And you should write $p$ instead of $s.$ Without any reason. It is just so that $p,q,r$ are primes and $s,t,u,v$ ordinary integers - mostly.

From $(2^{k}+1)\mid (2^{n}+1)$ and $2^{n}+1$ prime, we can conclude that either $k=n$ which contradicts $s>2$ or $k=0$ which also contradicts $s>2.$

Can you tell where the proof would go wrong if $s=2^r$ were a power of $2?$

That $s=2^r$ would go wrong in the proof, because then $s$ wouldn't be an odd prime factor.

 

[fresh_42]

That $s=2^r$ would go wrong in the proof, because then $s$ wouldn't be an odd prime factor.

So? Why can't I get the same contradiction if $s=2^r?$

 

[Math100]

So? Why can't I get the same contradiction if $s=2^r?$

Is it because $(2^{k}+1)\mid (2^{k\cdot q}-1)$?

 

[Math100]

Also, if $s=2^{r}$, then we have $n=k\cdot 2^{r}$ where $k\geq 1$. This implies $n=1\cdot 2^{r}$.

 

[Math100]

Or $n=2^{r}$, which fails the intention of using proof by contradiction.

 

[fresh_42]

Is it because $(2^{k}+1)\mid (2^{k\cdot q}-1)$?

Yes. It is well hidden here. We don't know anything about $2^{n}-1.$ We only have that $2^n+1$ is prime.

Or $n=2^{r}$, which fails the intention of using proof by contradiction.

The intention is irrelevant here. We know that $2^{(2^2)}+1=2^4+1=17$ is prime. This means such prime numbers exist. They are called Fermat numbers, and in case they are prime Fermat primes:
https://en.wikipedia.org/wiki/Fermat_number

 

[Math100]

I've never heard of Fermat numbers before.

 

[fresh_42]

I've never heard of Fermat numbers before.

The Mersenne primes are far more interesting:
https://en.wikipedia.org/wiki/Mersenne_prime

... except you want to construct with compass and straight edge alone regular inscribed polygons in a circle. Fermat numbers allow such polygons. (Gauß constructed a 17-gon with compass and ruler.)

 

[Math100]

The Mersenne primes are far more interesting:
https://en.wikipedia.org/wiki/Mersenne_prime

... except you want to construct with compass and straight edge alone regular inscribed polygons in a circle. Fermat numbers allow such polygons. (Gauß constructed a 17-gon with compass and ruler.)

Are Mersenne primes infinite?

 

[fresh_42]

Are Mersenne primes infinite?

Are there infinitely many Mersenne primes? Based on plausible heuristics, one assumes that there are about $c\cdot \ln(x)$ many Mersenne prime numbers $M_{p}$ with $p<x$ (for a positive constant $c$). If this were the case, then there would indeed be infinitely many Mersenne primes.

We do not know for sure.

We do not even know whether there are infinitely many Mersenne numbers, that are not prime.

Both answers are probably a 'yes'. But they are open problems.

 

[Math100]

Are there infinitely many Mersenne primes? Based on plausible heuristics, one assumes that there are about $c\cdot \ln(x)$ many Mersenne prime numbers $M_{p}$ with $p<x$ (for a positive constant $c$). If this were the case, then there would indeed be infinitely many Mersenne primes.

We do not know for sure.

We do not even know whether there are infinitely many Mersenne numbers, that are not prime.

Both answers are probably a 'yes'. But they are open problems.

Will you be successfully solve those open problems?

 

[fresh_42]

Will you be successfully solve those open problems?

Probably not. I am no number theorist (and too old). If one of our generations (= today) can solve it, then it would be Terence Tao. It is the kind of problem that he likes.

 

[Math100]

Probably not. I am no number theorist (and too old). If one of our generations (= today) can solve it, then it would be Terence Tao. It is the kind of problem that he likes.

I thought he's interested in combinatorics. I didn't know that he likes this kind of problem.

 

[fresh_42]

I thought he's interested in combinatorics. I didn't know that he likes this kind of problem.

He has a blog
https://terrytao.wordpress.com/2020...ure-for-sufficiently-high-degree-polynomials/
and a newsletter where you can find out what he is doing.