Greatest Common Divisor and Least Common Multiple

gcd(a,b) computes the greatest common divisor of two positive integer numbers by Euclid's algorithm.

lcm(...) computes the least common multiple of an arbitrary number of integers, iteratively applying lcm(a,b) = (a * b) / gcd(a,b).

GCD(a, b)
LCM(n, ...)

Arguments

a, b

two integer numbers.

n, ...

an integer (vector or number) and possibly more; the ... argument is for convenience, allowing e.g., LCM(2,3,4).

Value

a positive integer.

Author

Martin Maechler

Note

Very simple, but too useful to spend time on, if you need it.

See also

primes, and factorize.

Examples

GCD(12, 18)
#> [1] 6
GCD(15, 105)
#> [1] 15
GCD(84, 64)
#> [1] 4

LCM(1,2,3,4,5,6) # 60
#> [1] 60
LCM(2,3,5,7) == print(2*3*5*7) # true, of course
#> [1] 210
#> [1] TRUE
LCM(1:8) # 840
#> [1] 840

## the LCMs needed to get integer coefficients / N  in Taylor polynomial for log(1+x):
vapply(1:24, function(n) LCM(1:n), 1)
#>  [1]          1          2          6         12         60         60
#>  [7]        420        840       2520       2520      27720      27720
#> [13]     360360     360360     360360     720720   12252240   12252240
#> [19]  232792560  232792560  232792560  232792560 5354228880 5354228880