Euclid's Algorithm in Python?

[James Dennett]

Antoon Pardon wrote:

> On 2005-08-08, Bengt Richter <bokr at oz.net> wrote:
> 
>>On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jrastrick at student.usyd.edu.au> wrote:
>>
>>
>>>Good point. I suppose I'd only ever seen it implemented with the if
>>>test, but you're right, the plain while loop should work fine. Silly
>>>me.
>>>
>>>def gcd(a,b):
>>>    while b != 0:
>>>          a, b = b, a%b
>>>   return a
>>>
>>>Even nicer.
>>>
>>
>>what is the convention for handling signed arguments? E.g.,
> 
> 
> As far as I understand the convention is it doesn't make
> sense to talk about a gcd if not all numbers are positive.
> 
> I would be very interested if someone knows what the gcd
> of 3 and -3 should/would be.

Within the integers, common definitions of gcd don't distinguish
positive from negative numbers, so if 3 is a gcd of x and y then
-3 is also a gcd.  That's using a definition of gcd as something
like "g is a gcd of x and y if g|x and g|y and, for any h such
that h|x and h|y, h|g", i.e., a gcd is a common divisor and is
divisible by any other common divisor.  The word "greatest" in
this context is wrt the partial ordering imposed by | ("divides").
(Note that "|" in the above is the mathematical use as a|b if
there is an (integral) c such that ac=b, i.e., b is divisible
by a.  These definitions generalize to rings other than the
integers, without requiring a meaningful < comparison on the
ring.)

All of that said, it would be reasonable when working in the
integers to always report the positive value as the gcd, to
make gcd a simpler function.  For some applications, it won't
matter if you choose positive or negative, so going positive
does no harm, and others might be simplified by assuming gcd>0.

-- James