Greatest Common Divisor

Overview

Let $a$ and $b$ be two nonzero integers. Then the greatest common divisor (GCD) of $a$ and $b$ , denoted $gcd (a, b)$ , is the greatest positive integer $d$ such that $d$ is a divisor of both $a$ and $b$ . If both $a$ and $b$ are zero, the GCD is considered either undefined or $0$ .

Let $a$ and $b$ be two integers. Then the least common multiple (LCM) of $a$ and $b$ , denoted $lcm (a, b)$ , is the smallest positive integer $d$ such that $a$ and $b$ are both divisors of $d$ . If either $a$ or $b$ is zero, the LCM is sometimes considered either undefined or $0$ .

Definitions

Group Theory

In group theory, the GCD of $a, b \in Z^{+}$ is defined to be the positive generator of group ${m a + n b ∣ m, n \in Z}$ under addition.

The LCM is defined to be the positive generator of $a Z \cap b Z$ under addition.

Number Theory

In number theory, both GCD and LCM are defined by an appeal to the fundamental theorem of arithmetic. In particular, integers $m$ and $n$ have unique prime factorizations:

\begin{aligned} m & = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots \times p_{k}^{a_{k}} \\ n & = p_{1}^{b_{1}} \times p_{2}^{b_{2}} \times \dots \times p_{k}^{b_{k}} \end{aligned}

Then

\begin{aligned} lcm (m, n) & = p_{1}^{max (a_{1}, b_{1})} \times p_{2}^{max (a_{2}, b_{2})} \times \dots \times p_{k}^{max (a_{k}, b_{k})} \\ gcd (m, n) & = p_{1}^{min (a_{1}, b_{1})} \times p_{2}^{min (a_{2}, b_{2})} \times \dots \times p_{k}^{min (a_{k}, b_{k})} \end{aligned}

Order Theory

In order theory, the GCD is defined to be the greatest lower bound of the set of positive integers ordered by divisibility. That is, $gcd (a, b) = inf {a, b}$ with respect to divisibility.

The LCM is similarly defined to be the least upper bound of the set of positive integers ordered by divisibility. That is, $lcm (a, b) = sup {a, b}$ with respect to divisibility.

Monotonicity

Both GCD and LCM are monotonic under divisibility. That is,

If $a ∣ A$ and $b ∣ B$ , then $gcd (a, b) ∣ gcd (A, B)$ .
If $a ∣ A$ and $b ∣ B$ , then $lcm (a, b) ∣ lcm (A, B)$ .

Product Identity

We can relate $lcm$ and $gcd$ of two arguments like so:

lcm (a, b) = \frac{a b}{gcd (a, b)} .

We can generalize to $n$ argumets using PIE applied to maximums. This yields relationship:

lcm (a_{1}, \dots, a_{n}) = \frac{\prod_{\begin{matrix} S \subseteq {a_{1}, \dots, a_{n}} \\ # S odd \end{matrix}} gcd (S)}{\prod_{\begin{matrix} S \subseteq {a_{1}, \dots, a_{n}} \\ # S even \end{matrix}} gcd (S)}

This immediately implies $lcm (a_{1}, \dots, a_{n}) = a_{1} \dots a_{n}$ if and only if $gcd (a_{i}, a_{j}) = 1$ for all $1 \leq i < j \leq n$ .

Bézout's Lemma

For any pair of positive integers $a$ and $b$ , there exist integers $m$ and $n$ such that

gcd (a, b) = m a + n b .

Euclidean Algorithm

Let $a, b \in Z^{+}$ . By the division algorithm, there exist integers $q$ and $r$ such that $a = b q + r$ where $0 \leq r < b$ . Then $gcd (a, b) = gcd (b, r)$ .

The Euclidean algorithm (also known as Euclid's algorithm) is a method for computing the GCD of two positive integers using the above identity. It works by repeatedly applying the division algorithm, stopping once the remainder is $0$ . For integers $a, r_{0} \in Z^{+}$ , the process looks as follows:

\begin{aligned} a & = r_{0} q_{0} + r_{1} \\ r_{0} & = r_{1} q_{1} + r_{2} \\ r_{1} & = r_{2} q_{2} + r_{3} \\ ⋮ \\ r_{n - 1} & = r_{n} q_{n} + 0 \end{aligned}

This shows that $gcd (a, r_{0}) = \dots = gcd (r_{n - 1}, r_{n}) = gcd (r_{n}, 0) = r_{n}$ .