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 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.

[0] Clark, Pete. L. Factorization in integral domains. 29pp. 2009.
http://math.uga.edu/~pete/factorization.pdf

[1] D. Khurana, On GCD and LCM in domains: A Conjecture of Gauss.
Resonance 8 (2003), 72-79.
http://www.ias.ac.in/resonance/June2003/pdf/June2003Classroom.pdf

[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