A Problem with primes of the form $2^n-1$
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
I want to show that if $2^n-1$ is prime, then $n$ is prime.
I could not see a way to a direct proof based on the definition of a prime number. In that case, we could only write $2^n-1$ as $1 cdot (2^n-1)$, and I don't see how that would help.
I think the best way to go about this proof is to use the contrapositive of the statement, which I believe is "if $n$ is not prime, then $2^n-1$ is not prime". So, if $n$ is not prime, it is composite and can be factored into the form $ab$. We plug that into $2^n-1$ to get $2^ab-1$. Now, if either $a$ or $b$ is even, we could use the laws of exponents and the difference of two squares to get a factored form and therefore prove that $2^n-1$ is composite. The problem in this approach is showing that if both $a$ and $b$ are odd, how the resulting expression can factor. We write this symbolically as $2^(2k+1)(2m+1)-1$ for some natural numbers $k$ and $m$. I don't know how to factor this. If anyone sees how to factor this, that would be awesome. Or, if anyone sees a flaw in my approach, that would also be greatly appreciated.
Finally, I ask that y'all not directly give me the answer, but rather a powerful hint. I am really trying to learn on my own, and I feel that the struggle will eventually pay off. Thanks in advance.
elementary-number-theory
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
asked Sep 7 at 3:41
L. Tim
212
 |Â
show 2 more comments
up vote
4
down vote
favorite
I want to show that if $2^n-1$ is prime, then $n$ is prime.
I could not see a way to a direct proof based on the definition of a prime number. In that case, we could only write $2^n-1$ as $1 cdot (2^n-1)$, and I don't see how that would help.
I think the best way to go about this proof is to use the contrapositive of the statement, which I believe is "if $n$ is not prime, then $2^n-1$ is not prime". So, if $n$ is not prime, it is composite and can be factored into the form $ab$. We plug that into $2^n-1$ to get $2^ab-1$. Now, if either $a$ or $b$ is even, we could use the laws of exponents and the difference of two squares to get a factored form and therefore prove that $2^n-1$ is composite. The problem in this approach is showing that if both $a$ and $b$ are odd, how the resulting expression can factor. We write this symbolically as $2^(2k+1)(2m+1)-1$ for some natural numbers $k$ and $m$. I don't know how to factor this. If anyone sees how to factor this, that would be awesome. Or, if anyone sees a flaw in my approach, that would also be greatly appreciated.
Finally, I ask that y'all not directly give me the answer, but rather a powerful hint. I am really trying to learn on my own, and I feel that the struggle will eventually pay off. Thanks in advance.
elementary-number-theory
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
asked Sep 7 at 3:41
L. Tim
212
6
Hint: $a^n -b^n = (a-b)(a^n-1+a^n-2b + cdots + b^n-1 )$.
– xbh
Sep 7 at 3:45
The following post provides a generalization : math.stackexchange.com/questions/7473/…
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Sep 7 at 3:46
So, when I got help originally on this problem, he did help me to see that $a^n-1$ can be factored as $(a-1)(a^n-1+a^n-2+...+1)$. However, I noted that in our case, a=2, so (a-1) becomes 1. So, my thought process is that all we did here is multiply by 1, and find a new way to express $2^n-1$ as a sum, and that this doesn't help show that the $2^n-1$ is composite. Please, correct me if I'm wrong.
– L. Tim
Sep 7 at 4:05
1
You can use the given hint to show your contrapositive. As $n=ab$, where both $a,b>1$ then $2^n-1=(2^a)^b-1=(2^a-1)(2^a(b-1)+...+1)$
– Marco Bellocchi
Sep 7 at 4:29
1
Possible duplicate of For $a,n in Bbb N$, how to prove if $a^n-1$ is prime then $a=2$ and $n$ is prime?
– Jyrki Lahtonen
Sep 7 at 5:26
 |Â
