GCD and LCM

Within the classical range, Magma uses the fast classical Accelerated GCD algorithm of Kenneth Weber [Web95] to compute the GCD of two integers, and the fast classical Lehmer extended GCD (`XGCD') algorithm [Knu97, pp. 345--348] (which is about 5 times faster than the Euclidean XGCD algorithm) to compute the extended GCD of two integers.

For larger integers, Magma uses the asymptotically fast Schönhage recursive ("half-GCD") algorithm ([Sch71]; see also [Mon92, Sec. 3.8] for the basic idea, applied to polynomials). On a Sun SPARC workstation, the crossover point for the Schönhage GCD algorithm (where it beats the classical Accelerated GCD algorithm) is 32768 bits (about 10000 decimal digits), while the crossover point for the Schönhage XGCD algorithm (when it beats the Lehmer XGCD algorithm) is 6000 bits (about 2000 decimal digits).

GreatestCommonDivisor(m, n) : RngIntElt, RngIntElt -> RngIntElt

Gcd(m, n) : RngIntElt, RngIntElt -> RngIntElt

GCD(m, n) : RngIntElt, RngIntElt -> RngIntElt

The greatest common divisor of m and n, normalized to be non-negative. If either of the inputs is zero, then the result is the absolute value of the other input, while if m and n are both zero the result is zero.

GreatestCommonDivisor(s) : [RngIntElt] -> RngIntElt

Gcd(s) : [RngIntElt] -> RngIntElt

GCD(s) : [RngIntElt] -> RngIntElt

The GCD of the entries of the sequence s. If all entries of the sequence are zero, the result is zero. An error results if the sequence is the null sequence.

ExtendedGreatestCommonDivisor(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt, RngIntElt

Xgcd(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt, RngIntElt

XGCD(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt, RngIntElt

The extended GCD of m and n; returns integers g, x and y such that g is the greatest common divisor of the integers m and n, and g = x.m + y.n. If m and n are both zero, g is zero; otherwise g is always positive. If m and n are both non-zero, the multipliers x and y are unique.

ExtendedGreatestCommonDivisor(s) : [RngIntElt] -> RngIntElt, [RngIntElt]

Xgcd(s) : [RngIntElt] -> RngIntElt, [RngIntElt]

XGCD(s) : [RngIntElt] -> RngIntElt, [RngIntElt]

Given a sequence of integers s = [s₁, ..., s_r], return the non-negative integer g and a sequence X=(x₁, ..., x_r) such that g is the greatest common divisor of the integers s_i and g is the sum over i of x_i.s_i.

LeastCommonMultiple(m, n) : RngIntElt, RngIntElt -> RngIntElt

Lcm(m, n) : RngIntElt, RngIntElt -> RngIntElt

LCM(m, n) : RngIntElt, RngIntElt -> RngIntElt

The smallest non-negative integer divisible by both m and n. If m or n equals zero, the result is zero; this ensures that lcm(m, n)gcd(m, n) = m.n.

LeastCommonMultiple(s) : [RngIntElt] -> RngIntElt

Lcm(s) : [RngIntElt] -> RngIntElt

LCM(s) : [RngIntElt] -> RngIntElt

Least common multiple of the sequence of integers s.