Greatest Common Divisor

In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers \(a\), \(b\), the greatest common divisor of \(a\) and \(b\) is denoted as \(\begin{equation} \gcd(a,b) \end{equation}\). 1 2

Implementation

Euclidean algorithm

Euclidean algorithm is one of the most effiecient method for computing the GCD of two integers.

def gcd(a: int, b: int) -> int:
    if b == 0:
        return abs(a)
    else:
        return gcd(b, a mod b)

Least Common Multiple

\(gcd(a, b)\) can also be detrieved from \(\operatorname{lcm}(a,b)\), recall that Least Common Multiple (LCM) is the smallest positive integer that is divisible by both \(a\) and \(b\).

\[\begin{equation} {\gcd(a,b)} = \frac{\lvert ab \rvert}{\operatorname{lcm}(a,b)} \end{equation}\]

def gcd_from_lcm(a: int, b: int) -> int:
    if a == 0 and b == 0: return 0
    if a == 0: return abs(b)
    if b == 0: return abs(a)
    return abs(a * b) // lcm(a, b)

GCD of a List of Integers

To compute the GCD of a list integers, we iterate the array:

Calculate the GCD of 0 and first element, denoted \(result\);
Calculate the GCD of \(result\) and next element, and repeat till end.

def gcd_of_list(arr: list[int] -> int):
    if not arr: raise ValueError("Array must contain at least one element")
    result = 0
    for ele in arr:
        result = gcd(result, ele)
    return result

Practice

References

Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950.
↗ Greatest Common Divisor - Wikipedia