GCD is really an operation on the lattice of ideals, and the Euclidean algorithm is merely a calculational device that is sometimes helpful. Rings such as Z[i], Z[(1+√-3)/2], Z[√2], and the other quadratic PIDs may be easy to handle. But in the general case, the GCD is nonprincipal, and there are things like Z[roots of monic irreducible quintic]. Question for the algebraic number theory experts: Does every nonprincipal ideal become principal in some extension of the ring? And if so, does the representation of this ideal as (some algebraic integer) remain the same as the ring is further extended, and all the way to the ring of all algebraic integers? A mathematically proper GCD is probably far too messy to justify the effort to put it into code. As for GCD(1,π), it is an ideal containing 1, and the only correct ring theoretic value, if you insist on a number, is 1. On the other hand, GCD(e,π) is the ideal (e,π) whatever the containing ring. I just cannot envision a situation where the GCD is zero. I'd say the best way to handle a recalcitrant GCD is to return it unevaluated. -- Gene
________________________________ From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Sent: Saturday, November 30, 2013 9:06 PM Subject: Re: [math-fun] GCD[1,π]
On Fri, Nov 29, 2013 at 11:44 AM, Bill Gosper <billgosper@gmail.com> wrote:
OK, I give up. Especially since anyone who agrees with me can just In[895]:= Unprotect[GCD]; GCD[a_, b_] /; a/b ∉ Rationals = 0;
In[896]:= GCD[1/6, 1/9]
Out[896]= 1/18
In[897]:= {GCD[π, 1], GCD[1, π]}
Out[897]= {0, 0}
In[908]:= GCD[E,π]
Out[908]= GCD[E, π]
In[909]:= GCD[Sqrt[2], π]
Out[909]= 0
[...]
ARGH!
In[952]:= GCD[1198 - 197*I, 1147 + 398*I]
Out[952]= 0 <Hasty retreat>
In[953]:= Unprotect[GCD]; Clear[GCD]; GCD[1198 - 197*I, 1147 + 398*I]
Out[953]= 16 + 19 I
OK, how about Unprotect[GCD]; GCD[a_, b_] /; a/b \[NotElement] Rationals && a/b \[Element] Reals =0; In[1006]:= GCD[1198 + 197*I, 1147 + 398*I]
Out[1006]= 25 + 42 I
In[1007]:= GCD[1/6, 1/9]
Out[1007]= 1/18
In[1008]:= GCD[E, 1]
Out[1008]= 0
This time fer shure. --rwg
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun