gcd, lcm - greatest common divisor and least common multiple


(import (rnrs))                     ;R6RS
(import (rnrs base))                ;R6RS
(import (scheme r5rs))              ;R7RS
(import (scheme base))              ;R7RS


(gcd number ...)
(lcm number ...)


These procedures return the greatest common divisor and the least common multiple of their arguments, respectively. The result is always non-negative. The arguments must be integers.
Greatest common divisor
If all arguments are zero, or no arguments are given, then gcd returns zero. Otherwise the greatest common divisor is the largest integer that divides each of the arguments.
Least common multiple
If there are no arguments then 1 is returned. If one of the arguments is zero then zero is returned. Otherwise lcm returns the smallest positive integer that is divisible by each of the arguments.


Returns a non-negative number object.


(gcd 32 -36)     =>   4
(gcd)            =>   0

(lcm 32 -36)     =>   288
(lcm 32.0 -36)   =>   288.0
(lcm)            =>   1


The gcd procedure is needed internally in Scheme implementations for rational number support. Its implementation is not trivial, so it makes sense to provide it to users as well. The lcm procedure is a natural complement which is easily implemented once gcd is available.


These procedures are identical in all RnRS revisions since R2RS. An example with an inexact number was added in R4RS, but the signature did not change.

R7RS implementations that do not support arbitrarily large exact integers will not always be able to represent the mathematically expected result of lcm.


These procedures can raise exceptions with the following condition types:
&assertion (R6RS)
An argument was outside its domain.
The assertions described above are errors. Implementations may signal an error, extend the procedure's domain of definition to include such arguments, or fail catastrophically.




R4RS, IEEE Scheme, R5RS, R6RS, R7RS


The first Scheme report to name these procedures was R2RS. Nevertheless, Scheme has always had a gcd procedure because one was present even in MacLISP (see the LISP/MACLISP Reference Manual, 1973, Moon et al). The MacLISP version did not work with inexact numbers.

An algorithm for computing gcd appears in Euclid's Elements (circa 300 BCE).


This page is part of the scheme-manpages project. It includes materials from the RnRS documents. More information can be found at https://github.com/schemedoc/manpages/.


Ikarus Scheme 0.0.4 has the following bug:
(gcd -1)  => -1    ; wrong! should be 1

Markup created by unroff 1.0sc,    March 04, 2023.