It deserves to be much better known that nonexistant GCDs (and, similarly, nonprincipal ideals) arise immediately 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 any domain D.
LEMMA: (a,b) = (ac,bc)/c if (ac,bc) exists
Proof: d|a,b <=> dc|ac,bc <=> dc|(ac,bc) <=> d|(ac,bc)/c. QED
EUCLID'S LEMMA: a|bc and (a,b)=1 => a|c, if (ac,bc) exists
Proof: a|ac,bc => a|(ac,bc) = (a,b)c = c via Lemma. QED
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.
E.g. David Speyer's example above, and Khurana's example in [1] (= Theorem 41 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.
[0] Clark, Pete. L. Factorization in integral domains. 29pp. 2010. http://alpha.math.uga.edu/~pete/factorization2010.pdf
[1] D. Khurana, On GCD and LCM in domains: A Conjecture of Gauss. Resonance 8 (2003), 72-79. https://www.ias.ac.in/article/fulltext/reso/008/06/0072-0079
[2] sci.math.research, 3/12/09, seeking comments on expository article on factorization
http://groups.google.com/group/sci.math.research/msg/88343de90a4cf6b7
http://google.com/groups?selm=gparte%24si4%241%40dizzy.math.ohio-state.edu
