GCD is the smallest Linear Combination

Dependencies:

  1. Integer Division Theorem Used in proof

The GCD of a set of numbers is their smallest positive linear combination.

\[ \gcd(a_1, a_2, \ldots, a_n) = \min^+\left( \sum_{i=1}^n a_i\mathbb{Z} \right) \]

Proof

Let $g = \gcd(a_1, a_2, \ldots, a_n)$. Let $d = \sum_{i=1}^n k_ia_i$ be the smallest positive linear combination of $[a_1, a_2, \ldots, a_n]$.

Since $g \mid a_i$, $g \mid d$. So $g \le d$.

Let $a_i = qd + r$, where $0 \le r \lt d$ (by integer division theorem). Therefore, $r = a_i - qd$ is a linear combination of $[a_1, a_2, \ldots, a_n]$ which is smaller than $d$. Since $d$ is the smallest positive linear combination, $r$ must be 0. Therefore, $d$ divides $a_i$.

Since $d$ divides all $a_i$, it is a common divisor of $[a_1, a_2, \ldots, a_n]$. Therefore, $d \le g$.

Since $d \le g$ and $g \le d$, $d = g$.

Dependency for:

  1. Existence of Modular Inverse Used in proof
  2. Product of coprime divisors is divisor
  3. Euclid's lemma Used in proof
  4. If x divides ab and x is coprime to a, then x divides b
  5. Common divisor divides GCD
  6. Subgroups of a cyclic group

Info:

Transitive dependencies:

  1. Integer Division Theorem