gcd

gcd Function

Syntax:

gcd &rest integers → greatest-common-denominator

Arguments and Values:

integer—an integer .

greatest-common-denominator—a non-negative integer .

Description:

Returns the greatest common divisor of integers. If only one integer is supplied, its absolute value is returned. If no integers are given, gcd returns 0, which is an identity for this operation.

Examples:

(gcd) → 0 
(gcd 60 42) → 6 
(gcd 3333 -33 101) → 1 
(gcd 3333 -33 1002001) → 11 
(gcd 91 -49) → 7 
(gcd 63 -42 35) → 7 
(gcd 5) → 5 
(gcd -4) → 4 

Exceptional Situations:

Should signal an error of type type-error if any integer is not an integer .

See Also:

lcm

Notes:

For three or more arguments,

(gcd b c ... z) ≡ (gcd (gcd a b) c ... z)

Expanded Reference: gcd

Basic greatest common divisor

gcd returns the greatest common divisor of its integer arguments. With no arguments it returns 0 (the identity element).

(gcd)
=> 0
(gcd 12)
=> 12
(gcd 12 8)
=> 4
(gcd 60 42)
=> 6

Multiple arguments

gcd accepts any number of integer arguments.

(gcd 12 8 6)
=> 2
(gcd 63 -42 35)
=> 7
(gcd 3333 -33 1002001)
=> 11

Negative arguments

gcd always returns a non-negative integer. With a single argument, it returns the absolute value.

(gcd -4)
=> 4
(gcd 91 -49)
=> 7
(gcd -12 -8)
=> 4

Coprime numbers

Two numbers are coprime when their GCD is 1.

(gcd 7 11)
=> 1
(gcd 3333 -33 101)
=> 1
(= 1 (gcd 14 15))
=> T

Practical use: simplifying fractions

gcd can be used to reduce a fraction to lowest terms.

(defun simplify (numer denom)
  (let ((g (gcd numer denom)))
    (values (/ numer g) (/ denom g))))

(simplify 12 8)
=> 3
=> 2
(simplify 100 75)
=> 4
=> 3