Mixing
Extention of Euclid's GCD Algorithm. (The Art of Computer Programming, Volume 1, Edition 3, Section 1.2.1,...
$begingroup$
Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$,
needs the inputs to be positive integers.
Exercise 12 provides an extension to this algorithm and allows $c$ & $d$ to accept
values of the form $u+vsqrt{2}$, where $u$ and $v$ are integers.
In this case we can find a $r$ (of the form $u+vsqrt{2}$) such that
$c=dq+r$ , $q$ is a positive integer.
The algorithm can then continue as usual with $c$<-$d$ and $d$<-$r$ in the next step.
The algorithm will however not terminate if $c=1$ and $d=sqrt{2}$ because there
is no common divisor($q$) here.
However, the algorithm can be made to terminate in this case also if some extension
is done to the divisor $q$, as explained here (by the author):
If we extend the concept of divisor so that $u+vsqrt{2}$ is said to divide $a(u+vsqrt{2})$
if and only if $a$ has the form $u'+v'sqrt{2}$ for integers $u'$ and $v'$, there
is a way to extend the algorithm so that it always will terminate. If we have
$c=u+vsqrt{2}$ and $d=u'+v'sqrt{2}$, compute $c/d=c(u'-v'sqrt{2})/(u'^2-2v'^2)=x+ysqrt{2}$
where x and y are rational. Now let $q=u''+v''sqrt{2}$ where $u''$ and $v''$ are the
nearest integers to $x$ and $y$; and let $r=c-qd$. If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
I did not understand the last line that
If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
Please explain how $|u'''^2-2v'''^2|<|u'^2-2v'^2|$
and how this proves that
computation will terminate.
elementary-number-theory proof-explanation arithmetic divisibility irrational-numbers
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
asked Dec 19 '14 at 15:09
atif93atif93
1434
$endgroup$
add a comment |
$begingroup$
Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$,
needs the inputs to be positive integers.
Exercise 12 provides an extension to this algorithm and allows $c$ & $d$ to accept
values of the form $u+vsqrt{2}$, where $u$ and $v$ are integers.
In this case we can find a $r$ (of the form $u+vsqrt{2}$) such that
$c=dq+r$ , $q$ is a positive integer.
The algorithm can then continue as usual with $c$<-$d$ and $d$<-$r$ in the next step.
The algorithm will however not terminate if $c=1$ and $d=sqrt{2}$ because there
is no common divisor($q$) here.
However, the algorithm can be made to terminate in this case also if some extension
is done to the divisor $q$, as explained here (by the author):
If we extend the concept of divisor so that $u+vsqrt{2}$ is said to divide $a(u+vsqrt{2})$
if and only if $a$ has the form $u'+v'sqrt{2}$ for integers $u'$ and $v'$, there
is a way to extend the algorithm so that it always will terminate. If we have
$c=u+vsqrt{2}$ and $d=u'+v'sqrt{2}$, compute $c/d=c(u'-v'sqrt{2})/(u'^2-2v'^2)=x+ysqrt{2}$
where x and y are rational. Now let $q=u''+v''sqrt{2}$ where $u''$ and $v''$ are the
nearest integers to $x$ and $y$; and let $r=c-qd$. If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
I did not understand the last line that
If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
Please explain how $|u'''^2-2v'''^2|<|u'^2-2v'^2|$
and how this proves that
computation will terminate.
elementary-number-theory proof-explanation arithmetic divisibility irrational-numbers
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
asked Dec 19 '14 at 15:09
atif93atif93
1434
$endgroup$
2
$begingroup$
To learn more about euclidean quadratic number fields I recommend having on hand at least one number theory textbook. This is discussed in many classical textbooks, e.g. those by Hardy & Wright, Harvey Cohn, and Harold Stark, to name just a few of many elementary expositions.
$endgroup$
– Bill Dubuque
Dec 19 '14 at 16:58
add a comment |
$begingroup$
Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$,
needs the inputs to be positive integers.
Exercise 12 provides an extension to this algorithm and allows $c$ & $d$ to accept
values of the form $u+vsqrt{2}$, where $u$ and $v$ are integers.
In this case we can find a $r$ (of the form $u+vsqrt{2}$) such that
$c=dq+r$ , $q$ is a positive integer.
The algorithm can then continue as usual with $c$<-$d$ and $d$<-$r$ in the next step.
The algorithm will however not terminate if $c=1$ and $d=sqrt{2}$ because there
is no common divisor($q$) here.
However, the algorithm can be made to terminate in this case also if some extension
is done to the divisor $q$, as explained here (by the author):
If we extend the concept of divisor so that $u+vsqrt{2}$ is said to divide $a(u+vsqrt{2})$
if and only if $a$ has the form $u'+v'sqrt{2}$ for integers $u'$ and $v'$, there
is a way to extend the algorithm so that it always will terminate. If we have
$c=u+vsqrt{2}$ and $d=u'+v'sqrt{2}$, compute $c/d=c(u'-v'sqrt{2})/(u'^2-2v'^2)=x+ysqrt{2}$
where x and y are rational. Now let $q=u''+v''sqrt{2}$ where $u''$ and $v''$ are the
nearest integers to $x$ and $y$; and let $r=c-qd$. If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
I did not understand the last line that
If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
Please explain how $|u'''^2-2v'''^2|<|u'^2-2v'^2|$
and how this proves that
computation will terminate.
elementary-number-theory proof-explanation arithmetic divisibility irrational-numbers
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
asked Dec 19 '14 at 15:09
atif93atif93
1434
$endgroup$
Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$,
needs the inputs to be positive integers.
Exercise 12 provides an extension to this algorithm and allows $c$ & $d$ to accept
values of the form $u+vsqrt{2}$, where $u$ and $v$ are integers.
In this case we can find a $r$ (of the form $u+vsqrt{2}$) such that
$c=dq+r$ , $q$ is a positive integer.
The algorithm can then continue as usual with $c$<-$d$ and $d$<-$r$ in the next step.
The algorithm will however not terminate if $c=1$ and $d=sqrt{2}$ because there
is no common divisor($q$) here.
However, the algorithm can be made to terminate in this case also if some extension
is done to the divisor $q$, as explained here (by the author):
If we extend the concept of divisor so that $u+vsqrt{2}$ is said to divide $a(u+vsqrt{2})$
if and only if $a$ has the form $u'+v'sqrt{2}$ for integers $u'$ and $v'$, there
is a way to extend the algorithm so that it always will terminate. If we have
$c=u+vsqrt{2}$ and $d=u'+v'sqrt{2}$, compute $c/d=c(u'-v'sqrt{2})/(u'^2-2v'^2)=x+ysqrt{2}$
where x and y are rational. Now let $q=u''+v''sqrt{2}$ where $u''$ and $v''$ are the
nearest integers to $x$ and $y$; and let $r=c-qd$. If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
I did not understand the last line that
If $r=u'''+v'''sqrt{2}$, it follows
that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$, hence the computation will terminate.
Please explain how $|u'''^2-2v'''^2|<|u'^2-2v'^2|$
and how this proves that
computation will terminate.
elementary-number-theory proof-explanation arithmetic divisibility irrational-numbers
elementary-number-theory proof-explanation arithmetic divisibility irrational-numbers
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
asked Dec 19 '14 at 15:09
atif93atif93
1434
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
asked Dec 19 '14 at 15:09
atif93atif93
1434
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
edited Jan 5 at 8:54
Alex Ravsky
39.9k32282
39.9k32282
asked Dec 19 '14 at 15:09
atif93atif93
1434
asked Dec 19 '14 at 15:09
atif93atif93
1434
asked Dec 19 '14 at 15:09
atif93atif93
1434
1434
2
$begingroup$
To learn more about euclidean quadratic number fields I recommend having on hand at least one number theory textbook. This is discussed in many classical textbooks, e.g. those by Hardy & Wright, Harvey Cohn, and Harold Stark, to name just a few of many elementary expositions.
$endgroup$
– Bill Dubuque
Dec 19 '14 at 16:58
add a comment |
2
$begingroup$
To learn more about euclidean quadratic number fields I recommend having on hand at least one number theory textbook. This is discussed in many classical textbooks, e.g. those by Hardy & Wright, Harvey Cohn, and Harold Stark, to name just a few of many elementary expositions.
$endgroup$
– Bill Dubuque
Dec 19 '14 at 16:58
2
2
$begingroup$
To learn more about euclidean quadratic number fields I recommend having on hand at least one number theory textbook. This is discussed in many classical textbooks, e.g. those by Hardy & Wright, Harvey Cohn, and Harold Stark, to name just a few of many elementary expositions.
$endgroup$
– Bill Dubuque
Dec 19 '14 at 16:58
$begingroup$
To learn more about euclidean quadratic number fields I recommend having on hand at least one number theory textbook. This is discussed in many classical textbooks, e.g. those by Hardy & Wright, Harvey Cohn, and Harold Stark, to name just a few of many elementary expositions.
$endgroup$
– Bill Dubuque
Dec 19 '14 at 16:58
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The computation should terminate because of the same reason as the usual Euclidean algorithm, in which we search the greatest common divisor of natural numbers $c$ and $d$ with $c>d$. Namely, we have $c=qd+r$ with $r<d$. If $r>0$ then we have $d=q’r+r’$ with $r’<r$ and so forth. Following this way we consecutively construct a sequence $b>r>r’>r’’>dots$ of non-negative integer residues, which have to be finite and stop at the zero. In the question to this sequence corresponds a sequence $|b|>|r|>|r’|>dots$, where $|u+sqrt{2}|=|u^2-2v^2|$. When the sequence stops at $|r_k|=|u_k+sqrt{2}v_k|$ we have $|u_k^2-2v_k^2|=0$. Since $sqrt{2}$ is irrational, the equality can hold only if $u_k=v_k=0$.
Algebraically, the proposed algorithm extension is a part of a proof that a ring consisting of numbers of the form $u+sqrt{2}v$ is a Euclidean domain, endowed with a Euclidean function $|u^2-2v^2|$. In particular, that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$ is proved in this answer.
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
$endgroup$
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%2f1074620%2fextention-of-euclids-gcd-algorithm-the-art-of-computer-programming-volume-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The computation should terminate because of the same reason as the usual Euclidean algorithm, in which we search the greatest common divisor of natural numbers $c$ and $d$ with $c>d$. Namely, we have $c=qd+r$ with $r<d$. If $r>0$ then we have $d=q’r+r’$ with $r’<r$ and so forth. Following this way we consecutively construct a sequence $b>r>r’>r’’>dots$ of non-negative integer residues, which have to be finite and stop at the zero. In the question to this sequence corresponds a sequence $|b|>|r|>|r’|>dots$, where $|u+sqrt{2}|=|u^2-2v^2|$. When the sequence stops at $|r_k|=|u_k+sqrt{2}v_k|$ we have $|u_k^2-2v_k^2|=0$. Since $sqrt{2}$ is irrational, the equality can hold only if $u_k=v_k=0$.
Algebraically, the proposed algorithm extension is a part of a proof that a ring consisting of numbers of the form $u+sqrt{2}v$ is a Euclidean domain, endowed with a Euclidean function $|u^2-2v^2|$. In particular, that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$ is proved in this answer.
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
$endgroup$
add a comment |
$begingroup$
The computation should terminate because of the same reason as the usual Euclidean algorithm, in which we search the greatest common divisor of natural numbers $c$ and $d$ with $c>d$. Namely, we have $c=qd+r$ with $r<d$. If $r>0$ then we have $d=q’r+r’$ with $r’<r$ and so forth. Following this way we consecutively construct a sequence $b>r>r’>r’’>dots$ of non-negative integer residues, which have to be finite and stop at the zero. In the question to this sequence corresponds a sequence $|b|>|r|>|r’|>dots$, where $|u+sqrt{2}|=|u^2-2v^2|$. When the sequence stops at $|r_k|=|u_k+sqrt{2}v_k|$ we have $|u_k^2-2v_k^2|=0$. Since $sqrt{2}$ is irrational, the equality can hold only if $u_k=v_k=0$.
Algebraically, the proposed algorithm extension is a part of a proof that a ring consisting of numbers of the form $u+sqrt{2}v$ is a Euclidean domain, endowed with a Euclidean function $|u^2-2v^2|$. In particular, that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$ is proved in this answer.
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
$endgroup$
add a comment |
$begingroup$
The computation should terminate because of the same reason as the usual Euclidean algorithm, in which we search the greatest common divisor of natural numbers $c$ and $d$ with $c>d$. Namely, we have $c=qd+r$ with $r<d$. If $r>0$ then we have $d=q’r+r’$ with $r’<r$ and so forth. Following this way we consecutively construct a sequence $b>r>r’>r’’>dots$ of non-negative integer residues, which have to be finite and stop at the zero. In the question to this sequence corresponds a sequence $|b|>|r|>|r’|>dots$, where $|u+sqrt{2}|=|u^2-2v^2|$. When the sequence stops at $|r_k|=|u_k+sqrt{2}v_k|$ we have $|u_k^2-2v_k^2|=0$. Since $sqrt{2}$ is irrational, the equality can hold only if $u_k=v_k=0$.
Algebraically, the proposed algorithm extension is a part of a proof that a ring consisting of numbers of the form $u+sqrt{2}v$ is a Euclidean domain, endowed with a Euclidean function $|u^2-2v^2|$. In particular, that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$ is proved in this answer.
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
$endgroup$
The computation should terminate because of the same reason as the usual Euclidean algorithm, in which we search the greatest common divisor of natural numbers $c$ and $d$ with $c>d$. Namely, we have $c=qd+r$ with $r<d$. If $r>0$ then we have $d=q’r+r’$ with $r’<r$ and so forth. Following this way we consecutively construct a sequence $b>r>r’>r’’>dots$ of non-negative integer residues, which have to be finite and stop at the zero. In the question to this sequence corresponds a sequence $|b|>|r|>|r’|>dots$, where $|u+sqrt{2}|=|u^2-2v^2|$. When the sequence stops at $|r_k|=|u_k+sqrt{2}v_k|$ we have $|u_k^2-2v_k^2|=0$. Since $sqrt{2}$ is irrational, the equality can hold only if $u_k=v_k=0$.
Algebraically, the proposed algorithm extension is a part of a proof that a ring consisting of numbers of the form $u+sqrt{2}v$ is a Euclidean domain, endowed with a Euclidean function $|u^2-2v^2|$. In particular, that $|u'''^2-2v'''^2|<|u'^2-2v'^2|$ is proved in this answer.
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
answered Jan 5 at 8:53
Alex RavskyAlex Ravsky
39.9k32282
39.9k32282
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%2f1074620%2fextention-of-euclids-gcd-algorithm-the-art-of-computer-programming-volume-1%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
2
$begingroup$
To learn more about euclidean quadratic number fields I recommend having on hand at least one number theory textbook. This is discussed in many classical textbooks, e.g. those by Hardy & Wright, Harvey Cohn, and Harold Stark, to name just a few of many elementary expositions.
$endgroup$
– Bill Dubuque
Dec 19 '14 at 16:58