Doubt in proof of Euclidean Algorithm Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Clarification on the proof for the Euclidean algorithmproblem with GCD/Euclidean algorithmExtended Euclidean Algorithm, what is our answer?Proving the number of iterations in the Euclidean algorithmEuclidean Algorithm (gcd)Diophantine equations using Euclidean algorithmProof of cardinality of fibres - why finiteness condition?Extended Euclidean Algorithm As Row OperationsEuclidean algorithm matrix proofEuclidean Algorithm Proof
How to assign captions for two tables in LaTeX?
"Seemed to had" is it correct?
Do I really need recursive chmod to restrict access to a folder?
Is 1 ppb equal to 1 μg/kg?
What LEGO pieces have "real-world" functionality?
3 doors, three guards, one stone
Examples of mediopassive verb constructions
What is the correct way to use the pinch test for dehydration?
Do you forfeit tax refunds/credits if you aren't required to and don't file by April 15?
I am not a queen, who am I?
What's the purpose of writing one's academic bio in 3rd person?
Did Kevin spill real chili?
How do I stop a creek from eroding my steep embankment?
What do you call a plan that's an alternative plan in case your initial plan fails?
Disable hyphenation for an entire paragraph
If Jon Snow became King of the Seven Kingdoms what would his regnal number be?
When is phishing education going too far?
List *all* the tuples!
How much radiation do nuclear physics experiments expose researchers to nowadays?
Should I call the interviewer directly, if HR aren't responding?
Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?
Is there a documented rationale why the House Ways and Means chairman can demand tax info?
Why are there no cargo aircraft with "flying wing" design?
Single word antonym of "flightless"
Doubt in proof of Euclidean Algorithm
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Clarification on the proof for the Euclidean algorithmproblem with GCD/Euclidean algorithmExtended Euclidean Algorithm, what is our answer?Proving the number of iterations in the Euclidean algorithmEuclidean Algorithm (gcd)Diophantine equations using Euclidean algorithmProof of cardinality of fibres - why finiteness condition?Extended Euclidean Algorithm As Row OperationsEuclidean algorithm matrix proofEuclidean Algorithm Proof
$begingroup$
I got this text from https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf
Is it necessary for the proof to suppose:
"Now suppose $d$ is a common divisor of $b$ and $r$..."
By showing that if $d|a$ and $d|b$ then $d|(a-bq)$ aren't we already showing that the set of common dividers for $a$ and $b$ are the same $r$ and $b$?
proof-explanation euclidean-algorithm
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
$endgroup$
add a comment |
$begingroup$
I got this text from https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf
Is it necessary for the proof to suppose:
"Now suppose $d$ is a common divisor of $b$ and $r$..."
By showing that if $d|a$ and $d|b$ then $d|(a-bq)$ aren't we already showing that the set of common dividers for $a$ and $b$ are the same $r$ and $b$?
proof-explanation euclidean-algorithm
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
$endgroup$
$begingroup$
No, you've shown that each common divisor of $a$, $b$ is a common divisor of $b$, $r$. You have not yet shown that each common divisor of $b$, $r$ is a common divisor of $a$, $b$.
$endgroup$
– Lord Shark the Unknown
Apr 10 at 13:51
$begingroup$
So ANY divisor of $a$ and $b$ is also a divisor or $r$?
$endgroup$
– João Pedro
Apr 10 at 14:08
add a comment |
$begingroup$
I got this text from https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf
Is it necessary for the proof to suppose:
"Now suppose $d$ is a common divisor of $b$ and $r$..."
By showing that if $d|a$ and $d|b$ then $d|(a-bq)$ aren't we already showing that the set of common dividers for $a$ and $b$ are the same $r$ and $b$?
proof-explanation euclidean-algorithm
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
$endgroup$
I got this text from https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf
Is it necessary for the proof to suppose:
"Now suppose $d$ is a common divisor of $b$ and $r$..."
By showing that if $d|a$ and $d|b$ then $d|(a-bq)$ aren't we already showing that the set of common dividers for $a$ and $b$ are the same $r$ and $b$?
proof-explanation euclidean-algorithm
proof-explanation euclidean-algorithm
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
asked Apr 10 at 13:46
João PedroJoão Pedro
354118
354118
$begingroup$
No, you've shown that each common divisor of $a$, $b$ is a common divisor of $b$, $r$. You have not yet shown that each common divisor of $b$, $r$ is a common divisor of $a$, $b$.
$endgroup$
– Lord Shark the Unknown
Apr 10 at 13:51
$begingroup$
So ANY divisor of $a$ and $b$ is also a divisor or $r$?
$endgroup$
– João Pedro
Apr 10 at 14:08
add a comment |
$begingroup$
No, you've shown that each common divisor of $a$, $b$ is a common divisor of $b$, $r$. You have not yet shown that each common divisor of $b$, $r$ is a common divisor of $a$, $b$.
$endgroup$
– Lord Shark the Unknown
Apr 10 at 13:51
$begingroup$
So ANY divisor of $a$ and $b$ is also a divisor or $r$?
$endgroup$
– João Pedro
Apr 10 at 14:08
$begingroup$
No, you've shown that each common divisor of $a$, $b$ is a common divisor of $b$, $r$. You have not yet shown that each common divisor of $b$, $r$ is a common divisor of $a$, $b$.
$endgroup$
– Lord Shark the Unknown
Apr 10 at 13:51
$begingroup$
No, you've shown that each common divisor of $a$, $b$ is a common divisor of $b$, $r$. You have not yet shown that each common divisor of $b$, $r$ is a common divisor of $a$, $b$.
$endgroup$
– Lord Shark the Unknown
Apr 10 at 13:51
$begingroup$
So ANY divisor of $a$ and $b$ is also a divisor or $r$?
$endgroup$
– João Pedro
Apr 10 at 14:08
$begingroup$
So ANY divisor of $a$ and $b$ is also a divisor or $r$?
$endgroup$
– João Pedro
Apr 10 at 14:08
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Yes. Let $,rm CD(x,y),$ be the set of Common Divisors of $x,y$. The proof works as follows.
Note $ rm CD(a,b) ,subseteq, rm CD(b,r) $ by paragraph $2$ in the proof,
and $ rm CD(a,b), supseteq, rm CD(b,r) $ by paragraph $3$ in the proof.
Thus $, rm CD(a,b), =, rm CD(b,r) $ so they have the same greatest element (= common divisor)
i.e. $ rm GCD(a,b)! =! rm GCD(b,r)$
Note that the proof requires both containment directions (paragraph $2$ and $3$) to deduce the equality of the common divisor sets (hence equality of their greatest elements).
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
add a comment |
$begingroup$
No. By showing that if $dmid a$ and $dmid b$ then $dmid r$, we are showing that$$textcommon dividers of $a$ and $b$subsettextcommon dividers of $b$ and $r$.$$Now, we must prove that the reverse inclusion also holds.
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
$endgroup$
add a comment |
$begingroup$
Indeed, the proof shows that any common divisor of $a,b$ is a common divisor of $b,r$ and vice versa.
Thus $a,b$ and $b,r$ have the same greatest common divisor, where greatest is taken according to the divisibility relation.
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
$endgroup$
add a comment |
Your Answer
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%2f3182379%2fdoubt-in-proof-of-euclidean-algorithm%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$
Yes. Let $,rm CD(x,y),$ be the set of Common Divisors of $x,y$. The proof works as follows.
Note $ rm CD(a,b) ,subseteq, rm CD(b,r) $ by paragraph $2$ in the proof,
and $ rm CD(a,b), supseteq, rm CD(b,r) $ by paragraph $3$ in the proof.
Thus $, rm CD(a,b), =, rm CD(b,r) $ so they have the same greatest element (= common divisor)
i.e. $ rm GCD(a,b)! =! rm GCD(b,r)$
Note that the proof requires both containment directions (paragraph $2$ and $3$) to deduce the equality of the common divisor sets (hence equality of their greatest elements).
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
add a comment |
$begingroup$
Yes. Let $,rm CD(x,y),$ be the set of Common Divisors of $x,y$. The proof works as follows.
Note $ rm CD(a,b) ,subseteq, rm CD(b,r) $ by paragraph $2$ in the proof,
and $ rm CD(a,b), supseteq, rm CD(b,r) $ by paragraph $3$ in the proof.
Thus $, rm CD(a,b), =, rm CD(b,r) $ so they have the same greatest element (= common divisor)
i.e. $ rm GCD(a,b)! =! rm GCD(b,r)$
Note that the proof requires both containment directions (paragraph $2$ and $3$) to deduce the equality of the common divisor sets (hence equality of their greatest elements).
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
add a comment |
$begingroup$
Yes. Let $,rm CD(x,y),$ be the set of Common Divisors of $x,y$. The proof works as follows.
Note $ rm CD(a,b) ,subseteq, rm CD(b,r) $ by paragraph $2$ in the proof,
and $ rm CD(a,b), supseteq, rm CD(b,r) $ by paragraph $3$ in the proof.
Thus $, rm CD(a,b), =, rm CD(b,r) $ so they have the same greatest element (= common divisor)
i.e. $ rm GCD(a,b)! =! rm GCD(b,r)$
Note that the proof requires both containment directions (paragraph $2$ and $3$) to deduce the equality of the common divisor sets (hence equality of their greatest elements).
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
$endgroup$
Yes. Let $,rm CD(x,y),$ be the set of Common Divisors of $x,y$. The proof works as follows.
Note $ rm CD(a,b) ,subseteq, rm CD(b,r) $ by paragraph $2$ in the proof,
and $ rm CD(a,b), supseteq, rm CD(b,r) $ by paragraph $3$ in the proof.
Thus $, rm CD(a,b), =, rm CD(b,r) $ so they have the same greatest element (= common divisor)
i.e. $ rm GCD(a,b)! =! rm GCD(b,r)$
Note that the proof requires both containment directions (paragraph $2$ and $3$) to deduce the equality of the common divisor sets (hence equality of their greatest elements).
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
edited Apr 10 at 14:31
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
answered Apr 10 at 14:24
Bill DubuqueBill Dubuque
214k29197659
214k29197659
add a comment |
add a comment |
$begingroup$
No. By showing that if $dmid a$ and $dmid b$ then $dmid r$, we are showing that$$textcommon dividers of $a$ and $b$subsettextcommon dividers of $b$ and $r$.$$Now, we must prove that the reverse inclusion also holds.
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
$endgroup$
add a comment |
$begingroup$
No. By showing that if $dmid a$ and $dmid b$ then $dmid r$, we are showing that$$textcommon dividers of $a$ and $b$subsettextcommon dividers of $b$ and $r$.$$Now, we must prove that the reverse inclusion also holds.
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
$endgroup$
add a comment |
$begingroup$
No. By showing that if $dmid a$ and $dmid b$ then $dmid r$, we are showing that$$textcommon dividers of $a$ and $b$subsettextcommon dividers of $b$ and $r$.$$Now, we must prove that the reverse inclusion also holds.
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
$endgroup$
No. By showing that if $dmid a$ and $dmid b$ then $dmid r$, we are showing that$$textcommon dividers of $a$ and $b$subsettextcommon dividers of $b$ and $r$.$$Now, we must prove that the reverse inclusion also holds.
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
answered Apr 10 at 13:49
José Carlos SantosJosé Carlos Santos
175k24134243
175k24134243
add a comment |
add a comment |
$begingroup$
Indeed, the proof shows that any common divisor of $a,b$ is a common divisor of $b,r$ and vice versa.
Thus $a,b$ and $b,r$ have the same greatest common divisor, where greatest is taken according to the divisibility relation.
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
$endgroup$
add a comment |
$begingroup$
Indeed, the proof shows that any common divisor of $a,b$ is a common divisor of $b,r$ and vice versa.
Thus $a,b$ and $b,r$ have the same greatest common divisor, where greatest is taken according to the divisibility relation.
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
$endgroup$
add a comment |
$begingroup$
Indeed, the proof shows that any common divisor of $a,b$ is a common divisor of $b,r$ and vice versa.
Thus $a,b$ and $b,r$ have the same greatest common divisor, where greatest is taken according to the divisibility relation.
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
$endgroup$
Indeed, the proof shows that any common divisor of $a,b$ is a common divisor of $b,r$ and vice versa.
Thus $a,b$ and $b,r$ have the same greatest common divisor, where greatest is taken according to the divisibility relation.
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
answered Apr 10 at 13:54
WuestenfuxWuestenfux
5,5581513
5,5581513
add a comment |
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%2f3182379%2fdoubt-in-proof-of-euclidean-algorithm%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
$begingroup$
No, you've shown that each common divisor of $a$, $b$ is a common divisor of $b$, $r$. You have not yet shown that each common divisor of $b$, $r$ is a common divisor of $a$, $b$.
$endgroup$
– Lord Shark the Unknown
Apr 10 at 13:51
$begingroup$
So ANY divisor of $a$ and $b$ is also a divisor or $r$?
$endgroup$
– João Pedro
Apr 10 at 14:08