gcd: Find the Greatest Common Divisor, Smallest Common Multiple,...

In Ironholds/primes: Fast Functions for Prime Numbers

Find the Greatest Common Divisor, Smallest Common Multiple, or Coprimality

Description

These functions provide vectorized computations for the greatest common divisor (gcd), smallest common multiple (scm), and coprimality. Coprime numbers are also called mutually prime or relatively prime numbers. The smallest common multiple is often called the least common multiple.

Usage

gcd(m, n)

scm(m, n)

coprime(m, n)

Rgcd(...)

Rscm(...)

Arguments

m, n, ...

integer vectors.

Details

The greatest common divisor uses Euclid's algorithm, a fast and widely used method. The smallest common multiple and coprimality are computed using the gcd, where scm = \frac{a}{gcd(a, b)} \times b and two numbers are coprime when gcd = 1.

The gcd, scm, and coprime functions perform element-wise computation. The Rgcd and Rscm functions perform gcd and scm over multiple values using reduction. That is, they compute the greatest common divisor and least common multiple for an arbitrary number of integers based on the properties gcd(a_1, a_2, ..., a_n) = gcd(gcd(a_1, a_2, ...), a_n) and scm(a_1, a_2, ..., a_n) = scm(scm(a_1, a_2, ...), a_n). The binary operation is applied to two elements; then the result is used as the first operand in a call with the next element. This is done iteratively until all elements are used. It is idiomatically equivalent to Reduce(gcd, x) or Reduce(scm, x), where x is a vector of integers, but much faster.

Value

The functions gcd, scm, and coprime return a vector of the length of longest input vector. If one vector is shorter, it will be recycled. The gcd and scm functions return an integer vector while coprime returns a logical vector. The reduction functions Rgcd and Rscm return a single integer.

Author(s)

Paul Egeler, MS

Examples

gcd(c(18, 22, 49, 13), 42)
## [1] 6 2 7 1

Rgcd(18, 24, 36, 12)
## [1] 6

scm(60, 90)
## [1] 180

Rscm(1:10)
## [1] 2520

coprime(60, c(77, 90))
## [1]  TRUE FALSE

Ironholds/primes documentation built on Feb. 1, 2024, 1:26 a.m.