Mixing
Can we prove the existence of a gcd in $mathbb Z$ without using division with remainder?
$begingroup$
For $a,binmathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we prove the existence of a gcd of two integers (not both zero) without using
- Division with remainder (that is, without proving that $mathbb Z$ is Euclidean first)
or anything that relies on this, such as
- Euclid's lemma: $pmid abimplies pmid avee pmid b$
- Uniqueness of prime factorisation (which already relies on Euclid's lemma)?
I am aware that "without using ..." is quite vague, so I'll reformulate my question as follows:
Is any proof known of the existence of the gcd which does not rely on the above?
abstract-algebra divisibility integers
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
$endgroup$
add a comment |
$begingroup$
For $a,binmathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we prove the existence of a gcd of two integers (not both zero) without using
- Division with remainder (that is, without proving that $mathbb Z$ is Euclidean first)
or anything that relies on this, such as
- Euclid's lemma: $pmid abimplies pmid avee pmid b$
- Uniqueness of prime factorisation (which already relies on Euclid's lemma)?
I am aware that "without using ..." is quite vague, so I'll reformulate my question as follows:
Is any proof known of the existence of the gcd which does not rely on the above?
abstract-algebra divisibility integers
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
$endgroup$
3
$begingroup$
If Bill D. cannot think of one, I'll believe the answer is no.
$endgroup$
– rabota
Feb 6 '15 at 14:00
$begingroup$
Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $amathbb{Z}+bmathbb{Z}=cmathbb{Z}$ uses division with remainder to show that every subgroup of $mathbb{Z}$ is of the form $nmathbb{Z}$.
$endgroup$
– Hayden
Feb 6 '15 at 14:03
$begingroup$
By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor...
$endgroup$
– Thomas Andrews
Feb 6 '15 at 14:11
add a comment |
$begingroup$
For $a,binmathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we prove the existence of a gcd of two integers (not both zero) without using
- Division with remainder (that is, without proving that $mathbb Z$ is Euclidean first)
or anything that relies on this, such as
- Euclid's lemma: $pmid abimplies pmid avee pmid b$
- Uniqueness of prime factorisation (which already relies on Euclid's lemma)?
I am aware that "without using ..." is quite vague, so I'll reformulate my question as follows:
Is any proof known of the existence of the gcd which does not rely on the above?
abstract-algebra divisibility integers
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
$endgroup$
For $a,binmathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we prove the existence of a gcd of two integers (not both zero) without using
- Division with remainder (that is, without proving that $mathbb Z$ is Euclidean first)
or anything that relies on this, such as
- Euclid's lemma: $pmid abimplies pmid avee pmid b$
- Uniqueness of prime factorisation (which already relies on Euclid's lemma)?
I am aware that "without using ..." is quite vague, so I'll reformulate my question as follows:
Is any proof known of the existence of the gcd which does not rely on the above?
abstract-algebra divisibility integers
abstract-algebra divisibility integers
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
edited Feb 6 '15 at 16:10
rabota
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
asked Feb 6 '15 at 14:00
rabotarabota
14.3k32782
14.3k32782
3
$begingroup$
If Bill D. cannot think of one, I'll believe the answer is no.
$endgroup$
– rabota
Feb 6 '15 at 14:00
$begingroup$
Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $amathbb{Z}+bmathbb{Z}=cmathbb{Z}$ uses division with remainder to show that every subgroup of $mathbb{Z}$ is of the form $nmathbb{Z}$.
$endgroup$
– Hayden
Feb 6 '15 at 14:03
$begingroup$
By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor...
$endgroup$
– Thomas Andrews
Feb 6 '15 at 14:11
add a comment |
3
$begingroup$
If Bill D. cannot think of one, I'll believe the answer is no.
$endgroup$
– rabota
Feb 6 '15 at 14:00
$begingroup$
Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $amathbb{Z}+bmathbb{Z}=cmathbb{Z}$ uses division with remainder to show that every subgroup of $mathbb{Z}$ is of the form $nmathbb{Z}$.
$endgroup$
– Hayden
Feb 6 '15 at 14:03
$begingroup$
By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor...
$endgroup$
– Thomas Andrews
Feb 6 '15 at 14:11
3
3
$begingroup$
If Bill D. cannot think of one, I'll believe the answer is no.
$endgroup$
– rabota
Feb 6 '15 at 14:00
$begingroup$
If Bill D. cannot think of one, I'll believe the answer is no.
$endgroup$
– rabota
Feb 6 '15 at 14:00
$begingroup$
Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $amathbb{Z}+bmathbb{Z}=cmathbb{Z}$ uses division with remainder to show that every subgroup of $mathbb{Z}$ is of the form $nmathbb{Z}$.
$endgroup$
– Hayden
Feb 6 '15 at 14:03
$begingroup$
Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $amathbb{Z}+bmathbb{Z}=cmathbb{Z}$ uses division with remainder to show that every subgroup of $mathbb{Z}$ is of the form $nmathbb{Z}$.
$endgroup$
– Hayden
Feb 6 '15 at 14:03
$begingroup$
By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor...
$endgroup$
– Thomas Andrews
Feb 6 '15 at 14:11
$begingroup$
By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor...
$endgroup$
– Thomas Andrews
Feb 6 '15 at 14:11
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.
The set $rm:S:$ of all integers of the form $rm:a:x + b:y,, x,yin mathbb Z,:$ is closed under subtraction so, by the Lemma below, every positive $rm:nin S:$ is divisible by $rm:d = $ least positive $rmin S,:$ so $rm:a,bin S:$ $Rightarrow$ $rm:d:|:a,b.:$ So $rm:d:$ is a common divisor of $rm:a,b,:$ necessarily greatest: $rm:c:|:a,b:$ $Rightarrow$ $rm:c:|:d = a,x_1!+! b,y_1,$ ($Rightarrow$ $rm:cle d).$
Lemma $ $ Let $,rm Sneemptyset ,$ be a set of integers $>0$ closed under subtraction $> 0,,$ i.e. for all $rm,n,min S, ,$ $rm n > m Rightarrow n-m, in, S.,$ Then every element of $rm,S,$ is a multiple of the least element $rm:ell = min, S.$
Proof $ $ If not there is a least nonmultiple $rm,nin S,,$ contra $rm,n-ell in S,$ is a nonmultiple of $rm,ell.$
Remark $ $ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).
However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)
edited Apr 13 '17 at 12:21
Community♦
1
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
1
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
add a comment |
$begingroup$
Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:
Euclidean domain $implies$ principal ideal domain $implies$ unique factorization domain,
and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
$endgroup$
2
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
add a comment |
$begingroup$
For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
$endgroup$
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
3
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
add a comment |
$begingroup$
I have a unique method to prove the existence of gcd
Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.
So let's start.... Consider "a", "b" such that "a", "b"$in$ $Z^+$
We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)
Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.
Applying euclidean algorithm to "a","b"....
a=bq1+r1, 0< r1 < b
b=r1q2+r2, 0< r2 < r1
r1=r2q3+r3, 0< r3 < r2
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers
So we got a infinite sequence of strictly decreasing positive integers ...
But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.
So we are left with a contradiction!!
Hence Euclidean Algorithm terminates.
Since Euclidean Algorithm provides gcd
So gcd also exists!!!!
Hope it helps 😋
answered Jan 27 at 5:48
user629660user629660
123
$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%2f1136470%2fcan-we-prove-the-existence-of-a-gcd-in-mathbb-z-without-using-division-with-r%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.
The set $rm:S:$ of all integers of the form $rm:a:x + b:y,, x,yin mathbb Z,:$ is closed under subtraction so, by the Lemma below, every positive $rm:nin S:$ is divisible by $rm:d = $ least positive $rmin S,:$ so $rm:a,bin S:$ $Rightarrow$ $rm:d:|:a,b.:$ So $rm:d:$ is a common divisor of $rm:a,b,:$ necessarily greatest: $rm:c:|:a,b:$ $Rightarrow$ $rm:c:|:d = a,x_1!+! b,y_1,$ ($Rightarrow$ $rm:cle d).$
Lemma $ $ Let $,rm Sneemptyset ,$ be a set of integers $>0$ closed under subtraction $> 0,,$ i.e. for all $rm,n,min S, ,$ $rm n > m Rightarrow n-m, in, S.,$ Then every element of $rm,S,$ is a multiple of the least element $rm:ell = min, S.$
Proof $ $ If not there is a least nonmultiple $rm,nin S,,$ contra $rm,n-ell in S,$ is a nonmultiple of $rm,ell.$
Remark $ $ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).
However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)
edited Apr 13 '17 at 12:21
Community♦
1
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
1
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
add a comment |
$begingroup$
One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.
The set $rm:S:$ of all integers of the form $rm:a:x + b:y,, x,yin mathbb Z,:$ is closed under subtraction so, by the Lemma below, every positive $rm:nin S:$ is divisible by $rm:d = $ least positive $rmin S,:$ so $rm:a,bin S:$ $Rightarrow$ $rm:d:|:a,b.:$ So $rm:d:$ is a common divisor of $rm:a,b,:$ necessarily greatest: $rm:c:|:a,b:$ $Rightarrow$ $rm:c:|:d = a,x_1!+! b,y_1,$ ($Rightarrow$ $rm:cle d).$
Lemma $ $ Let $,rm Sneemptyset ,$ be a set of integers $>0$ closed under subtraction $> 0,,$ i.e. for all $rm,n,min S, ,$ $rm n > m Rightarrow n-m, in, S.,$ Then every element of $rm,S,$ is a multiple of the least element $rm:ell = min, S.$
Proof $ $ If not there is a least nonmultiple $rm,nin S,,$ contra $rm,n-ell in S,$ is a nonmultiple of $rm,ell.$
Remark $ $ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).
However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)
edited Apr 13 '17 at 12:21
Community♦
1
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
1
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
add a comment |
$begingroup$
One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.
The set $rm:S:$ of all integers of the form $rm:a:x + b:y,, x,yin mathbb Z,:$ is closed under subtraction so, by the Lemma below, every positive $rm:nin S:$ is divisible by $rm:d = $ least positive $rmin S,:$ so $rm:a,bin S:$ $Rightarrow$ $rm:d:|:a,b.:$ So $rm:d:$ is a common divisor of $rm:a,b,:$ necessarily greatest: $rm:c:|:a,b:$ $Rightarrow$ $rm:c:|:d = a,x_1!+! b,y_1,$ ($Rightarrow$ $rm:cle d).$
Lemma $ $ Let $,rm Sneemptyset ,$ be a set of integers $>0$ closed under subtraction $> 0,,$ i.e. for all $rm,n,min S, ,$ $rm n > m Rightarrow n-m, in, S.,$ Then every element of $rm,S,$ is a multiple of the least element $rm:ell = min, S.$
Proof $ $ If not there is a least nonmultiple $rm,nin S,,$ contra $rm,n-ell in S,$ is a nonmultiple of $rm,ell.$
Remark $ $ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).
However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)
edited Apr 13 '17 at 12:21
Community♦
1
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
One can eliminate explicit use of the division algorithm by replacing its use by its inductive essence (i.e. rewriting the proof in mathematical "assembly language"). Below is one simple way.
The set $rm:S:$ of all integers of the form $rm:a:x + b:y,, x,yin mathbb Z,:$ is closed under subtraction so, by the Lemma below, every positive $rm:nin S:$ is divisible by $rm:d = $ least positive $rmin S,:$ so $rm:a,bin S:$ $Rightarrow$ $rm:d:|:a,b.:$ So $rm:d:$ is a common divisor of $rm:a,b,:$ necessarily greatest: $rm:c:|:a,b:$ $Rightarrow$ $rm:c:|:d = a,x_1!+! b,y_1,$ ($Rightarrow$ $rm:cle d).$
Lemma $ $ Let $,rm Sneemptyset ,$ be a set of integers $>0$ closed under subtraction $> 0,,$ i.e. for all $rm,n,min S, ,$ $rm n > m Rightarrow n-m, in, S.,$ Then every element of $rm,S,$ is a multiple of the least element $rm:ell = min, S.$
Proof $ $ If not there is a least nonmultiple $rm,nin S,,$ contra $rm,n-ell in S,$ is a nonmultiple of $rm,ell.$
Remark $ $ Using the same idea one can give "elementary" proofs of other theorems of number theory, e.g. the proof of FTA = Fundamental Theorem of Arithmetic due to Zermelo (and others).
However, this is exactly the opposite of what one desires from a pedagogical standpoint. The innate ideal theoretic structure that underlies many of these results should be highlighted - not eliminated (for example, see posts on denominator ideals and order ideals)
edited Apr 13 '17 at 12:21
Community♦
1
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
1
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
answered Feb 6 '15 at 15:07
Bill DubuqueBill Dubuque
213k29195654
213k29195654
1
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
add a comment |
1
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
1
1
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
$begingroup$
As i said: One can cheat. And I definitely agree with your last paragraph.
$endgroup$
– MooS
Feb 6 '15 at 16:36
add a comment |
$begingroup$
Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:
Euclidean domain $implies$ principal ideal domain $implies$ unique factorization domain,
and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
$endgroup$
2
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
add a comment |
$begingroup$
Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:
Euclidean domain $implies$ principal ideal domain $implies$ unique factorization domain,
and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
$endgroup$
2
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
add a comment |
$begingroup$
Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:
Euclidean domain $implies$ principal ideal domain $implies$ unique factorization domain,
and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
$endgroup$
Building on previous comments and on MooS' answer, it seems that you definitely need unique factorization to prove the existence of the gcd. But most importanly, I think that one piece of information deserves to be highlighted, namely:
Euclidean domain $implies$ principal ideal domain $implies$ unique factorization domain,
and these arrows can't be reversed (i.e., there are rings falsifying each converse). That means, that unique factorization (UF) is strictly weaker than having division with remainder, and thus it could be said that an argument using UF doesn't rely on the algorithm of division. In that sense, the answer to the question stated in the title would be "Yes", but "No" to the one expanded in the text.
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
edited Feb 6 '15 at 15:36
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
answered Feb 6 '15 at 15:10
Pedro Sánchez TerrafPedro Sánchez Terraf
2,6091923
2,6091923
2
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
add a comment |
2
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
2
2
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
I think your arrows are backwards.
$endgroup$
– GPerez
Feb 6 '15 at 15:33
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
$begingroup$
@GPerez, absolutely right, typo. Just edited it
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 15:34
add a comment |
$begingroup$
For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
$endgroup$
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
3
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
add a comment |
$begingroup$
For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
$endgroup$
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
3
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
add a comment |
$begingroup$
For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
$endgroup$
For the greatest common divisor to exist and be well defined, we need a unique factorization domain. So if you do not allow the use of unique prime factorization, it is probably not possible. Of course we could come up with a proof, which implicitly shows unique prime factorization on its way, but this would be cheating.
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
answered Feb 6 '15 at 14:08
MooSMooS
27.1k11334
27.1k11334
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
3
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
add a comment |
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
3
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
$begingroup$
I think the existence of gcd as stated implies that you have a principal ideal domain, which in turns implies UFD, isn't it? So without UFD you couldn't do it.
$endgroup$
– Pedro Sánchez Terraf
Feb 6 '15 at 14:11
3
3
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
Principal ideal domain indeed implies UFD. But we do not need a PID to have a gcd. If you have 2 elements in an UFD, just look at their prime factorizations and for each prime occuring take minimum of the exponents to build the gcd. But one should point out: We need a PID if we want Bezout's Lemma to hold.
$endgroup$
– MooS
Feb 6 '15 at 14:17
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
$begingroup$
The first sentence is false. For example, the ring of all algebraic integers is Bezout so a GCD domain, but it is not a UFD since it has no irreducibles, since $, alpha = sqrtalpha sqrtalpha.,$
$endgroup$
– Bill Dubuque
Feb 6 '15 at 20:32
add a comment |
$begingroup$
I have a unique method to prove the existence of gcd
Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.
So let's start.... Consider "a", "b" such that "a", "b"$in$ $Z^+$
We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)
Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.
Applying euclidean algorithm to "a","b"....
a=bq1+r1, 0< r1 < b
b=r1q2+r2, 0< r2 < r1
r1=r2q3+r3, 0< r3 < r2
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers
So we got a infinite sequence of strictly decreasing positive integers ...
But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.
So we are left with a contradiction!!
Hence Euclidean Algorithm terminates.
Since Euclidean Algorithm provides gcd
So gcd also exists!!!!
Hope it helps 😋
answered Jan 27 at 5:48
user629660user629660
123
$endgroup$
add a comment |
$begingroup$
I have a unique method to prove the existence of gcd
Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.
So let's start.... Consider "a", "b" such that "a", "b"$in$ $Z^+$
We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)
Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.
Applying euclidean algorithm to "a","b"....
a=bq1+r1, 0< r1 < b
b=r1q2+r2, 0< r2 < r1
r1=r2q3+r3, 0< r3 < r2
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers
So we got a infinite sequence of strictly decreasing positive integers ...
But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.
So we are left with a contradiction!!
Hence Euclidean Algorithm terminates.
Since Euclidean Algorithm provides gcd
So gcd also exists!!!!
Hope it helps 😋
answered Jan 27 at 5:48
user629660user629660
123
$endgroup$
add a comment |
$begingroup$
I have a unique method to prove the existence of gcd
Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.
So let's start.... Consider "a", "b" such that "a", "b"$in$ $Z^+$
We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)
Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.
Applying euclidean algorithm to "a","b"....
a=bq1+r1, 0< r1 < b
b=r1q2+r2, 0< r2 < r1
r1=r2q3+r3, 0< r3 < r2
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers
So we got a infinite sequence of strictly decreasing positive integers ...
But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.
So we are left with a contradiction!!
Hence Euclidean Algorithm terminates.
Since Euclidean Algorithm provides gcd
So gcd also exists!!!!
Hope it helps 😋
answered Jan 27 at 5:48
user629660user629660
123
$endgroup$
I have a unique method to prove the existence of gcd
Since Euclidean Algorithm provides gcd,so proving that Euclidean Algorithm terminates might help us to prove that gcd exists.
So let's start.... Consider "a", "b" such that "a", "b"$in$ $Z^+$
We know that Euclidean Algorithm ends when remainder becomes "0" ---(1)
Let us assume that Euclidean Algorithm never ends, So according to statement (1) none of remainder should be zero.
Applying euclidean algorithm to "a","b"....
a=bq1+r1, 0< r1 < b
b=r1q2+r2, 0< r2 < r1
r1=r2q3+r3, 0< r3 < r2
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
So continuing the process will give us b>r1>r2>r3>r4>r5>r6..... ∞ .Since b,r1,r2,r3,r4,r5...∞ are positive integers
So we got a infinite sequence of strictly decreasing positive integers ...
But according to statement of infinite descent which is a consequence of well ordering Principle, no such sequence exists.
So we are left with a contradiction!!
Hence Euclidean Algorithm terminates.
Since Euclidean Algorithm provides gcd
So gcd also exists!!!!
Hope it helps 😋
answered Jan 27 at 5:48
user629660user629660
123
edited Jan 28 at 14:33
answered Jan 27 at 5:48
user629660user629660
123
answered Jan 27 at 5:48
user629660user629660
123
answered Jan 27 at 5:48
user629660user629660
123
123
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%2f1136470%2fcan-we-prove-the-existence-of-a-gcd-in-mathbb-z-without-using-division-with-r%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
3
$begingroup$
If Bill D. cannot think of one, I'll believe the answer is no.
$endgroup$
– rabota
Feb 6 '15 at 14:00
$begingroup$
Not an answer, but rather an observation of a route that doesn't work: Even the approach of defining the gcd of $a,b$ integers as the unique positive integer $c$ such that $amathbb{Z}+bmathbb{Z}=cmathbb{Z}$ uses division with remainder to show that every subgroup of $mathbb{Z}$ is of the form $nmathbb{Z}$.
$endgroup$
– Hayden
Feb 6 '15 at 14:03
$begingroup$
By the way, that is not the definition of "a greatest common divisor." You didn't state that $d$ has to be a common divisor...
$endgroup$
– Thomas Andrews
Feb 6 '15 at 14:11