show 2 more comments
up vote
4
down vote
favorite
up vote
4
down vote
favorite
I want to show that if $2^n-1$ is prime, then $n$ is prime.
I could not see a way to a direct proof based on the definition of a prime number. In that case, we could only write $2^n-1$ as $1 cdot (2^n-1)$, and I don't see how that would help.
I think the best way to go about this proof is to use the contrapositive of the statement, which I believe is "if $n$ is not prime, then $2^n-1$ is not prime". So, if $n$ is not prime, it is composite and can be factored into the form $ab$. We plug that into $2^n-1$ to get $2^ab-1$. Now, if either $a$ or $b$ is even, we could use the laws of exponents and the difference of two squares to get a factored form and therefore prove that $2^n-1$ is composite. The problem in this approach is showing that if both $a$ and $b$ are odd, how the resulting expression can factor. We write this symbolically as $2^(2k+1)(2m+1)-1$ for some natural numbers $k$ and $m$. I don't know how to factor this. If anyone sees how to factor this, that would be awesome. Or, if anyone sees a flaw in my approach, that would also be greatly appreciated.
Finally, I ask that y'all not directly give me the answer, but rather a powerful hint. I am really trying to learn on my own, and I feel that the struggle will eventually pay off. Thanks in advance.
elementary-number-theory
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
asked Sep 7 at 3:41
L. Tim
212
I want to show that if $2^n-1$ is prime, then $n$ is prime.
I could not see a way to a direct proof based on the definition of a prime number. In that case, we could only write $2^n-1$ as $1 cdot (2^n-1)$, and I don't see how that would help.
I think the best way to go about this proof is to use the contrapositive of the statement, which I believe is "if $n$ is not prime, then $2^n-1$ is not prime". So, if $n$ is not prime, it is composite and can be factored into the form $ab$. We plug that into $2^n-1$ to get $2^ab-1$. Now, if either $a$ or $b$ is even, we could use the laws of exponents and the difference of two squares to get a factored form and therefore prove that $2^n-1$ is composite. The problem in this approach is showing that if both $a$ and $b$ are odd, how the resulting expression can factor. We write this symbolically as $2^(2k+1)(2m+1)-1$ for some natural numbers $k$ and $m$. I don't know how to factor this. If anyone sees how to factor this, that would be awesome. Or, if anyone sees a flaw in my approach, that would also be greatly appreciated.
Finally, I ask that y'all not directly give me the answer, but rather a powerful hint. I am really trying to learn on my own, and I feel that the struggle will eventually pay off. Thanks in advance.
elementary-number-theory
elementary-number-theory
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
asked Sep 7 at 3:41
L. Tim
212
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
asked Sep 7 at 3:41
L. Tim
212
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
edited Sep 7 at 10:57
Jendrik Stelzner
7,69121137
7,69121137
asked Sep 7 at 3:41
L. Tim
212
asked Sep 7 at 3:41
L. Tim
212
asked Sep 7 at 3:41
L. Tim
212
212
6
Hint: $a^n -b^n = (a-b)(a^n-1+a^n-2b + cdots + b^n-1 )$.
– xbh
Sep 7 at 3:45
The following post provides a generalization : math.stackexchange.com/questions/7473/…
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Sep 7 at 3:46
So, when I got help originally on this problem, he did help me to see that $a^n-1$ can be factored as $(a-1)(a^n-1+a^n-2+...+1)$. However, I noted that in our case, a=2, so (a-1) becomes 1. So, my thought process is that all we did here is multiply by 1, and find a new way to express $2^n-1$ as a sum, and that this doesn't help show that the $2^n-1$ is composite. Please, correct me if I'm wrong.
– L. Tim
Sep 7 at 4:05
1
You can use the given hint to show your contrapositive. As $n=ab$, where both $a,b>1$ then $2^n-1=(2^a)^b-1=(2^a-1)(2^a(b-1)+...+1)$
– Marco Bellocchi
Sep 7 at 4:29
1
Possible duplicate of For $a,n in Bbb N$, how to prove if $a^n-1$ is prime then $a=2$ and $n$ is prime?
– Jyrki Lahtonen
Sep 7 at 5:26
 |Â
