How to Find an Answer to 2^n + 1 Prime Question

[Math100]

Homework Statement

An unanswered question is whether there are infinitely many primes that are $1$ more than a power of $2$, such as $5=2^2+1$. Find two more of these primes.

Relevant Equations

None.

Proof:

$17=2^4+1$

Now I'm stuck. How should I find the correct answers to this problem?

 

[Klystron]

This question appears to be a variation on Mersenne primes, adding one to 2ⁿ instead of subtracting.

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.

 

[Office_Shredder]

Just try literally the next power of 2

 

[Math100]

So $2^{8}+1=257$.

 

[Math100]

But how should I explain these two prime numbers in my proof? What should I start with?

 

[Office_Shredder]

Are you asking how to explain how you found these, or how to prove they are prime numbers.

You probably don't need to explain how you came up with them, or you can just write "I tried some examples and here's what I found" if you're worried about a particularly harsh grader.

 

[Math100]

Are you asking how to explain how you found these, or how to prove they are prime numbers.

You probably don't need to explain how you came up with them, or you can just write "I tried some examples and here's what I found" if you're worried about a particularly harsh grader.

So do I just show my work and answer for this problem without proof?

$17=2^{4}+1$
$257=2^{8}+1$

 

[Office_Shredder]

So do I just show my work and answer for this problem without proof?

$17=2^{4}+1$
$257=2^{8}+1$

I don't know what your grader is expecting, but my guess is this is fine. If you think you need to be very rigorous on proving the primeness, it's not that hard. I'll do 17 for you so you can get the feel for it.

Here's a useful lemma: if $n$ is a composite number, then there exists a prime $p$ such that $p|n$ and $p^2 \leq n$
Proof: factor $n=mk$. One of $m$ or $k$ is smaller (or they are equal) wlog let it be $k\leq m$. Then $k^2\leq km=n$. And there must be some prime $p$ that divides $k$, and hence divides $n$. If $k=pq$, then $p^2 \leq k^2 \leq n$.

Since $5^2 > 17$, if 17 is composite it must be divisible by a prime less than or equal to 4. 1 and 4 are not primes, so we only need to check 2 and 3. But $17= 2*8+1$ and $17=3*5+2$ demonstrates 17 is not divisible by either.

Again though, I would be very surprised if you were supposed to actually prove this, though I don't know the level of dumb details your course requires you to provide. I would guess just what you wrote is sufficient. (What I wrote is assuming a bunch of properties about how multiplication preserves ordering, so if you're a real stickler you could also prove things like $k\leq m \rightarrow k^2 \leq km$

 

[Math100]

I don't know what your grader is expecting, but my guess is this is fine. If you think you need to be very rigorous on proving the primeness, it's not that hard. I'll do 17 for you so you can get the feel for it.

Here's a useful lemma: if $n$ is a composite number, then there exists a prime $p$ such that $p|n$ and $p^2 \leq n$
Proof: factor $n=mk$. One of $m$ or $k$ is smaller (or they are equal) wlog let it be $k\leq m$. Then $k^2\leq km=n$. And there must be some prime $p$ that divides $k$, and hence divides $n$. If $k=pq$, then $p^2 \leq k^2 \leq n$.

Since $5^2 > 17$, if 17 is composite it must be divisible by a prime less than or equal to 4. 1 and 4 are not primes, so we only need to check 2 and 3. But $17= 2*8+1$ and $17=3*5+2$ demonstrates 17 is not divisible by either.

Again though, I would be very surprised if you were supposed to actually prove this, though I don't know the level of dumb details your course requires you to provide. I would guess just what you wrote is sufficient. (What I wrote is assuming a bunch of properties about how multiplication preserves ordering, so if you're a real stickler you could also prove things like $k\leq m \rightarrow k^2 \leq km$

Thank you!

 

[Mark44]

Find two more of these primes.

Now I'm stuck.

All that the problem is asking you to do is to find two more primes of the given form. There is nothing that you need to prove, other than has already been stated about showing that your found examples are indeed prime.

 

[nuuskur]

Homework Statement:: An unanswered question is whether there are infinitely many primes that are $1$ more than a power of $2$, such as $5=2^2+1$. Find two more of these primes.

Just say primes of the form $2^k+1$. The only purpose this convoluted phrasing serves is confusing or annoying the reader.

 

[PeroK]

So do I just show my work and answer for this problem without proof?

$17=2^{4}+1$
$257=2^{8}+1$

Every composite number has a prime factor less than or equal to its square root. To check $257$ is prime you need only divide by $3, 7, 11$ and $13$. You can see by inspection it's not divisible by $2$ or $5$.