Mixing
How to prove an equivalence of two equations?
up vote
0
down vote
favorite
Task:
Prove that . $s cdot a + t cdot b = c$ has a solution $s, t in mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $.
I’m not sure whether my proof is correct or not, so pleas have a look on it:
It’s to show that $s cdot a + t cdot b = c Leftrightarrow gcd(a,b) cdot p = c$
“$Rightarrow$”:
Hypothesis: $s cdot a + t cdot b = c$
Consequence: Then $gcd(a,b) cdot p = c$
Proof: $gcd(a,b) cdot p = s cdot a + t cdot b$
$Leftrightarrow p = s cdot frac{a}{gcd(a, b)} + t cdot frac{b}{gcd(a, b)} = s cdot q + t cdot r$ such that $q = frac{a}{gcd(a, b)} in mathbb{Z}$ and $r = frac{b}{gcd(a, b)} in mathbb{Z}$
So there exists a $p in mathbb{Z}$ for the equation so the implication is shown.
For the proof of “$Leftarrow$” I’ll take a very similar way:
Hypothesis: $gcd(a,b) cdot p = c$
Consequence: Then $s cdot a + t cdot b = c$
Proof: $s cdot a + t cdot b = gcd(a,b) cdot p$
From here are the steps identical to the previous proof.
I could also use the proposition of Bézout for “$Rightarrow$” and “$Leftarrow$” which says: $s cdot a + t cdot b = gcd(a,b) $
Then I get for both proofs $p=1$.
So I’m not sure if my solution is correct, especially because the proofs for “$Rightarrow$” and “$Leftarrow$” are identical.
Could anyone please help?
Thanks
Best regards
Asg
proof-verification divisibility greatest-common-divisor
asked 4 hours ago
Asg
84
add a comment |
up vote
0
down vote
favorite
Task:
Prove that . $s cdot a + t cdot b = c$ has a solution $s, t in mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $.
I’m not sure whether my proof is correct or not, so pleas have a look on it:
It’s to show that $s cdot a + t cdot b = c Leftrightarrow gcd(a,b) cdot p = c$
“$Rightarrow$”:
Hypothesis: $s cdot a + t cdot b = c$
Consequence: Then $gcd(a,b) cdot p = c$
Proof: $gcd(a,b) cdot p = s cdot a + t cdot b$
$Leftrightarrow p = s cdot frac{a}{gcd(a, b)} + t cdot frac{b}{gcd(a, b)} = s cdot q + t cdot r$ such that $q = frac{a}{gcd(a, b)} in mathbb{Z}$ and $r = frac{b}{gcd(a, b)} in mathbb{Z}$
So there exists a $p in mathbb{Z}$ for the equation so the implication is shown.
For the proof of “$Leftarrow$” I’ll take a very similar way:
Hypothesis: $gcd(a,b) cdot p = c$
Consequence: Then $s cdot a + t cdot b = c$
Proof: $s cdot a + t cdot b = gcd(a,b) cdot p$
From here are the steps identical to the previous proof.
I could also use the proposition of Bézout for “$Rightarrow$” and “$Leftarrow$” which says: $s cdot a + t cdot b = gcd(a,b) $
Then I get for both proofs $p=1$.
So I’m not sure if my solution is correct, especially because the proofs for “$Rightarrow$” and “$Leftarrow$” are identical.
Could anyone please help?
Thanks
Best regards
Asg
proof-verification divisibility greatest-common-divisor
asked 4 hours ago
Asg
84
What is ggT? Is it the same as gcd?
– Taladris
4 hours ago
Yes, it was my mistake, I corrected now. Thanks!
– Asg
4 hours ago
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Task:
Prove that . $s cdot a + t cdot b = c$ has a solution $s, t in mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $.
I’m not sure whether my proof is correct or not, so pleas have a look on it:
It’s to show that $s cdot a + t cdot b = c Leftrightarrow gcd(a,b) cdot p = c$
“$Rightarrow$”:
Hypothesis: $s cdot a + t cdot b = c$
Consequence: Then $gcd(a,b) cdot p = c$
Proof: $gcd(a,b) cdot p = s cdot a + t cdot b$
$Leftrightarrow p = s cdot frac{a}{gcd(a, b)} + t cdot frac{b}{gcd(a, b)} = s cdot q + t cdot r$ such that $q = frac{a}{gcd(a, b)} in mathbb{Z}$ and $r = frac{b}{gcd(a, b)} in mathbb{Z}$
So there exists a $p in mathbb{Z}$ for the equation so the implication is shown.
For the proof of “$Leftarrow$” I’ll take a very similar way:
Hypothesis: $gcd(a,b) cdot p = c$
Consequence: Then $s cdot a + t cdot b = c$
Proof: $s cdot a + t cdot b = gcd(a,b) cdot p$
From here are the steps identical to the previous proof.
I could also use the proposition of Bézout for “$Rightarrow$” and “$Leftarrow$” which says: $s cdot a + t cdot b = gcd(a,b) $
Then I get for both proofs $p=1$.
So I’m not sure if my solution is correct, especially because the proofs for “$Rightarrow$” and “$Leftarrow$” are identical.
Could anyone please help?
Thanks
Best regards
Asg
proof-verification divisibility greatest-common-divisor
asked 4 hours ago
Asg
84
Task:
Prove that . $s cdot a + t cdot b = c$ has a solution $s, t in mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $.
I’m not sure whether my proof is correct or not, so pleas have a look on it:
It’s to show that $s cdot a + t cdot b = c Leftrightarrow gcd(a,b) cdot p = c$
“$Rightarrow$”:
Hypothesis: $s cdot a + t cdot b = c$
Consequence: Then $gcd(a,b) cdot p = c$
Proof: $gcd(a,b) cdot p = s cdot a + t cdot b$
$Leftrightarrow p = s cdot frac{a}{gcd(a, b)} + t cdot frac{b}{gcd(a, b)} = s cdot q + t cdot r$ such that $q = frac{a}{gcd(a, b)} in mathbb{Z}$ and $r = frac{b}{gcd(a, b)} in mathbb{Z}$
So there exists a $p in mathbb{Z}$ for the equation so the implication is shown.
For the proof of “$Leftarrow$” I’ll take a very similar way:
Hypothesis: $gcd(a,b) cdot p = c$
Consequence: Then $s cdot a + t cdot b = c$
Proof: $s cdot a + t cdot b = gcd(a,b) cdot p$
From here are the steps identical to the previous proof.
I could also use the proposition of Bézout for “$Rightarrow$” and “$Leftarrow$” which says: $s cdot a + t cdot b = gcd(a,b) $
Then I get for both proofs $p=1$.
So I’m not sure if my solution is correct, especially because the proofs for “$Rightarrow$” and “$Leftarrow$” are identical.
Could anyone please help?
Thanks
Best regards
Asg
proof-verification divisibility greatest-common-divisor
proof-verification divisibility greatest-common-divisor
asked 4 hours ago
Asg
84
asked 4 hours ago
Asg
84
edited 2 hours ago
asked 4 hours ago
Asg
84
asked 4 hours ago
Asg
84
asked 4 hours ago
Asg
84
84
What is ggT? Is it the same as gcd?
– Taladris
4 hours ago
Yes, it was my mistake, I corrected now. Thanks!
– Asg
4 hours ago
add a comment |
What is ggT? Is it the same as gcd?
– Taladris
4 hours ago
Yes, it was my mistake, I corrected now. Thanks!
– Asg
4 hours ago
What is ggT? Is it the same as gcd?
– Taladris
4 hours ago
What is ggT? Is it the same as gcd?
– Taladris
4 hours ago
Yes, it was my mistake, I corrected now. Thanks!
– Asg
4 hours ago
Yes, it was my mistake, I corrected now. Thanks!
– Asg
4 hours ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
No, it is not correct. There are several issues.
- You wrote that what's to be proved is that$$stimes a + ttimes b = c iffgcd(a,b)times p = c.$$It is not. It is:$$(exists s,tinmathbb{Z}):stimes a+ttimes b=ciff(exists pinmathbb{Z}):gcd(a,b)times p=c.$$
- The idea of the proof of $implies$ is correct. The proof of $Longleftarrow$ makes no sense. You cannot just say that “the steps are identical”. The goal is to prove that there are integers $s$ and $t$ such that $stimes a+ttimes b=c$ assuming that there is an integer $p$ such that $gcd(a,b)times p=c$. You did no such thing.
answered 4 hours ago
José Carlos Santos
139k18111202
Oh I see. Thank you for your quick help.
– Asg
2 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
0
down vote
accepted
No, it is not correct. There are several issues.
- You wrote that what's to be proved is that$$stimes a + ttimes b = c iffgcd(a,b)times p = c.$$It is not. It is:$$(exists s,tinmathbb{Z}):stimes a+ttimes b=ciff(exists pinmathbb{Z}):gcd(a,b)times p=c.$$
- The idea of the proof of $implies$ is correct. The proof of $Longleftarrow$ makes no sense. You cannot just say that “the steps are identical”. The goal is to prove that there are integers $s$ and $t$ such that $stimes a+ttimes b=c$ assuming that there is an integer $p$ such that $gcd(a,b)times p=c$. You did no such thing.
answered 4 hours ago
José Carlos Santos
139k18111202
Oh I see. Thank you for your quick help.
– Asg
2 hours ago
add a comment |
up vote
0
down vote
accepted
No, it is not correct. There are several issues.
- You wrote that what's to be proved is that$$stimes a + ttimes b = c iffgcd(a,b)times p = c.$$It is not. It is:$$(exists s,tinmathbb{Z}):stimes a+ttimes b=ciff(exists pinmathbb{Z}):gcd(a,b)times p=c.$$
- The idea of the proof of $implies$ is correct. The proof of $Longleftarrow$ makes no sense. You cannot just say that “the steps are identical”. The goal is to prove that there are integers $s$ and $t$ such that $stimes a+ttimes b=c$ assuming that there is an integer $p$ such that $gcd(a,b)times p=c$. You did no such thing.
answered 4 hours ago
José Carlos Santos
139k18111202
Oh I see. Thank you for your quick help.
– Asg
2 hours ago
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
No, it is not correct. There are several issues.
- You wrote that what's to be proved is that$$stimes a + ttimes b = c iffgcd(a,b)times p = c.$$It is not. It is:$$(exists s,tinmathbb{Z}):stimes a+ttimes b=ciff(exists pinmathbb{Z}):gcd(a,b)times p=c.$$
- The idea of the proof of $implies$ is correct. The proof of $Longleftarrow$ makes no sense. You cannot just say that “the steps are identical”. The goal is to prove that there are integers $s$ and $t$ such that $stimes a+ttimes b=c$ assuming that there is an integer $p$ such that $gcd(a,b)times p=c$. You did no such thing.
answered 4 hours ago
José Carlos Santos
139k18111202
No, it is not correct. There are several issues.
- You wrote that what's to be proved is that$$stimes a + ttimes b = c iffgcd(a,b)times p = c.$$It is not. It is:$$(exists s,tinmathbb{Z}):stimes a+ttimes b=ciff(exists pinmathbb{Z}):gcd(a,b)times p=c.$$
- The idea of the proof of $implies$ is correct. The proof of $Longleftarrow$ makes no sense. You cannot just say that “the steps are identical”. The goal is to prove that there are integers $s$ and $t$ such that $stimes a+ttimes b=c$ assuming that there is an integer $p$ such that $gcd(a,b)times p=c$. You did no such thing.
answered 4 hours ago
José Carlos Santos
139k18111202
answered 4 hours ago
José Carlos Santos
139k18111202
answered 4 hours ago
José Carlos Santos
139k18111202
answered 4 hours ago
José Carlos Santos
139k18111202
139k18111202
Oh I see. Thank you for your quick help.
– Asg
2 hours ago
add a comment |
Oh I see. Thank you for your quick help.
– Asg
2 hours ago
Oh I see. Thank you for your quick help.
– Asg
2 hours ago
Oh I see. Thank you for your quick help.
– Asg
2 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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004624%2fhow-to-prove-an-equivalence-of-two-equations%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
What is ggT? Is it the same as gcd?
– Taladris
4 hours ago
Yes, it was my mistake, I corrected now. Thanks!
– Asg
4 hours ago