# [racket-dev] feature request: gcd, lcm for rationals

What does "divides" even mean in Q? I think we need David to explain
what his extension of GCD and LCM means here, in that "divisors" and
"multiples" are fairly trivial things in Q.
Carl Eastlund
On Fri, Dec 9, 2011 at 3:08 PM, J. Ian Johnson <ianj at ccs.neu.edu> wrote:
>* What? The greatest common divisor would definitely not divide 1, unless it truly were 1.
*>* -Ian
*>* ----- Original Message -----
*>* From: "Jens Axel Søgaard" <jensaxel at soegaard.net>
*>* To: "David Van Horn" <dvanhorn at ccs.neu.edu>
*>* Cc: "Racket Dev List" <dev at racket-lang.org>
*>* Sent: Friday, December 9, 2011 2:04:46 PM GMT -05:00 US/Canada Eastern
*>* Subject: Re: [racket-dev] feature request: gcd, lcm for rationals
*>*
*>*
*>*
*>*
*>* One definition of greatest common divisor in a ring R is:
*>* d is a greatest common divisor of x and y when:
*>* i) d divides both x and y
*>* ii) If e is a divisor of both x and y, then d divides e
*>*
*>*
*>* Now let's consider the ring Q. Since Q is a field, 1 divides all elements.
*>*
*>*
*>* This implies that 1 is a greatest common divisor of any non-zero x and y.
*>* ( ad i) 1 is a divisor of both x and y
*>* ad ii) 1 is a divisor of e )
*>*
*>*
*>* It is therefore not obvious that gcd should be extendend as you suggest.
*>* But maybe we can finde another name for the operation?
*>*
*>*
*>* /Jens Axel
*>*
*>*
*>*
*>* 2011/12/7 David Van Horn < dvanhorn at ccs.neu.edu >
*>*
*>*
*>* It would be nice if gcd and lcm were extended to rational numbers, which seems in-line with Scheme's philosophy (but not standards) on numbers.
*>*
*>* (define (gcd-rational . rs)
*>* (/ (apply gcd (map numerator rs))
*>* (apply lcm (map denominator rs))))
*>*
*>* (define (lcm-rational . rs)
*>* (/ (abs (apply * rs))
*>* (apply gcd-rational rs)))
*>*
*>* David
*