Mixing
Prove that if $n$ and $x$ are natural numbers and $n$ is odd then $(2^n- 1, 2^x+ 1) = 1$ [closed]
$begingroup$
I tried to use Bachet-Bezout lemma:$(a, b) = ax + by$,
but couldn't go further.
How can we use the fact that $n$ is odd?
elementary-number-theory
edited Jan 1 at 8:14
user26857
39.3k124083
asked Jan 1 at 7:48
MelinaMelina
153
$endgroup$
closed as off-topic by Eevee Trainer, user26857, Jyrki Lahtonen, Lord Shark the Unknown, Saad Jan 1 at 12:36
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, user26857, Saad
If this question can be reworded to fit the rules in the help center, please edit the question.
|
show 4 more comments
$begingroup$
I tried to use Bachet-Bezout lemma:$(a, b) = ax + by$,
but couldn't go further.
How can we use the fact that $n$ is odd?
elementary-number-theory
edited Jan 1 at 8:14
user26857
39.3k124083
asked Jan 1 at 7:48
MelinaMelina
153
$endgroup$
closed as off-topic by Eevee Trainer, user26857, Jyrki Lahtonen, Lord Shark the Unknown, Saad Jan 1 at 12:36
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, user26857, Saad
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
OP, please clarify what $(2^n_- 1, 2^x_+ 1) = 1$ is supposed to be. I just edited with correct typesetting based on what you had. Did you mean $(2^n - 1, 2^x + 1) = 1$?
$endgroup$
– The Pointer
Jan 1 at 8:10
$begingroup$
Do you mean that it reduces to identity?
$endgroup$
– Colebasaur
Jan 1 at 8:15
1
$begingroup$
You mean $ gcd(2^n-1,2^x-1)=1$?
$endgroup$
– PerelMan
Jan 1 at 8:17
1
$begingroup$
Who has downvoted this question ? It is correctly asked. Everybody knows that (a,b) means gcd(a,b).
$endgroup$
– MikeTeX
Jan 1 at 8:48
3
$begingroup$
Possible duplicate of Showing $gcd(2^m-1,2^n+1)=1$
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:00
|
show 4 more comments
$begingroup$
I tried to use Bachet-Bezout lemma:$(a, b) = ax + by$,
but couldn't go further.
How can we use the fact that $n$ is odd?
elementary-number-theory
edited Jan 1 at 8:14
user26857
39.3k124083
asked Jan 1 at 7:48
MelinaMelina
153
$endgroup$
I tried to use Bachet-Bezout lemma:$(a, b) = ax + by$,
but couldn't go further.
How can we use the fact that $n$ is odd?
elementary-number-theory
elementary-number-theory
edited Jan 1 at 8:14
user26857
39.3k124083
asked Jan 1 at 7:48
MelinaMelina
153
edited Jan 1 at 8:14
user26857
39.3k124083
asked Jan 1 at 7:48
MelinaMelina
153
edited Jan 1 at 8:14
user26857
39.3k124083
edited Jan 1 at 8:14
user26857
39.3k124083
edited Jan 1 at 8:14
user26857
39.3k124083
39.3k124083
asked Jan 1 at 7:48
MelinaMelina
153
asked Jan 1 at 7:48
MelinaMelina
153
asked Jan 1 at 7:48
MelinaMelina
153
153
closed as off-topic by Eevee Trainer, user26857, Jyrki Lahtonen, Lord Shark the Unknown, Saad Jan 1 at 12:36
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, user26857, Saad
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Eevee Trainer, user26857, Jyrki Lahtonen, Lord Shark the Unknown, Saad Jan 1 at 12:36
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, user26857, Saad
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
OP, please clarify what $(2^n_- 1, 2^x_+ 1) = 1$ is supposed to be. I just edited with correct typesetting based on what you had. Did you mean $(2^n - 1, 2^x + 1) = 1$?
$endgroup$
– The Pointer
Jan 1 at 8:10
$begingroup$
Do you mean that it reduces to identity?
$endgroup$
– Colebasaur
Jan 1 at 8:15
1
$begingroup$
You mean $ gcd(2^n-1,2^x-1)=1$?
$endgroup$
– PerelMan
Jan 1 at 8:17
1
$begingroup$
Who has downvoted this question ? It is correctly asked. Everybody knows that (a,b) means gcd(a,b).
$endgroup$
– MikeTeX
Jan 1 at 8:48
3
$begingroup$
Possible duplicate of Showing $gcd(2^m-1,2^n+1)=1$
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:00
|
show 4 more comments
$begingroup$
OP, please clarify what $(2^n_- 1, 2^x_+ 1) = 1$ is supposed to be. I just edited with correct typesetting based on what you had. Did you mean $(2^n - 1, 2^x + 1) = 1$?
$endgroup$
– The Pointer
Jan 1 at 8:10
$begingroup$
Do you mean that it reduces to identity?
$endgroup$
– Colebasaur
Jan 1 at 8:15
1
$begingroup$
You mean $ gcd(2^n-1,2^x-1)=1$?
$endgroup$
– PerelMan
Jan 1 at 8:17
1
$begingroup$
Who has downvoted this question ? It is correctly asked. Everybody knows that (a,b) means gcd(a,b).
$endgroup$
– MikeTeX
Jan 1 at 8:48
3
$begingroup$
Possible duplicate of Showing $gcd(2^m-1,2^n+1)=1$
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:00
$begingroup$
OP, please clarify what $(2^n_- 1, 2^x_+ 1) = 1$ is supposed to be. I just edited with correct typesetting based on what you had. Did you mean $(2^n - 1, 2^x + 1) = 1$?
$endgroup$
– The Pointer
Jan 1 at 8:10
$begingroup$
OP, please clarify what $(2^n_- 1, 2^x_+ 1) = 1$ is supposed to be. I just edited with correct typesetting based on what you had. Did you mean $(2^n - 1, 2^x + 1) = 1$?
$endgroup$
– The Pointer
Jan 1 at 8:10
$begingroup$
Do you mean that it reduces to identity?
$endgroup$
– Colebasaur
Jan 1 at 8:15
$begingroup$
Do you mean that it reduces to identity?
$endgroup$
– Colebasaur
Jan 1 at 8:15
1
1
$begingroup$
You mean $ gcd(2^n-1,2^x-1)=1$?
$endgroup$
– PerelMan
Jan 1 at 8:17
$begingroup$
You mean $ gcd(2^n-1,2^x-1)=1$?
$endgroup$
– PerelMan
Jan 1 at 8:17
1
1
$begingroup$
Who has downvoted this question ? It is correctly asked. Everybody knows that (a,b) means gcd(a,b).
$endgroup$
– MikeTeX
Jan 1 at 8:48
$begingroup$
Who has downvoted this question ? It is correctly asked. Everybody knows that (a,b) means gcd(a,b).
$endgroup$
– MikeTeX
Jan 1 at 8:48
3
3
$begingroup$
Possible duplicate of Showing $gcd(2^m-1,2^n+1)=1$
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:00
$begingroup$
Possible duplicate of Showing $gcd(2^m-1,2^n+1)=1$
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:00
|
show 4 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Let $g = gcd(2^{n}-1, 2^{x}+1)$ (so $g$ is odd).
Since $g$ divide both numbers, it must divide their sum, that is $2^n+2^x$.
Assume for example that $nleq x$.
So $g$ divides $2^n(1+2^{x-n}) = 2^n + 2^x$. But $g$ is odd, hence it must in fact divide $1+2^{x-n}$. Repeat this argument with $x-n$ in place of $x$ above, and repeat it again an again as much as possible: So $g$ divides $1 + 2^{x - nq}$, where $q$ is such that $x-nq < n$ (Euclidean division). Let $r = x-nq$. We have now that $g$ divides $2^n-1$ and $2^r + 1$, hence it must divide their sum $2^r(2^{n-r} + 1)$, hence in fact $2^{n-r} + 1$. Repeat this argument as much as possible etc. etc., and you have finally that $g$ must divide $2^s + 1$, with $s = gcd(n,x)$ (Euclidean algorithm). The same argument works if in place of assuming $n leq x$ at the beginning, you assume $xleq n$, and leads to the same conclusion.
Let us write $n = st$, which is Ok since $s$ divides $n$. So $g$ divides $2^{st}-1$ and $2^s + 1$. Recall that
$$a^n - 1 = (a-1)(1+a+a^2+cdots + a^{n-1}),$$
hence
$$2^{st} - 1 = (2^s - 1)(1 + 2^s + 2^{2s} + cdots 2^{(t-1)s}).$$
$g$ is coprime to $2^s - 1$ otherwise, a non trivial factor of $g$ would divide both
$2^s - 1$ and $2^s + 1$, hence also their difference equal to 2. But $g$ is odd, hence this is impossible.
Consequently, $g$ must divide
$$1 + 2^s + 2^{2s} + cdots + 2^{(t-1)s},$$
and since $g$ divides $1+2^s$, it must divide
$$2^{2s}+cdots 2^{(t-1)s} = 2^{2s}(1+2^s+2^2s+cdots + 2^{(t-3)s}).$$
Consequently, it must divide
$$1+2^s+2^{2s}+cdots + 2^{(t-3)s}.$$
Repeat this argument again and again, until you obtain that $g$ divide
$$1+2^s+2^{(t-1-2k)s}$$
where $k$ is such that $t-1-2k = 2 or 3$.
But $n$ is odd, hence $t$ is odd and $t-1$ is even. So $t-1 -2k = 2$.
Finally $g$ divides $1+2^s+2^{2s}$, hence also $2^{2s}$. Since $g$ is odd, there must hold $g = 1$ (q.e.d). (sorry for the multiple edits)
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
$endgroup$
add a comment |
$begingroup$
Suppose $p$ is a prime factor of both $2^n-1$ and $2^x+1$ where $n$ is odd.
Then
$$2^nequiv1pmod p$$
and
$$2^xequiv-1pmod p.$$
Then
$$2^{nx}=(2^n)^xequiv1pmod p$$
and
$$2^{nx}=(2^x)^nequiv(-1)^n=-1pmod p.$$
Therefore
$$1equiv-1pmod p$$
and $p=2$, which is impossible.
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
$endgroup$
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
|
show 2 more comments
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $g = gcd(2^{n}-1, 2^{x}+1)$ (so $g$ is odd).
Since $g$ divide both numbers, it must divide their sum, that is $2^n+2^x$.
Assume for example that $nleq x$.
So $g$ divides $2^n(1+2^{x-n}) = 2^n + 2^x$. But $g$ is odd, hence it must in fact divide $1+2^{x-n}$. Repeat this argument with $x-n$ in place of $x$ above, and repeat it again an again as much as possible: So $g$ divides $1 + 2^{x - nq}$, where $q$ is such that $x-nq < n$ (Euclidean division). Let $r = x-nq$. We have now that $g$ divides $2^n-1$ and $2^r + 1$, hence it must divide their sum $2^r(2^{n-r} + 1)$, hence in fact $2^{n-r} + 1$. Repeat this argument as much as possible etc. etc., and you have finally that $g$ must divide $2^s + 1$, with $s = gcd(n,x)$ (Euclidean algorithm). The same argument works if in place of assuming $n leq x$ at the beginning, you assume $xleq n$, and leads to the same conclusion.
Let us write $n = st$, which is Ok since $s$ divides $n$. So $g$ divides $2^{st}-1$ and $2^s + 1$. Recall that
$$a^n - 1 = (a-1)(1+a+a^2+cdots + a^{n-1}),$$
hence
$$2^{st} - 1 = (2^s - 1)(1 + 2^s + 2^{2s} + cdots 2^{(t-1)s}).$$
$g$ is coprime to $2^s - 1$ otherwise, a non trivial factor of $g$ would divide both
$2^s - 1$ and $2^s + 1$, hence also their difference equal to 2. But $g$ is odd, hence this is impossible.
Consequently, $g$ must divide
$$1 + 2^s + 2^{2s} + cdots + 2^{(t-1)s},$$
and since $g$ divides $1+2^s$, it must divide
$$2^{2s}+cdots 2^{(t-1)s} = 2^{2s}(1+2^s+2^2s+cdots + 2^{(t-3)s}).$$
Consequently, it must divide
$$1+2^s+2^{2s}+cdots + 2^{(t-3)s}.$$
Repeat this argument again and again, until you obtain that $g$ divide
$$1+2^s+2^{(t-1-2k)s}$$
where $k$ is such that $t-1-2k = 2 or 3$.
But $n$ is odd, hence $t$ is odd and $t-1$ is even. So $t-1 -2k = 2$.
Finally $g$ divides $1+2^s+2^{2s}$, hence also $2^{2s}$. Since $g$ is odd, there must hold $g = 1$ (q.e.d). (sorry for the multiple edits)
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
$endgroup$
add a comment |
$begingroup$
Let $g = gcd(2^{n}-1, 2^{x}+1)$ (so $g$ is odd).
Since $g$ divide both numbers, it must divide their sum, that is $2^n+2^x$.
Assume for example that $nleq x$.
So $g$ divides $2^n(1+2^{x-n}) = 2^n + 2^x$. But $g$ is odd, hence it must in fact divide $1+2^{x-n}$. Repeat this argument with $x-n$ in place of $x$ above, and repeat it again an again as much as possible: So $g$ divides $1 + 2^{x - nq}$, where $q$ is such that $x-nq < n$ (Euclidean division). Let $r = x-nq$. We have now that $g$ divides $2^n-1$ and $2^r + 1$, hence it must divide their sum $2^r(2^{n-r} + 1)$, hence in fact $2^{n-r} + 1$. Repeat this argument as much as possible etc. etc., and you have finally that $g$ must divide $2^s + 1$, with $s = gcd(n,x)$ (Euclidean algorithm). The same argument works if in place of assuming $n leq x$ at the beginning, you assume $xleq n$, and leads to the same conclusion.
Let us write $n = st$, which is Ok since $s$ divides $n$. So $g$ divides $2^{st}-1$ and $2^s + 1$. Recall that
$$a^n - 1 = (a-1)(1+a+a^2+cdots + a^{n-1}),$$
hence
$$2^{st} - 1 = (2^s - 1)(1 + 2^s + 2^{2s} + cdots 2^{(t-1)s}).$$
$g$ is coprime to $2^s - 1$ otherwise, a non trivial factor of $g$ would divide both
$2^s - 1$ and $2^s + 1$, hence also their difference equal to 2. But $g$ is odd, hence this is impossible.
Consequently, $g$ must divide
$$1 + 2^s + 2^{2s} + cdots + 2^{(t-1)s},$$
and since $g$ divides $1+2^s$, it must divide
$$2^{2s}+cdots 2^{(t-1)s} = 2^{2s}(1+2^s+2^2s+cdots + 2^{(t-3)s}).$$
Consequently, it must divide
$$1+2^s+2^{2s}+cdots + 2^{(t-3)s}.$$
Repeat this argument again and again, until you obtain that $g$ divide
$$1+2^s+2^{(t-1-2k)s}$$
where $k$ is such that $t-1-2k = 2 or 3$.
But $n$ is odd, hence $t$ is odd and $t-1$ is even. So $t-1 -2k = 2$.
Finally $g$ divides $1+2^s+2^{2s}$, hence also $2^{2s}$. Since $g$ is odd, there must hold $g = 1$ (q.e.d). (sorry for the multiple edits)
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
$endgroup$
add a comment |
$begingroup$
Let $g = gcd(2^{n}-1, 2^{x}+1)$ (so $g$ is odd).
Since $g$ divide both numbers, it must divide their sum, that is $2^n+2^x$.
Assume for example that $nleq x$.
So $g$ divides $2^n(1+2^{x-n}) = 2^n + 2^x$. But $g$ is odd, hence it must in fact divide $1+2^{x-n}$. Repeat this argument with $x-n$ in place of $x$ above, and repeat it again an again as much as possible: So $g$ divides $1 + 2^{x - nq}$, where $q$ is such that $x-nq < n$ (Euclidean division). Let $r = x-nq$. We have now that $g$ divides $2^n-1$ and $2^r + 1$, hence it must divide their sum $2^r(2^{n-r} + 1)$, hence in fact $2^{n-r} + 1$. Repeat this argument as much as possible etc. etc., and you have finally that $g$ must divide $2^s + 1$, with $s = gcd(n,x)$ (Euclidean algorithm). The same argument works if in place of assuming $n leq x$ at the beginning, you assume $xleq n$, and leads to the same conclusion.
Let us write $n = st$, which is Ok since $s$ divides $n$. So $g$ divides $2^{st}-1$ and $2^s + 1$. Recall that
$$a^n - 1 = (a-1)(1+a+a^2+cdots + a^{n-1}),$$
hence
$$2^{st} - 1 = (2^s - 1)(1 + 2^s + 2^{2s} + cdots 2^{(t-1)s}).$$
$g$ is coprime to $2^s - 1$ otherwise, a non trivial factor of $g$ would divide both
$2^s - 1$ and $2^s + 1$, hence also their difference equal to 2. But $g$ is odd, hence this is impossible.
Consequently, $g$ must divide
$$1 + 2^s + 2^{2s} + cdots + 2^{(t-1)s},$$
and since $g$ divides $1+2^s$, it must divide
$$2^{2s}+cdots 2^{(t-1)s} = 2^{2s}(1+2^s+2^2s+cdots + 2^{(t-3)s}).$$
Consequently, it must divide
$$1+2^s+2^{2s}+cdots + 2^{(t-3)s}.$$
Repeat this argument again and again, until you obtain that $g$ divide
$$1+2^s+2^{(t-1-2k)s}$$
where $k$ is such that $t-1-2k = 2 or 3$.
But $n$ is odd, hence $t$ is odd and $t-1$ is even. So $t-1 -2k = 2$.
Finally $g$ divides $1+2^s+2^{2s}$, hence also $2^{2s}$. Since $g$ is odd, there must hold $g = 1$ (q.e.d). (sorry for the multiple edits)
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
$endgroup$
Let $g = gcd(2^{n}-1, 2^{x}+1)$ (so $g$ is odd).
Since $g$ divide both numbers, it must divide their sum, that is $2^n+2^x$.
Assume for example that $nleq x$.
So $g$ divides $2^n(1+2^{x-n}) = 2^n + 2^x$. But $g$ is odd, hence it must in fact divide $1+2^{x-n}$. Repeat this argument with $x-n$ in place of $x$ above, and repeat it again an again as much as possible: So $g$ divides $1 + 2^{x - nq}$, where $q$ is such that $x-nq < n$ (Euclidean division). Let $r = x-nq$. We have now that $g$ divides $2^n-1$ and $2^r + 1$, hence it must divide their sum $2^r(2^{n-r} + 1)$, hence in fact $2^{n-r} + 1$. Repeat this argument as much as possible etc. etc., and you have finally that $g$ must divide $2^s + 1$, with $s = gcd(n,x)$ (Euclidean algorithm). The same argument works if in place of assuming $n leq x$ at the beginning, you assume $xleq n$, and leads to the same conclusion.
Let us write $n = st$, which is Ok since $s$ divides $n$. So $g$ divides $2^{st}-1$ and $2^s + 1$. Recall that
$$a^n - 1 = (a-1)(1+a+a^2+cdots + a^{n-1}),$$
hence
$$2^{st} - 1 = (2^s - 1)(1 + 2^s + 2^{2s} + cdots 2^{(t-1)s}).$$
$g$ is coprime to $2^s - 1$ otherwise, a non trivial factor of $g$ would divide both
$2^s - 1$ and $2^s + 1$, hence also their difference equal to 2. But $g$ is odd, hence this is impossible.
Consequently, $g$ must divide
$$1 + 2^s + 2^{2s} + cdots + 2^{(t-1)s},$$
and since $g$ divides $1+2^s$, it must divide
$$2^{2s}+cdots 2^{(t-1)s} = 2^{2s}(1+2^s+2^2s+cdots + 2^{(t-3)s}).$$
Consequently, it must divide
$$1+2^s+2^{2s}+cdots + 2^{(t-3)s}.$$
Repeat this argument again and again, until you obtain that $g$ divide
$$1+2^s+2^{(t-1-2k)s}$$
where $k$ is such that $t-1-2k = 2 or 3$.
But $n$ is odd, hence $t$ is odd and $t-1$ is even. So $t-1 -2k = 2$.
Finally $g$ divides $1+2^s+2^{2s}$, hence also $2^{2s}$. Since $g$ is odd, there must hold $g = 1$ (q.e.d). (sorry for the multiple edits)
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
edited Jan 1 at 9:59
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
answered Jan 1 at 9:44
MikeTeXMikeTeX
1,301412
1,301412
add a comment |
add a comment |
$begingroup$
Suppose $p$ is a prime factor of both $2^n-1$ and $2^x+1$ where $n$ is odd.
Then
$$2^nequiv1pmod p$$
and
$$2^xequiv-1pmod p.$$
Then
$$2^{nx}=(2^n)^xequiv1pmod p$$
and
$$2^{nx}=(2^x)^nequiv(-1)^n=-1pmod p.$$
Therefore
$$1equiv-1pmod p$$
and $p=2$, which is impossible.
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
$endgroup$
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
|
show 2 more comments
$begingroup$
Suppose $p$ is a prime factor of both $2^n-1$ and $2^x+1$ where $n$ is odd.
Then
$$2^nequiv1pmod p$$
and
$$2^xequiv-1pmod p.$$
Then
$$2^{nx}=(2^n)^xequiv1pmod p$$
and
$$2^{nx}=(2^x)^nequiv(-1)^n=-1pmod p.$$
Therefore
$$1equiv-1pmod p$$
and $p=2$, which is impossible.
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
$endgroup$
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
|
show 2 more comments
$begingroup$
Suppose $p$ is a prime factor of both $2^n-1$ and $2^x+1$ where $n$ is odd.
Then
$$2^nequiv1pmod p$$
and
$$2^xequiv-1pmod p.$$
Then
$$2^{nx}=(2^n)^xequiv1pmod p$$
and
$$2^{nx}=(2^x)^nequiv(-1)^n=-1pmod p.$$
Therefore
$$1equiv-1pmod p$$
and $p=2$, which is impossible.
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
$endgroup$
Suppose $p$ is a prime factor of both $2^n-1$ and $2^x+1$ where $n$ is odd.
Then
$$2^nequiv1pmod p$$
and
$$2^xequiv-1pmod p.$$
Then
$$2^{nx}=(2^n)^xequiv1pmod p$$
and
$$2^{nx}=(2^x)^nequiv(-1)^n=-1pmod p.$$
Therefore
$$1equiv-1pmod p$$
and $p=2$, which is impossible.
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
answered Jan 1 at 9:48
Lord Shark the UnknownLord Shark the Unknown
102k959132
102k959132
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
|
show 2 more comments
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
Very concise & lovely answer.
$endgroup$
– John Omielan
Jan 1 at 9:50
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
very clever argument, admittedly better than mine. But it uses congruence basic notation and theory which is not necessarily available to all. Also, I think at the end of your answer you mean "which is impossible, unless $p = 2$. But $pnot = 2$ since the two given numbers are odd."
$endgroup$
– MikeTeX
Jan 1 at 10:03
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
A fine answer. IMHO it would do well also in the dupe target thread.
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:04
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
Can you explain how did you get p=2?What does 1=-1(mod p) stand for ?
$endgroup$
– Melina
Jan 1 at 10:53
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
$begingroup$
@Melina I wrote $1equiv-1pmod p$, not $1=-1pmod p$. This is a congruence: en.wikipedia.org/wiki/Modular_arithmetic
$endgroup$
– Lord Shark the Unknown
Jan 1 at 11:46
|
show 2 more comments
$begingroup$
OP, please clarify what $(2^n_- 1, 2^x_+ 1) = 1$ is supposed to be. I just edited with correct typesetting based on what you had. Did you mean $(2^n - 1, 2^x + 1) = 1$?
$endgroup$
– The Pointer
Jan 1 at 8:10
$begingroup$
Do you mean that it reduces to identity?
$endgroup$
– Colebasaur
Jan 1 at 8:15
1
$begingroup$
You mean $ gcd(2^n-1,2^x-1)=1$?
$endgroup$
– PerelMan
Jan 1 at 8:17
1
$begingroup$
Who has downvoted this question ? It is correctly asked. Everybody knows that (a,b) means gcd(a,b).
$endgroup$
– MikeTeX
Jan 1 at 8:48
3
$begingroup$
Possible duplicate of Showing $gcd(2^m-1,2^n+1)=1$
$endgroup$
– Jyrki Lahtonen
Jan 1 at 10:00