If $2^n - 1$ is prime from some integer $n$, prove that n must also be prime.$2^p -1$ then $p$ is a primeIf $2^k - 1$ is prime then $k$ is prime, using $2^m -1 vert 2^mn - 1$$2^n + 1$ is prime $ implies n$ is a power of $2$Showing that $a = 2^1264504 - 1$ is not primeHow to prove that $n$ is a prime if $2^n-1$ is a primeIf $2^n-1$ is prime, then n is prime - proof involving the Mersenne primes by counterexampleIf an integer is divisible by 8 and 15, then the integer also must be divisible by which of the following?Prove that $1$ has only one divisorProve if $3$ does not divide $n$, then $n^2=1+3k$ for some integer $k$Prove for each positive integer $n$, there exists $n$ consecutive positive integers none of which is an integral power of a prime numberProving that no integer has multiplicative order 40 (mod 100)The integer $m$ is odd if and only if there exists $q in mathbbZ$ such that $m = 2q + 1$$A$ must contain two relatively prime elementsProve that for all prime numbers $ a,b,c , a^2 + b^2 neq c^2$Find all integers $x$ such that $frac2x^2-33x-1$ is an integer.Prove that integer not divisible by 2 or 3 is not divisible by 6
A Cautionary Suggestion
Error in Twin Prime Conjecture
Have researchers managed to "reverse time"? If so, what does that mean for physics?
It's a yearly task, alright
Official degrees of earth’s rotation per day
My Graph Theory Students
What is the significance behind "40 days" that often appears in the Bible?
Can a druid choose the size of its wild shape beast?
My adviser wants to be the first author
Science-fiction short story where space navy wanted hospital ships and settlers had guns mounted everywhere
Professor being mistaken for a grad student
compactness of a set where am I going wrong
Time travel from stationary position?
How to deal with a cynical class?
Co-worker team leader wants to inject his friend's awful software into our development. What should I say to our common boss?
What do Xenomorphs eat in the Alien series?
Creature kill and resurrect effects on the stack interaction?
how to write formula in word in latex
Why do passenger jet manufacturers design their planes with stall prevention systems?
Look at your watch and tell me what time is it. vs Look at your watch and tell me what time it is
What exactly is this small puffer fish doing and how did it manage to accomplish such a feat?
Why doesn't using two cd commands in bash script execute the second command?
How to read the value of this capacitor?
How to deal with taxi scam when on vacation?
If $2^n - 1$ is prime from some integer $n$, prove that n must also be prime.
$2^p -1$ then $p$ is a primeIf $2^k - 1$ is prime then $k$ is prime, using $2^m -1 vert 2^mn - 1$$2^n + 1$ is prime $ implies n$ is a power of $2$Showing that $a = 2^1264504 - 1$ is not primeHow to prove that $n$ is a prime if $2^n-1$ is a primeIf $2^n-1$ is prime, then n is prime - proof involving the Mersenne primes by counterexampleIf an integer is divisible by 8 and 15, then the integer also must be divisible by which of the following?Prove that $1$ has only one divisorProve if $3$ does not divide $n$, then $n^2=1+3k$ for some integer $k$Prove for each positive integer $n$, there exists $n$ consecutive positive integers none of which is an integral power of a prime numberProving that no integer has multiplicative order 40 (mod 100)The integer $m$ is odd if and only if there exists $q in mathbbZ$ such that $m = 2q + 1$$A$ must contain two relatively prime elementsProve that for all prime numbers $ a,b,c , a^2 + b^2 neq c^2$Find all integers $x$ such that $frac2x^2-33x-1$ is an integer.Prove that integer not divisible by 2 or 3 is not divisible by 6
$begingroup$
I understand the idea of the proof. I just want to make sure I wrote my proof well.
Suppose $n$ is not prime. Then $exists x,y in mathbbZ$ such that $n = xy$.
$2^xy - 1 = (2^x)^y - 1$
$ = (2^y - 1)(2^y(x-1) + 2^y(x-2) + ... + 2^y + 1)$
Since $2^n - 1$ is divisible by $2^y - 1$ it must be that $2^n - 1$ is not prime. Contradiction. Thus $n$ must be prime.
How does this look?
number-theory divisibility
asked Mar 3 '13 at 23:57
user64013user64013
219128
$endgroup$
|
show 3 more comments
$begingroup$
I understand the idea of the proof. I just want to make sure I wrote my proof well.
Suppose $n$ is not prime. Then $exists x,y in mathbbZ$ such that $n = xy$.
$2^xy - 1 = (2^x)^y - 1$
$ = (2^y - 1)(2^y(x-1) + 2^y(x-2) + ... + 2^y + 1)$
Since $2^n - 1$ is divisible by $2^y - 1$ it must be that $2^n - 1$ is not prime. Contradiction. Thus $n$ must be prime.
How does this look?
number-theory divisibility
asked Mar 3 '13 at 23:57
user64013user64013
219128
$endgroup$
6
$begingroup$
Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two.
$endgroup$
– anon
Mar 4 '13 at 0:00
4
$begingroup$
Don't say in $mathbbZ$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $gt 1$.
$endgroup$
– André Nicolas
Mar 4 '13 at 0:19
$begingroup$
Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$).
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:41
$begingroup$
To make the proof really complete, you have to assume $x, y > 1$, so that $2^y - 1 > 1$, and $2^y - 1$ is a proper divisor of $2^n - 1$.
$endgroup$
– Andreas Caranti
Sep 17 '13 at 11:42
$begingroup$
@AndreasCaranti: and $2^y(x-1) + 2^y(x-2) + ... + 2^y + 1>1$ (since $x>1$) so the other factor is also a proper divisor.
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:44
|
show 3 more comments
$begingroup$
I understand the idea of the proof. I just want to make sure I wrote my proof well.
Suppose $n$ is not prime. Then $exists x,y in mathbbZ$ such that $n = xy$.
$2^xy - 1 = (2^x)^y - 1$
$ = (2^y - 1)(2^y(x-1) + 2^y(x-2) + ... + 2^y + 1)$
Since $2^n - 1$ is divisible by $2^y - 1$ it must be that $2^n - 1$ is not prime. Contradiction. Thus $n$ must be prime.
How does this look?
number-theory divisibility
asked Mar 3 '13 at 23:57
user64013user64013
219128
$endgroup$
I understand the idea of the proof. I just want to make sure I wrote my proof well.
Suppose $n$ is not prime. Then $exists x,y in mathbbZ$ such that $n = xy$.
$2^xy - 1 = (2^x)^y - 1$
$ = (2^y - 1)(2^y(x-1) + 2^y(x-2) + ... + 2^y + 1)$
Since $2^n - 1$ is divisible by $2^y - 1$ it must be that $2^n - 1$ is not prime. Contradiction. Thus $n$ must be prime.
How does this look?
number-theory divisibility
number-theory divisibility
asked Mar 3 '13 at 23:57
user64013user64013
219128
asked Mar 3 '13 at 23:57
user64013user64013
219128
asked Mar 3 '13 at 23:57
user64013user64013
219128
asked Mar 3 '13 at 23:57
user64013user64013
219128
asked Mar 3 '13 at 23:57
user64013user64013
219128
219128
6
$begingroup$
Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two.
$endgroup$
– anon
Mar 4 '13 at 0:00
4
$begingroup$
Don't say in $mathbbZ$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $gt 1$.
$endgroup$
– André Nicolas
Mar 4 '13 at 0:19
$begingroup$
Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$).
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:41
$begingroup$
To make the proof really complete, you have to assume $x, y > 1$, so that $2^y - 1 > 1$, and $2^y - 1$ is a proper divisor of $2^n - 1$.
$endgroup$
– Andreas Caranti
Sep 17 '13 at 11:42
$begingroup$
@AndreasCaranti: and $2^y(x-1) + 2^y(x-2) + ... + 2^y + 1>1$ (since $x>1$) so the other factor is also a proper divisor.
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:44
|
show 3 more comments
6
$begingroup$
Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two.
$endgroup$
– anon
Mar 4 '13 at 0:00
4
$begingroup$
Don't say in $mathbbZ$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $gt 1$.
$endgroup$
– André Nicolas
Mar 4 '13 at 0:19
$begingroup$
Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$).
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:41
$begingroup$
To make the proof really complete, you have to assume $x, y > 1$, so that $2^y - 1 > 1$, and $2^y - 1$ is a proper divisor of $2^n - 1$.
$endgroup$
– Andreas Caranti
Sep 17 '13 at 11:42
$begingroup$
@AndreasCaranti: and $2^y(x-1) + 2^y(x-2) + ... + 2^y + 1>1$ (since $x>1$) so the other factor is also a proper divisor.
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:44
6
6
$begingroup$
Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two.
$endgroup$
– anon
Mar 4 '13 at 0:00
$begingroup$
Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two.
$endgroup$
– anon
Mar 4 '13 at 0:00
4
4
$begingroup$
Don't say in $mathbbZ$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $gt 1$.
$endgroup$
– André Nicolas
Mar 4 '13 at 0:19
$begingroup$
Don't say in $mathbbZ$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $gt 1$.
$endgroup$
– André Nicolas
Mar 4 '13 at 0:19
$begingroup$
Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$).
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:41
$begingroup$
Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$).
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:41
$begingroup$
To make the proof really complete, you have to assume $x, y > 1$, so that $2^y - 1 > 1$, and $2^y - 1$ is a proper divisor of $2^n - 1$.
$endgroup$
– Andreas Caranti
Sep 17 '13 at 11:42
$begingroup$
To make the proof really complete, you have to assume $x, y > 1$, so that $2^y - 1 > 1$, and $2^y - 1$ is a proper divisor of $2^n - 1$.
$endgroup$
– Andreas Caranti
Sep 17 '13 at 11:42
$begingroup$
@AndreasCaranti: and $2^y(x-1) + 2^y(x-2) + ... + 2^y + 1>1$ (since $x>1$) so the other factor is also a proper divisor.
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:44
$begingroup$
@AndreasCaranti: and $2^y(x-1) + 2^y(x-2) + ... + 2^y + 1>1$ (since $x>1$) so the other factor is also a proper divisor.
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:44
|
show 3 more comments
3 Answers
3
active
oldest
votes
$begingroup$
I'll try to recapituate all the comments made in an adapted version of the proof.
If $2^n−1$ is prime from some integer$~n$, then $n$ must also be prime.
Since the hypothesis requires $ngeq2$ to be true, one may assume that.
We prove the contrapositive: if $ngeq2$ is not prime then $2^n-1$ is not prime either.
Suppose $ngeq2$ is not prime. Then there exist integers $x,y>1$ such that $n = xy$.
One has $2^n-1 = 2^yx - 1 = (2^y)^x - 1 = (2^y - 1)(2^y(x-1) + 2^y(x-2) + cdots + 2^y.1 + 2^y.0)$. Since $y>1$ the first factor $2^y - 1$ is$>1$, and since $x>1$ that factor is less than $2^n-1$.
Since $2^n - 1$ has a proper divisor $2^y - 1$ greater than$~1$, we have shown that $2^n - 1$ is composite, establishing the contrapositive.
Remark. The contrapositive statement proved remains true if powers of $2$ are replaced throughout by powers of some integer $ageq2$. However with that change it is no longer true that the original hypothesis requires $ngeq2$, as $n=1$ might work. Therefore such a generalisation of the original statement requires an explicit additional hypothesis $ngeq2$.
$endgroup$
add a comment |
$begingroup$
Perhaps a minor nit-pick, but it seems the middle step should be $((2^y)^x-1)$, since you're utilizing the identity $$a^x-1=(a-1)(a^x-1+a^x-2+cdots+a+1)$$ with $a=2^y$.
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
$endgroup$
add a comment |
$begingroup$
This feels more like proof by contrapositive than proof by contradiction. Also, although obvious, without conditions on n,x,y it is not clear that $2^y-1$ can't be 1.
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
$endgroup$
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f319963%2fif-2n-1-is-prime-from-some-integer-n-prove-that-n-must-also-be-prime%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I'll try to recapituate all the comments made in an adapted version of the proof.
If $2^n−1$ is prime from some integer$~n$, then $n$ must also be prime.
Since the hypothesis requires $ngeq2$ to be true, one may assume that.
We prove the contrapositive: if $ngeq2$ is not prime then $2^n-1$ is not prime either.
Suppose $ngeq2$ is not prime. Then there exist integers $x,y>1$ such that $n = xy$.
One has $2^n-1 = 2^yx - 1 = (2^y)^x - 1 = (2^y - 1)(2^y(x-1) + 2^y(x-2) + cdots + 2^y.1 + 2^y.0)$. Since $y>1$ the first factor $2^y - 1$ is$>1$, and since $x>1$ that factor is less than $2^n-1$.
Since $2^n - 1$ has a proper divisor $2^y - 1$ greater than$~1$, we have shown that $2^n - 1$ is composite, establishing the contrapositive.
Remark. The contrapositive statement proved remains true if powers of $2$ are replaced throughout by powers of some integer $ageq2$. However with that change it is no longer true that the original hypothesis requires $ngeq2$, as $n=1$ might work. Therefore such a generalisation of the original statement requires an explicit additional hypothesis $ngeq2$.
$endgroup$
add a comment |
$begingroup$
I'll try to recapituate all the comments made in an adapted version of the proof.
If $2^n−1$ is prime from some integer$~n$, then $n$ must also be prime.
Since the hypothesis requires $ngeq2$ to be true, one may assume that.
We prove the contrapositive: if $ngeq2$ is not prime then $2^n-1$ is not prime either.
Suppose $ngeq2$ is not prime. Then there exist integers $x,y>1$ such that $n = xy$.
One has $2^n-1 = 2^yx - 1 = (2^y)^x - 1 = (2^y - 1)(2^y(x-1) + 2^y(x-2) + cdots + 2^y.1 + 2^y.0)$. Since $y>1$ the first factor $2^y - 1$ is$>1$, and since $x>1$ that factor is less than $2^n-1$.
Since $2^n - 1$ has a proper divisor $2^y - 1$ greater than$~1$, we have shown that $2^n - 1$ is composite, establishing the contrapositive.
Remark. The contrapositive statement proved remains true if powers of $2$ are replaced throughout by powers of some integer $ageq2$. However with that change it is no longer true that the original hypothesis requires $ngeq2$, as $n=1$ might work. Therefore such a generalisation of the original statement requires an explicit additional hypothesis $ngeq2$.
$endgroup$
add a comment |
$begingroup$
I'll try to recapituate all the comments made in an adapted version of the proof.
If $2^n−1$ is prime from some integer$~n$, then $n$ must also be prime.
Since the hypothesis requires $ngeq2$ to be true, one may assume that.
We prove the contrapositive: if $ngeq2$ is not prime then $2^n-1$ is not prime either.
Suppose $ngeq2$ is not prime. Then there exist integers $x,y>1$ such that $n = xy$.
One has $2^n-1 = 2^yx - 1 = (2^y)^x - 1 = (2^y - 1)(2^y(x-1) + 2^y(x-2) + cdots + 2^y.1 + 2^y.0)$. Since $y>1$ the first factor $2^y - 1$ is$>1$, and since $x>1$ that factor is less than $2^n-1$.
Since $2^n - 1$ has a proper divisor $2^y - 1$ greater than$~1$, we have shown that $2^n - 1$ is composite, establishing the contrapositive.
Remark. The contrapositive statement proved remains true if powers of $2$ are replaced throughout by powers of some integer $ageq2$. However with that change it is no longer true that the original hypothesis requires $ngeq2$, as $n=1$ might work. Therefore such a generalisation of the original statement requires an explicit additional hypothesis $ngeq2$.
$endgroup$
I'll try to recapituate all the comments made in an adapted version of the proof.
If $2^n−1$ is prime from some integer$~n$, then $n$ must also be prime.
Since the hypothesis requires $ngeq2$ to be true, one may assume that.
We prove the contrapositive: if $ngeq2$ is not prime then $2^n-1$ is not prime either.
Suppose $ngeq2$ is not prime. Then there exist integers $x,y>1$ such that $n = xy$.
One has $2^n-1 = 2^yx - 1 = (2^y)^x - 1 = (2^y - 1)(2^y(x-1) + 2^y(x-2) + cdots + 2^y.1 + 2^y.0)$. Since $y>1$ the first factor $2^y - 1$ is$>1$, and since $x>1$ that factor is less than $2^n-1$.
Since $2^n - 1$ has a proper divisor $2^y - 1$ greater than$~1$, we have shown that $2^n - 1$ is composite, establishing the contrapositive.
Remark. The contrapositive statement proved remains true if powers of $2$ are replaced throughout by powers of some integer $ageq2$. However with that change it is no longer true that the original hypothesis requires $ngeq2$, as $n=1$ might work. Therefore such a generalisation of the original statement requires an explicit additional hypothesis $ngeq2$.
edited Sep 18 '13 at 13:37
community wiki
3 revs
Marc van Leeuwen
add a comment |
add a comment |
$begingroup$
Perhaps a minor nit-pick, but it seems the middle step should be $((2^y)^x-1)$, since you're utilizing the identity $$a^x-1=(a-1)(a^x-1+a^x-2+cdots+a+1)$$ with $a=2^y$.
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
$endgroup$
add a comment |
$begingroup$
Perhaps a minor nit-pick, but it seems the middle step should be $((2^y)^x-1)$, since you're utilizing the identity $$a^x-1=(a-1)(a^x-1+a^x-2+cdots+a+1)$$ with $a=2^y$.
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
$endgroup$
add a comment |
$begingroup$
Perhaps a minor nit-pick, but it seems the middle step should be $((2^y)^x-1)$, since you're utilizing the identity $$a^x-1=(a-1)(a^x-1+a^x-2+cdots+a+1)$$ with $a=2^y$.
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
$endgroup$
Perhaps a minor nit-pick, but it seems the middle step should be $((2^y)^x-1)$, since you're utilizing the identity $$a^x-1=(a-1)(a^x-1+a^x-2+cdots+a+1)$$ with $a=2^y$.
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
answered Sep 17 '13 at 11:29
Rebecca J. StonesRebecca J. Stones
21k22781
21k22781
add a comment |
add a comment |
$begingroup$
This feels more like proof by contrapositive than proof by contradiction. Also, although obvious, without conditions on n,x,y it is not clear that $2^y-1$ can't be 1.
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
$endgroup$
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
add a comment |
$begingroup$
This feels more like proof by contrapositive than proof by contradiction. Also, although obvious, without conditions on n,x,y it is not clear that $2^y-1$ can't be 1.
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
$endgroup$
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
add a comment |
$begingroup$
This feels more like proof by contrapositive than proof by contradiction. Also, although obvious, without conditions on n,x,y it is not clear that $2^y-1$ can't be 1.
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
$endgroup$
This feels more like proof by contrapositive than proof by contradiction. Also, although obvious, without conditions on n,x,y it is not clear that $2^y-1$ can't be 1.
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
answered Mar 4 '13 at 0:09
newToProgrammingnewToProgramming
1755
1755
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
add a comment |
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
Should I say that $x$ and $y$ have to be greater then $1$ then?
$endgroup$
– user64013
Mar 4 '13 at 0:11
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
yes, and you are also implicitly assuming $ngt1$
$endgroup$
– newToProgramming
Mar 4 '13 at 0:15
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
Whats the reasoning x and y cant be 1?
$endgroup$
– user64013
Mar 4 '13 at 3:06
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
$begingroup$
In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion?
$endgroup$
– newToProgramming
Mar 4 '13 at 3:16
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f319963%2fif-2n-1-is-prime-from-some-integer-n-prove-that-n-must-also-be-prime%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
6
$begingroup$
Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two.
$endgroup$
– anon
Mar 4 '13 at 0:00
4
$begingroup$
Don't say in $mathbbZ$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $gt 1$.
$endgroup$
– André Nicolas
Mar 4 '13 at 0:19
$begingroup$
Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$).
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:41
$begingroup$
To make the proof really complete, you have to assume $x, y > 1$, so that $2^y - 1 > 1$, and $2^y - 1$ is a proper divisor of $2^n - 1$.
$endgroup$
– Andreas Caranti
Sep 17 '13 at 11:42
$begingroup$
@AndreasCaranti: and $2^y(x-1) + 2^y(x-2) + ... + 2^y + 1>1$ (since $x>1$) so the other factor is also a proper divisor.
$endgroup$
– Marc van Leeuwen
Sep 17 '13 at 11:44