Disprove that if $n$ is an odd positive integer greater than $1$ then $2^n-1$ is prime. [duplicate]
$begingroup$
This question already has an answer here:
If $n$ is composite, so is $2^n-1$ [duplicate]
2 answers
Disprove that if $n$ is an odd positive integer greater than $1$ then $2^n-1$ is prime.
So my approach to this is as follows but I have no idea where to go from here or whether this is the right approach.
Let $n=2x+1$ where $xinBbb Z^+$
Then $2^n+1=2^{2x+1}-1$
$=6(2^n)-1$
elementary-number-theory divisibility
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
$endgroup$
marked as duplicate by Bill Dubuque divisibility
Users with the divisibility badge can single-handedly close divisibility questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 20:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
|
show 1 more comment
$begingroup$
This question already has an answer here:
If $n$ is composite, so is $2^n-1$ [duplicate]
2 answers
Disprove that if $n$ is an odd positive integer greater than $1$ then $2^n-1$ is prime.
So my approach to this is as follows but I have no idea where to go from here or whether this is the right approach.
Let $n=2x+1$ where $xinBbb Z^+$
Then $2^n+1=2^{2x+1}-1$
$=6(2^n)-1$
elementary-number-theory divisibility
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
$endgroup$
marked as duplicate by Bill Dubuque divisibility
Users with the divisibility badge can single-handedly close divisibility questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 20:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
All you need is a single counterexample, and there is a fairly small one.
$endgroup$
– lulu
Dec 16 '18 at 19:32
1
$begingroup$
is there not a way this can be proved by deduction then?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:32
1
$begingroup$
You are trying to disprove something. In truth, there are primes of this form and there are composites of this form. To disprove this claim you just need to find a single composite example.
$endgroup$
– lulu
Dec 16 '18 at 19:34
1
$begingroup$
Oh okay, the question is worth 4 marks and i thought a simple counter example way to simple
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:35
2
$begingroup$
Nope. All it takes is one counterexample to disprove a theorem.
$endgroup$
– lulu
Dec 16 '18 at 19:35
|
show 1 more comment
$begingroup$
This question already has an answer here:
If $n$ is composite, so is $2^n-1$ [duplicate]
2 answers
Disprove that if $n$ is an odd positive integer greater than $1$ then $2^n-1$ is prime.
So my approach to this is as follows but I have no idea where to go from here or whether this is the right approach.
Let $n=2x+1$ where $xinBbb Z^+$
Then $2^n+1=2^{2x+1}-1$
$=6(2^n)-1$
elementary-number-theory divisibility
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
$endgroup$
This question already has an answer here:
If $n$ is composite, so is $2^n-1$ [duplicate]
2 answers
Disprove that if $n$ is an odd positive integer greater than $1$ then $2^n-1$ is prime.
So my approach to this is as follows but I have no idea where to go from here or whether this is the right approach.
Let $n=2x+1$ where $xinBbb Z^+$
Then $2^n+1=2^{2x+1}-1$
$=6(2^n)-1$
This question already has an answer here:
If $n$ is composite, so is $2^n-1$ [duplicate]
2 answers
elementary-number-theory divisibility
elementary-number-theory divisibility
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
edited Dec 16 '18 at 20:03
Brahadeesh
6,19742361
6,19742361
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
asked Dec 16 '18 at 19:28
H.LinkhornH.Linkhorn
34213
34213
marked as duplicate by Bill Dubuque divisibility
Users with the divisibility badge can single-handedly close divisibility questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 20:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Bill Dubuque divisibility
Users with the divisibility badge can single-handedly close divisibility questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 16 '18 at 20:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
All you need is a single counterexample, and there is a fairly small one.
$endgroup$
– lulu
Dec 16 '18 at 19:32
1
$begingroup$
is there not a way this can be proved by deduction then?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:32
1
$begingroup$
You are trying to disprove something. In truth, there are primes of this form and there are composites of this form. To disprove this claim you just need to find a single composite example.
$endgroup$
– lulu
Dec 16 '18 at 19:34
1
$begingroup$
Oh okay, the question is worth 4 marks and i thought a simple counter example way to simple
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:35
2
$begingroup$
Nope. All it takes is one counterexample to disprove a theorem.
$endgroup$
– lulu
Dec 16 '18 at 19:35
|
show 1 more comment
$begingroup$
All you need is a single counterexample, and there is a fairly small one.
$endgroup$
– lulu
Dec 16 '18 at 19:32
1
$begingroup$
is there not a way this can be proved by deduction then?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:32
1
$begingroup$
You are trying to disprove something. In truth, there are primes of this form and there are composites of this form. To disprove this claim you just need to find a single composite example.
$endgroup$
– lulu
Dec 16 '18 at 19:34
1
$begingroup$
Oh okay, the question is worth 4 marks and i thought a simple counter example way to simple
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:35
2
$begingroup$
Nope. All it takes is one counterexample to disprove a theorem.
$endgroup$
– lulu
Dec 16 '18 at 19:35
$begingroup$
All you need is a single counterexample, and there is a fairly small one.
$endgroup$
– lulu
Dec 16 '18 at 19:32
$begingroup$
All you need is a single counterexample, and there is a fairly small one.
$endgroup$
– lulu
Dec 16 '18 at 19:32
1
1
$begingroup$
is there not a way this can be proved by deduction then?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:32
$begingroup$
is there not a way this can be proved by deduction then?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:32
1
1
$begingroup$
You are trying to disprove something. In truth, there are primes of this form and there are composites of this form. To disprove this claim you just need to find a single composite example.
$endgroup$
– lulu
Dec 16 '18 at 19:34
$begingroup$
You are trying to disprove something. In truth, there are primes of this form and there are composites of this form. To disprove this claim you just need to find a single composite example.
$endgroup$
– lulu
Dec 16 '18 at 19:34
1
1
$begingroup$
Oh okay, the question is worth 4 marks and i thought a simple counter example way to simple
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:35
$begingroup$
Oh okay, the question is worth 4 marks and i thought a simple counter example way to simple
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:35
2
2
$begingroup$
Nope. All it takes is one counterexample to disprove a theorem.
$endgroup$
– lulu
Dec 16 '18 at 19:35
$begingroup$
Nope. All it takes is one counterexample to disprove a theorem.
$endgroup$
– lulu
Dec 16 '18 at 19:35
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
In general:
If $n$ is composite, then $2^n-1$ is composite. The prove is not hard to follow up. since $n$ is composite, $n = km$. This implies that $2^{km}-1 = (2^k-1)(1+2^k+2^{2k}+2^{3k}...+2^{km-1})$.
If $2^n - 1$ is prime, then $n$ is prime. The prove can be deduced from the previous part by "counter-positiving" this statement. "NOTE THAT THE CONVERSE IS NOT TRUE".
A quick counter example to disprove, take $n$ to be $9$, then $ 2^9-1 = 511 = 7*73$ which is divisible by $2^3 - 1 = 7$ and $1+2^3+2^6 = 73$.
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
$endgroup$
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
1
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
add a comment |
$begingroup$
Take $$2^{11}-1=23cdot 89$$ and this number is not prime
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
$endgroup$
1
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
1
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In general:
If $n$ is composite, then $2^n-1$ is composite. The prove is not hard to follow up. since $n$ is composite, $n = km$. This implies that $2^{km}-1 = (2^k-1)(1+2^k+2^{2k}+2^{3k}...+2^{km-1})$.
If $2^n - 1$ is prime, then $n$ is prime. The prove can be deduced from the previous part by "counter-positiving" this statement. "NOTE THAT THE CONVERSE IS NOT TRUE".
A quick counter example to disprove, take $n$ to be $9$, then $ 2^9-1 = 511 = 7*73$ which is divisible by $2^3 - 1 = 7$ and $1+2^3+2^6 = 73$.
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
$endgroup$
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
1
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
add a comment |
$begingroup$
In general:
If $n$ is composite, then $2^n-1$ is composite. The prove is not hard to follow up. since $n$ is composite, $n = km$. This implies that $2^{km}-1 = (2^k-1)(1+2^k+2^{2k}+2^{3k}...+2^{km-1})$.
If $2^n - 1$ is prime, then $n$ is prime. The prove can be deduced from the previous part by "counter-positiving" this statement. "NOTE THAT THE CONVERSE IS NOT TRUE".
A quick counter example to disprove, take $n$ to be $9$, then $ 2^9-1 = 511 = 7*73$ which is divisible by $2^3 - 1 = 7$ and $1+2^3+2^6 = 73$.
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
$endgroup$
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
1
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
add a comment |
$begingroup$
In general:
If $n$ is composite, then $2^n-1$ is composite. The prove is not hard to follow up. since $n$ is composite, $n = km$. This implies that $2^{km}-1 = (2^k-1)(1+2^k+2^{2k}+2^{3k}...+2^{km-1})$.
If $2^n - 1$ is prime, then $n$ is prime. The prove can be deduced from the previous part by "counter-positiving" this statement. "NOTE THAT THE CONVERSE IS NOT TRUE".
A quick counter example to disprove, take $n$ to be $9$, then $ 2^9-1 = 511 = 7*73$ which is divisible by $2^3 - 1 = 7$ and $1+2^3+2^6 = 73$.
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
$endgroup$
In general:
If $n$ is composite, then $2^n-1$ is composite. The prove is not hard to follow up. since $n$ is composite, $n = km$. This implies that $2^{km}-1 = (2^k-1)(1+2^k+2^{2k}+2^{3k}...+2^{km-1})$.
If $2^n - 1$ is prime, then $n$ is prime. The prove can be deduced from the previous part by "counter-positiving" this statement. "NOTE THAT THE CONVERSE IS NOT TRUE".
A quick counter example to disprove, take $n$ to be $9$, then $ 2^9-1 = 511 = 7*73$ which is divisible by $2^3 - 1 = 7$ and $1+2^3+2^6 = 73$.
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
edited Dec 17 '18 at 5:34
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
answered Dec 16 '18 at 19:42
Maged SaeedMaged Saeed
8471417
8471417
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
1
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
add a comment |
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
1
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
There is a much smaller counterexample. Since you know $n$ must be composite, what's the first thing to try?
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:54
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
$begingroup$
@EthanBolker The first odd $n$ to be a counterexample seems to be $9$. Is there a smaller number?
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:55
1
1
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
Oops missed the "odd". Sorry.
$endgroup$
– Ethan Bolker
Dec 16 '18 at 19:56
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
$begingroup$
@EthanBolker I guessed so :).
$endgroup$
– Maged Saeed
Dec 16 '18 at 19:57
add a comment |
$begingroup$
Take $$2^{11}-1=23cdot 89$$ and this number is not prime
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
$endgroup$
1
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
1
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
add a comment |
$begingroup$
Take $$2^{11}-1=23cdot 89$$ and this number is not prime
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
$endgroup$
1
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
1
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
add a comment |
$begingroup$
Take $$2^{11}-1=23cdot 89$$ and this number is not prime
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
$endgroup$
Take $$2^{11}-1=23cdot 89$$ and this number is not prime
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
answered Dec 16 '18 at 19:36
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
74k42865
74k42865
1
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
1
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
add a comment |
1
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
1
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
1
1
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
$begingroup$
is n=9 not a simpler example?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:39
1
1
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
$begingroup$
Here is also the exponent prime!
$endgroup$
– Dr. Sonnhard Graubner
Dec 16 '18 at 19:41
add a comment |
$begingroup$
All you need is a single counterexample, and there is a fairly small one.
$endgroup$
– lulu
Dec 16 '18 at 19:32
1
$begingroup$
is there not a way this can be proved by deduction then?
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:32
1
$begingroup$
You are trying to disprove something. In truth, there are primes of this form and there are composites of this form. To disprove this claim you just need to find a single composite example.
$endgroup$
– lulu
Dec 16 '18 at 19:34
1
$begingroup$
Oh okay, the question is worth 4 marks and i thought a simple counter example way to simple
$endgroup$
– H.Linkhorn
Dec 16 '18 at 19:35
2
$begingroup$
Nope. All it takes is one counterexample to disprove a theorem.
$endgroup$
– lulu
Dec 16 '18 at 19:35