Introductions to GCD

Introduction to the GCD and LCM (greatest common divisor and least common multiple)

General

The legendary Greek mathematician Euclid (ca. 325–270 BC) suggested an algorithm for finding the greatest common divisor of two integers, which was later named the Euclidean algorithm. This algorithm, as well as computationally refined versions, are in widespread use today.

Definitions of GCD and LCM

The GCD and LCM group of functions includes the following three functions:
• the greatest common divisor (gcd): gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m]))
• the least common multiple (lcm): lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m]))
• the extended greatest common divisor (egcd): egcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m]))

These functions are defined in the following ways:

Connections within the group of the GCD and LCM and with other function groups

Representations through equivalent functions

The functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) satisfy the following interrelations:

The best-known properties and formulas of the GCD and LCM

Specific values for specialized variables

The functions GCD and LCM gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])), egcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])), and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) have the following values for specialized values:

The first values of the greatest common divisor (gcd(m, n)) of the integers m and n for 1≤m≤20 and 1≤n≤20 are described in the following table:

The first values of the extended greatest common divisor (egcd(m,n) of the integers m and n for 1≤m≤10 and 1≤n≤10 are described in the following table:

The first values of the least common multiple (lcm(m,n)) of the integers m and n for 1≤m≤20 and 1≤n≤20 are described in the following table:

Analyticity

The functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) are nonanalytical functions defined over (ℤ^m) with values in ℤ.
The function egcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) is a vector-valued nonanalytical function defined over (ℤ^m).

Periodicity

All three functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])), egcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])), and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) do not have periodicity.

Parity and symmetry

The functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) are even functions:

The functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) have permutation symmetry:

Series representations

The function gcd(m,n) has the following sum representations:

where ⌊p⌋ is the floor function and (Subscript[δ, q]) is the Kronecker delta function.

Product representations

The functions gcd((Subscript[n, 1]),(Subscript[n, 2])) and lcm((Subscript[n, 1]),(Subscript[n, 2])) have the following product representations:

Generating functions

The function gcd(k,n) can be represented as the coefficients of the series expansion of corresponding generating functions, which includes a sum of the Euler totient function:

Transformations with multiple arguments

The GCD and LCM functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])), egcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])), and  lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) satisfy special relations including multiple arguments, for example:

Identities

The GCD and LCM functions satisfy some parallel identities that can be presented in the forms shown in the following table:

Summation

There are many finite and infinite sums containing GCD and LCM functions, for example:

Limit operation

The following two related limits include the function gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])). The third limit includes lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])):

Inequalities

The functions gcd((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) and lcm((Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m])) satisfy various inequalities, for example:

Applications of the GCD and LCM

The GCD and LCM functions have numerous applications throughout mathematics, number theory, symbolic algorithms, and linear Diophantine equations.

Copyright