An example of two elements without a greatest common divisor - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:10:30Z http://mathoverflow.net/feeds/question/11105 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11105/an-example-of-two-elements-without-a-greatest-common-divisor An example of two elements without a greatest common divisor Alfonso Gracia-Saz 2010-01-08T05:17:19Z 2010-07-12T16:41:46Z <p>Is there an easy example of an integral domain and two elements on it which do not have a greatest common divisor? It will have to be a non-UFD, obviously.</p> <p>"Easy" means that I can explain it to my undergrad students, although I will be happy with any example.</p> http://mathoverflow.net/questions/11105/an-example-of-two-elements-without-a-greatest-common-divisor/11107#11107 Answer by Charles Siegel for An example of two elements without a greatest common divisor Charles Siegel 2010-01-08T05:23:56Z 2010-01-08T05:23:56Z <p><a href="http://en.wikipedia.org/wiki/Greatest%5Fcommon%5Fdivisor" rel="nofollow">Here's</a> an example stolen blatantly from wikipedia.</p> <p>Let $R=\mathbb{Z}[\sqrt{-3}]$, let $a=4=2*2=(1+\sqrt{-3})(1-\sqrt{-3})$ and $b=2(1+\sqrt{-3})$. Now, $2$ and $1+\sqrt{-3}$ are both maximal among divisors, but are not associates, thus, there is not GCD.</p> http://mathoverflow.net/questions/11105/an-example-of-two-elements-without-a-greatest-common-divisor/11108#11108 Answer by Ben Linowitz for An example of two elements without a greatest common divisor Ben Linowitz 2010-01-08T05:28:51Z 2010-01-08T05:28:51Z <p>Since Charles has already given you an example, I'll just mention that there is a name for integral domains in which any two non-zero elements have a gcd: <a href="http://en.wikipedia.org/wiki/GCD_domain" rel="nofollow">GCD-Domains</a>.</p> <p>See also Pete's response to <a href="http://mathoverflow.net/questions/6651/counter-example-for-gausss-lemma-on-irreducible-polynomials" rel="nofollow">“Counter”-example for Gauss’s Lemma on irreducible polynomials</a>.</p> http://mathoverflow.net/questions/11105/an-example-of-two-elements-without-a-greatest-common-divisor/11173#11173 Answer by S. Carnahan for An example of two elements without a greatest common divisor S. Carnahan 2010-01-08T19:23:48Z 2010-01-08T19:54:36Z <p>Another possible answer, following Qiaochu's comment: The elements <strike>$x^2$ and $x^3$</strike> (<b>Edit:</b> $x^5$ and $x^6$) in $k[x^2, x^3]$ (alternatively, $k[x,y]/(x^3-y^2)$), where $k$ is a nonzero ring.</p> http://mathoverflow.net/questions/11105/an-example-of-two-elements-without-a-greatest-common-divisor/11176#11176 Answer by David Speyer for An example of two elements without a greatest common divisor David Speyer 2010-01-08T20:02:50Z 2010-01-08T20:02:50Z <p>I should point out, there are plenty of examples in integrally closed rings. For example:</p> <p>In $k[a,b,c,d]/(ad-bc)$, there is no GCD of $ad$ and $ab$. (Note that $a$ and $b$ are both common divisors.)</p> <p>In $\mathbb{Z}[\sqrt{-5}]$, there is no GCD of $6$ and $2 (1+\sqrt{-5})$. (Note that $2$ and $1+\sqrt{-5}$ are both common divisors.)</p> http://mathoverflow.net/questions/11105/an-example-of-two-elements-without-a-greatest-common-divisor/31490#31490 Answer by Bill Dubuque for An example of two elements without a greatest common divisor Bill Dubuque 2010-07-12T01:33:42Z 2010-07-12T16:41:46Z <p>It deserves to be much better known that <strong>nonexistant GCDs</strong> (and, similarly, <strong>nonprincipal ideals</strong>) arise <em>immediately</em> from any failure of Euclid's Lemma, and this provides an illuminating way to view many of the standard examples. Below is a detailed explanation extracted from one of my sci.math.research posts [2]. The results below hold true in <em>any</em> domain D.</p> <p><strong>LEMMA</strong>: (a,b) = (ac,bc)/c if (ac,bc) exists</p> <p>Proof: d|a,b &lt;=> dc|ac,bc &lt;=> dc|(ac,bc) &lt;=> d|(ac,bc)/c. QED</p> <p><strong>EUCLID'S LEMMA</strong>: a|bc and (a,b)=1 => a|c, if (ac,bc) exists </p> <p>Proof: a|ac,bc => a|(ac,bc) = (a,b)c = c via Lemma. QED </p> <p>Therefore if a,b,c fail to satisfy the implication in Euclid's Lemma, namely if (a,b) = 1 and a|bc, not a|c, then one immediately deduces that the gcd (ac,bc) fails to exist in D.</p> <p>E.g. David Speyer's example above, and Khurana's example in [1] (= Theorem 31 in Pete L. Clark's [0]) are simply specializations where a,b,c = p,1+w,1-w in a quadratic number (sub)ring Z[w], ww = -d. </p> <p>[0] Clark, Pete. L. Factorization in integral domains. 29pp. 2009. <a href="http://math.uga.edu/~pete/factorization.pdf" rel="nofollow">http://math.uga.edu/~pete/factorization.pdf</a></p> <p>[1] D. Khurana, On GCD and LCM in domains: A Conjecture of Gauss. Resonance 8 (2003), 72-79. <a href="http://www.ias.ac.in/resonance/June2003/pdf/June2003Classroom.pdf" rel="nofollow">http://www.ias.ac.in/resonance/June2003/pdf/June2003Classroom.pdf</a> </p> <p>[2] sci.math.research, 3/12/09, seeking comments on expository article on factorization<br> <a href="http://groups.google.com/group/sci.math.research/msg/88343de90a4cf6b7" rel="nofollow">http://groups.google.com/group/sci.math.research/msg/88343de90a4cf6b7</a><br> <a href="http://google.com/groups?selm=gparte%24si4%241%40dizzy.math.ohio-state.edu" rel="nofollow">http://google.com/groups?selm=gparte%24si4%241%40dizzy.math.ohio-state.edu</a> </p>