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
Multi tool use
Why did it take so long to abandon sail after steamships were demonstrated?
How to deal with taxi scam when on vacation?
Should we release the security issues we found in our product as CVE or we can just update those on weekly release notes?
If curse and magic is two sides of the same coin, why the former is forbidden?
Does someone need to be connected to my network to sniff HTTP requests?
Are all passive ability checks floors for active ability checks?
How to simplify this time periods definition interface?
Gantt Chart like rectangles with log scale
Science-fiction short story where space navy wanted hospital ships and settlers had guns mounted everywhere
Could the Saturn V actually have launched astronauts around Venus?
Why would a flight no longer considered airworthy be redirected like this?
Can I use USB data pins as power source
How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?
Life insurance that covers only simultaneous/dual deaths
Gravity magic - How does it work?
Brexit - No Deal Rejection
Is a party consisting of only a bard, a cleric, and a warlock functional long-term?
What did Alexander Pope mean by "Expletives their feeble Aid do join"?
Combining an idiom with a metonymy
Do I need to be arrogant to get ahead?
How Could an Airship Be Repaired Mid-Flight
Have researchers managed to "reverse time"? If so, what does that mean for physics?
How to explain that I do not want to visit a country due to personal safety concern?
A sequence that has integer values for prime indexes only:
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
5AYqFy1liK56pGjXhaEI c,j6ouRpo9cvgAUB0aKSKH nffcVm3ck,TJI9Q4EaLe,dT13NnE,xLY,YmhXYNtAMOh7
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