show 2 more comments
6
Hint: $a^n -b^n = (a-b)(a^n-1+a^n-2b + cdots + b^n-1 )$.
– xbh
Sep 7 at 3:45
The following post provides a generalization : math.stackexchange.com/questions/7473/…
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Sep 7 at 3:46
So, when I got help originally on this problem, he did help me to see that $a^n-1$ can be factored as $(a-1)(a^n-1+a^n-2+...+1)$. However, I noted that in our case, a=2, so (a-1) becomes 1. So, my thought process is that all we did here is multiply by 1, and find a new way to express $2^n-1$ as a sum, and that this doesn't help show that the $2^n-1$ is composite. Please, correct me if I'm wrong.
– L. Tim
Sep 7 at 4:05
1
You can use the given hint to show your contrapositive. As $n=ab$, where both $a,b>1$ then $2^n-1=(2^a)^b-1=(2^a-1)(2^a(b-1)+...+1)$
– Marco Bellocchi
Sep 7 at 4:29
1
Possible duplicate of For $a,n in Bbb N$, how to prove if $a^n-1$ is prime then $a=2$ and $n$ is prime?
– Jyrki Lahtonen
Sep 7 at 5:26
6
6
Hint: $a^n -b^n = (a-b)(a^n-1+a^n-2b + cdots + b^n-1 )$.
– xbh
Sep 7 at 3:45
Hint: $a^n -b^n = (a-b)(a^n-1+a^n-2b + cdots + b^n-1 )$.
– xbh
Sep 7 at 3:45
The following post provides a generalization : math.stackexchange.com/questions/7473/…
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Sep 7 at 3:46
The following post provides a generalization : math.stackexchange.com/questions/7473/…
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Sep 7 at 3:46
So, when I got help originally on this problem, he did help me to see that $a^n-1$ can be factored as $(a-1)(a^n-1+a^n-2+...+1)$. However, I noted that in our case, a=2, so (a-1) becomes 1. So, my thought process is that all we did here is multiply by 1, and find a new way to express $2^n-1$ as a sum, and that this doesn't help show that the $2^n-1$ is composite. Please, correct me if I'm wrong.
– L. Tim
Sep 7 at 4:05
So, when I got help originally on this problem, he did help me to see that $a^n-1$ can be factored as $(a-1)(a^n-1+a^n-2+...+1)$. However, I noted that in our case, a=2, so (a-1) becomes 1. So, my thought process is that all we did here is multiply by 1, and find a new way to express $2^n-1$ as a sum, and that this doesn't help show that the $2^n-1$ is composite. Please, correct me if I'm wrong.
– L. Tim
Sep 7 at 4:05
1
1
You can use the given hint to show your contrapositive. As $n=ab$, where both $a,b>1$ then $2^n-1=(2^a)^b-1=(2^a-1)(2^a(b-1)+...+1)$
– Marco Bellocchi
Sep 7 at 4:29
You can use the given hint to show your contrapositive. As $n=ab$, where both $a,b>1$ then $2^n-1=(2^a)^b-1=(2^a-1)(2^a(b-1)+...+1)$
– Marco Bellocchi
Sep 7 at 4:29
1
1
Possible duplicate of For $a,n in Bbb N$, how to prove if $a^n-1$ is prime then $a=2$ and $n$ is prime?
– Jyrki Lahtonen
Sep 7 at 5:26
Possible duplicate of For $a,n in Bbb N$, how to prove if $a^n-1$ is prime then $a=2$ and $n$ is prime?
– Jyrki Lahtonen
Sep 7 at 5:26
 |Â
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2908246%2fa-problem-with-primes-of-the-form-2n-1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
6
Hint: $a^n -b^n = (a-b)(a^n-1+a^n-2b + cdots + b^n-1 )$.
– xbh
Sep 7 at 3:45
The following post provides a generalization : math.stackexchange.com/questions/7473/…
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Sep 7 at 3:46
So, when I got help originally on this problem, he did help me to see that $a^n-1$ can be factored as $(a-1)(a^n-1+a^n-2+...+1)$. However, I noted that in our case, a=2, so (a-1) becomes 1. So, my thought process is that all we did here is multiply by 1, and find a new way to express $2^n-1$ as a sum, and that this doesn't help show that the $2^n-1$ is composite. Please, correct me if I'm wrong.
– L. Tim
Sep 7 at 4:05
1
You can use the given hint to show your contrapositive. As $n=ab$, where both $a,b>1$ then $2^n-1=(2^a)^b-1=(2^a-1)(2^a(b-1)+...+1)$
– Marco Bellocchi
Sep 7 at 4:29
1
Possible duplicate of For $a,n in Bbb N$, how to prove if $a^n-1$ is prime then $a=2$ and $n$ is prime?
– Jyrki Lahtonen
Sep 7 at 5:26