Mixing
How $gcd (s,t)=1$ implies $gcd(s-t,s+t) =1$?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let $s$ and $t$ be two relatively prime odd numbers. We want to know the $d=gcd(s-t,s+t).$ Let $d=2^lm$ thus $s-t=2^lmk_1$ and $s+t=2^lmk_2$ for $k_1$ and $k_2$ odd numbers and $gcd(k_1, k_2)=1.$ Summing and subtracting both sides of two equality-es and diving by $2$ results in $s=2^lm frac(k_1+k_2)2$ and $t=2^lm frac(k_2-k_1)2$ in which $frac(k_2 pm k_1)2$ are integers as both $k_1$ and $k_2$ are odd numbers and because $s$ and $t$ are relatively prime implies $l=0$ which is not possible since both $s-t$ and $s+t$ are even so must $l ge 1$ !! Contradiction?
A rewritten version of this same question, for the author's benefit:
Let $s$ and $t$ be two distinct relatively prime odd numbers.
We want to compute $d=gcd(s-t,s+t).$ Note that $s-t$ and $s+t$ are both nonzero because $s$ and $t$ are distinct.
Let $d=2^ell m$, where $m$ is odd. Then since $s-t$ and $s+t$ are both multiples of $d$, we have
beginalign
s-t&=2^ell mk_1 textand\
s+t&=2^ell mk_2
endalign
where $k_1$ and $k_2$ are both odd. Furthermore, $gcd(k_1, k_2)=1,$ for if it were some other number $u > 1$, then $ud$ would divide both $s+t$ and $s-t$, contradicting the fact that $d$ is their greatest common divisor.
Finally, since both $s-t$ and $s+t$ are even and nonzero, we must have $ell ge 1$, which we'll use shortly.
Summing and subtracting both sides of these two equalities and dividing by $2$ gives
beginalign
s&=2^ell m frac(k_1+k_2)2 text and\
t& =2^ell m frac(k_2-k_1)2
endalign
Note that because $k_1$ and $k_2$ are both odd, their sum and difference are both even, hence
$frac(k_2 pm k_1)2$ are both integers.
Now $s$ and $t$ are relatively prime (given), so $ell$ must be zero (otherwise $2^ell$ would divide both, and the gcd could not be $1$).
On the other hand, we showed above that $ell ge 1$. That's a contradiction.
=====
Now there's definitely something screwy in the "proof" above, because Jyrki's example shows that the gcd is actually $2$. But you'll have a lot easier time finding the error now that the "proof" is actually written clearly and coherently.
elementary-number-theory
edited 5 hours ago
John Hughes
59.3k23685
asked 6 hours ago
Edi
1,114728
add a comment |Â
up vote
0
down vote
favorite
Let $s$ and $t$ be two relatively prime odd numbers. We want to know the $d=gcd(s-t,s+t).$ Let $d=2^lm$ thus $s-t=2^lmk_1$ and $s+t=2^lmk_2$ for $k_1$ and $k_2$ odd numbers and $gcd(k_1, k_2)=1.$ Summing and subtracting both sides of two equality-es and diving by $2$ results in $s=2^lm frac(k_1+k_2)2$ and $t=2^lm frac(k_2-k_1)2$ in which $frac(k_2 pm k_1)2$ are integers as both $k_1$ and $k_2$ are odd numbers and because $s$ and $t$ are relatively prime implies $l=0$ which is not possible since both $s-t$ and $s+t$ are even so must $l ge 1$ !! Contradiction?
A rewritten version of this same question, for the author's benefit:
Let $s$ and $t$ be two distinct relatively prime odd numbers.
We want to compute $d=gcd(s-t,s+t).$ Note that $s-t$ and $s+t$ are both nonzero because $s$ and $t$ are distinct.
Let $d=2^ell m$, where $m$ is odd. Then since $s-t$ and $s+t$ are both multiples of $d$, we have
beginalign
s-t&=2^ell mk_1 textand\
s+t&=2^ell mk_2
endalign
where $k_1$ and $k_2$ are both odd. Furthermore, $gcd(k_1, k_2)=1,$ for if it were some other number $u > 1$, then $ud$ would divide both $s+t$ and $s-t$, contradicting the fact that $d$ is their greatest common divisor.
Finally, since both $s-t$ and $s+t$ are even and nonzero, we must have $ell ge 1$, which we'll use shortly.
Summing and subtracting both sides of these two equalities and dividing by $2$ gives
beginalign
s&=2^ell m frac(k_1+k_2)2 text and\
t& =2^ell m frac(k_2-k_1)2
endalign
Note that because $k_1$ and $k_2$ are both odd, their sum and difference are both even, hence
$frac(k_2 pm k_1)2$ are both integers.
Now $s$ and $t$ are relatively prime (given), so $ell$ must be zero (otherwise $2^ell$ would divide both, and the gcd could not be $1$).
On the other hand, we showed above that $ell ge 1$. That's a contradiction.
=====
Now there's definitely something screwy in the "proof" above, because Jyrki's example shows that the gcd is actually $2$. But you'll have a lot easier time finding the error now that the "proof" is actually written clearly and coherently.
elementary-number-theory
edited 5 hours ago
John Hughes
59.3k23685
asked 6 hours ago
Edi
1,114728
2
$s=5,t=3implies s+t=8, s-t=2$ and $gcd(s+t,s-t)=?$
– Jyrki Lahtonen
6 hours ago
1
If $s$ and $t$ are two relatively prime odd numbers, then $gcd(s+t,s-t)=2$.
– Batominovski
6 hours ago
@Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title.
– Edi
6 hours ago
2
Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding.
– John Hughes
6 hours ago
@JohnHughes, of course it matters. Thanks a lot for your suggestion. :)
– Edi
6 hours ago
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $s$ and $t$ be two relatively prime odd numbers. We want to know the $d=gcd(s-t,s+t).$ Let $d=2^lm$ thus $s-t=2^lmk_1$ and $s+t=2^lmk_2$ for $k_1$ and $k_2$ odd numbers and $gcd(k_1, k_2)=1.$ Summing and subtracting both sides of two equality-es and diving by $2$ results in $s=2^lm frac(k_1+k_2)2$ and $t=2^lm frac(k_2-k_1)2$ in which $frac(k_2 pm k_1)2$ are integers as both $k_1$ and $k_2$ are odd numbers and because $s$ and $t$ are relatively prime implies $l=0$ which is not possible since both $s-t$ and $s+t$ are even so must $l ge 1$ !! Contradiction?
A rewritten version of this same question, for the author's benefit:
Let $s$ and $t$ be two distinct relatively prime odd numbers.
We want to compute $d=gcd(s-t,s+t).$ Note that $s-t$ and $s+t$ are both nonzero because $s$ and $t$ are distinct.
Let $d=2^ell m$, where $m$ is odd. Then since $s-t$ and $s+t$ are both multiples of $d$, we have
beginalign
s-t&=2^ell mk_1 textand\
s+t&=2^ell mk_2
endalign
where $k_1$ and $k_2$ are both odd. Furthermore, $gcd(k_1, k_2)=1,$ for if it were some other number $u > 1$, then $ud$ would divide both $s+t$ and $s-t$, contradicting the fact that $d$ is their greatest common divisor.
Finally, since both $s-t$ and $s+t$ are even and nonzero, we must have $ell ge 1$, which we'll use shortly.
Summing and subtracting both sides of these two equalities and dividing by $2$ gives
beginalign
s&=2^ell m frac(k_1+k_2)2 text and\
t& =2^ell m frac(k_2-k_1)2
endalign
Note that because $k_1$ and $k_2$ are both odd, their sum and difference are both even, hence
$frac(k_2 pm k_1)2$ are both integers.
Now $s$ and $t$ are relatively prime (given), so $ell$ must be zero (otherwise $2^ell$ would divide both, and the gcd could not be $1$).
On the other hand, we showed above that $ell ge 1$. That's a contradiction.
=====
Now there's definitely something screwy in the "proof" above, because Jyrki's example shows that the gcd is actually $2$. But you'll have a lot easier time finding the error now that the "proof" is actually written clearly and coherently.
elementary-number-theory
edited 5 hours ago
John Hughes
59.3k23685
asked 6 hours ago
Edi
1,114728
Let $s$ and $t$ be two relatively prime odd numbers. We want to know the $d=gcd(s-t,s+t).$ Let $d=2^lm$ thus $s-t=2^lmk_1$ and $s+t=2^lmk_2$ for $k_1$ and $k_2$ odd numbers and $gcd(k_1, k_2)=1.$ Summing and subtracting both sides of two equality-es and diving by $2$ results in $s=2^lm frac(k_1+k_2)2$ and $t=2^lm frac(k_2-k_1)2$ in which $frac(k_2 pm k_1)2$ are integers as both $k_1$ and $k_2$ are odd numbers and because $s$ and $t$ are relatively prime implies $l=0$ which is not possible since both $s-t$ and $s+t$ are even so must $l ge 1$ !! Contradiction?
A rewritten version of this same question, for the author's benefit:
Let $s$ and $t$ be two distinct relatively prime odd numbers.
We want to compute $d=gcd(s-t,s+t).$ Note that $s-t$ and $s+t$ are both nonzero because $s$ and $t$ are distinct.
Let $d=2^ell m$, where $m$ is odd. Then since $s-t$ and $s+t$ are both multiples of $d$, we have
beginalign
s-t&=2^ell mk_1 textand\
s+t&=2^ell mk_2
endalign
where $k_1$ and $k_2$ are both odd. Furthermore, $gcd(k_1, k_2)=1,$ for if it were some other number $u > 1$, then $ud$ would divide both $s+t$ and $s-t$, contradicting the fact that $d$ is their greatest common divisor.
Finally, since both $s-t$ and $s+t$ are even and nonzero, we must have $ell ge 1$, which we'll use shortly.
Summing and subtracting both sides of these two equalities and dividing by $2$ gives
beginalign
s&=2^ell m frac(k_1+k_2)2 text and\
t& =2^ell m frac(k_2-k_1)2
endalign
Note that because $k_1$ and $k_2$ are both odd, their sum and difference are both even, hence
$frac(k_2 pm k_1)2$ are both integers.
Now $s$ and $t$ are relatively prime (given), so $ell$ must be zero (otherwise $2^ell$ would divide both, and the gcd could not be $1$).
On the other hand, we showed above that $ell ge 1$. That's a contradiction.
=====
Now there's definitely something screwy in the "proof" above, because Jyrki's example shows that the gcd is actually $2$. But you'll have a lot easier time finding the error now that the "proof" is actually written clearly and coherently.
elementary-number-theory
edited 5 hours ago
John Hughes
59.3k23685
asked 6 hours ago
Edi
1,114728
edited 5 hours ago
John Hughes
59.3k23685
edited 5 hours ago
John Hughes
59.3k23685
edited 5 hours ago
John Hughes
59.3k23685
59.3k23685
asked 6 hours ago
Edi
1,114728
asked 6 hours ago
Edi
1,114728
asked 6 hours ago
Edi
1,114728
1,114728
2
$s=5,t=3implies s+t=8, s-t=2$ and $gcd(s+t,s-t)=?$
– Jyrki Lahtonen
6 hours ago
1
If $s$ and $t$ are two relatively prime odd numbers, then $gcd(s+t,s-t)=2$.
– Batominovski
6 hours ago
@Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title.
– Edi
6 hours ago
2
Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding.
– John Hughes
6 hours ago
@JohnHughes, of course it matters. Thanks a lot for your suggestion. :)
– Edi
6 hours ago
add a comment |Â
2
$s=5,t=3implies s+t=8, s-t=2$ and $gcd(s+t,s-t)=?$
– Jyrki Lahtonen
6 hours ago
1
If $s$ and $t$ are two relatively prime odd numbers, then $gcd(s+t,s-t)=2$.
– Batominovski
6 hours ago
@Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title.
– Edi
6 hours ago
2
Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding.
– John Hughes
6 hours ago
@JohnHughes, of course it matters. Thanks a lot for your suggestion. :)
– Edi
6 hours ago
2
2
$s=5,t=3implies s+t=8, s-t=2$ and $gcd(s+t,s-t)=?$
– Jyrki Lahtonen
6 hours ago
$s=5,t=3implies s+t=8, s-t=2$ and $gcd(s+t,s-t)=?$
– Jyrki Lahtonen
6 hours ago
1
1
If $s$ and $t$ are two relatively prime odd numbers, then $gcd(s+t,s-t)=2$.
– Batominovski
6 hours ago
If $s$ and $t$ are two relatively prime odd numbers, then $gcd(s+t,s-t)=2$.
– Batominovski
6 hours ago
@Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title.
– Edi
6 hours ago
@Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title.
– Edi
6 hours ago
2
2
Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding.
– John Hughes
6 hours ago
Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding.
– John Hughes
6 hours ago
@JohnHughes, of course it matters. Thanks a lot for your suggestion. :)
– Edi
6 hours ago
@JohnHughes, of course it matters. Thanks a lot for your suggestion. :)
– Edi
6 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
$k_1$ and $k_2$ don't have to be odd numbers, only one of them has to be. If $s$ and $t$ are both odd, $s+t$ and $s-t$ are both even, so you know that $d$ is also even.
answered 6 hours ago
TitiMcMath
463
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
2
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
$k_1$ and $k_2$ don't have to be odd numbers, only one of them has to be. If $s$ and $t$ are both odd, $s+t$ and $s-t$ are both even, so you know that $d$ is also even.
answered 6 hours ago
TitiMcMath
463
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
2
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
add a comment |Â
up vote
2
down vote
accepted
$k_1$ and $k_2$ don't have to be odd numbers, only one of them has to be. If $s$ and $t$ are both odd, $s+t$ and $s-t$ are both even, so you know that $d$ is also even.
answered 6 hours ago
TitiMcMath
463
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
2
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
$k_1$ and $k_2$ don't have to be odd numbers, only one of them has to be. If $s$ and $t$ are both odd, $s+t$ and $s-t$ are both even, so you know that $d$ is also even.
answered 6 hours ago
TitiMcMath
463
$k_1$ and $k_2$ don't have to be odd numbers, only one of them has to be. If $s$ and $t$ are both odd, $s+t$ and $s-t$ are both even, so you know that $d$ is also even.
answered 6 hours ago
TitiMcMath
463
answered 6 hours ago
TitiMcMath
463
answered 6 hours ago
TitiMcMath
463
answered 6 hours ago
TitiMcMath
463
463
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
2
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
add a comment |Â
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
2
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
I factored all 2's so that k_1 and k_2 be odds
– Edi
6 hours ago
2
2
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
It could be that $s-t=4cdottextodd$ but $s+t=2cdottextodd$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$.
– Batominovski
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
Exactly, take $s=5$ and $t=1$ for example
– TitiMcMath
6 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
I've edited your question to add a reformatted "proof" that is (I believe) much more readable.
– John Hughes
4 hours ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873329%2fhow-gcd-s-t-1-implies-gcds-t-st-1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
$s=5,t=3implies s+t=8, s-t=2$ and $gcd(s+t,s-t)=?$
– Jyrki Lahtonen
6 hours ago
1
If $s$ and $t$ are two relatively prime odd numbers, then $gcd(s+t,s-t)=2$.
– Batominovski
6 hours ago
@Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title.
– Edi
6 hours ago
2
Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding.
– John Hughes
6 hours ago
@JohnHughes, of course it matters. Thanks a lot for your suggestion. :)
– Edi
6 hours ago