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

  • Thread starter Math100
  • Start date
  • Tags
    Power
In summary: Combinatorics is over. And Tao is not 1 person but 2. They are both interested in this problem. They are both interested in this problem.Yes.
  • #1
Math100
750
201
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 ##.
 
Physics news on Phys.org
  • #2
Math100 said:
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?##
 
  • Like
Likes Math100
  • #3
fresh_42 said:
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.
 
  • #4
Math100 said:
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?##
 
  • #5
fresh_42 said:
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) ##?
 
  • #6
Also, if ## s=2^{r} ##, then we have ## n=k\cdot 2^{r} ## where ## k\geq 1 ##. This implies ## n=1\cdot 2^{r} ##.
 
  • #7
Or ## n=2^{r} ##, which fails the intention of using proof by contradiction.
 
  • #8
Math100 said:
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.
Math100 said:
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
 
  • Love
Likes Math100
  • #9
I've never heard of Fermat numbers before.
 
  • #10
Math100 said:
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.)
 
  • Informative
Likes Math100
  • #11
fresh_42 said:
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?
 
  • #12
Math100 said:
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.
 
  • Informative
Likes Math100
  • #13
fresh_42 said:
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?
 
  • #14
Math100 said:
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.
 
  • Haha
Likes Math100
  • #15
fresh_42 said:
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.
 

1. What does it mean for a number to be a power of 2?

A number is considered to be a power of 2 if it can be written as 2 to the power of some integer, meaning it is the product of 2 multiplied by itself a certain number of times. For example, 8 is a power of 2 because it can be written as 2 to the power of 3 (2 x 2 x 2).

2. Why is it important to prove that a number is a power of 2?

Proving that a number is a power of 2 can be useful in various mathematical and scientific applications. For example, it can help in understanding patterns in data or in designing efficient algorithms for computer programs.

3. How do you prove that a number is a power of 2?

One way to prove that a number is a power of 2 is by showing that it can be written as 2 to the power of some integer. This can be done through mathematical induction, where you show that the statement is true for the base case (usually 2) and then prove that if it is true for any integer n, it is also true for n+1.

4. Can a number be a power of 2 if it is not an integer?

No, a number must be an integer to be considered a power of 2. This is because raising a number to a non-integer power will result in a non-integer value, and thus cannot be a power of 2.

5. Are there any other ways to prove that a number is a power of 2?

Yes, there are other methods such as using logarithms or binary representation. However, these methods may not be as straightforward as using mathematical induction and may require a deeper understanding of mathematical concepts.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
779
  • Precalculus Mathematics Homework Help
Replies
8
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
898
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
14
Views
887
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
Back
Top