# GCD is the smallest Linear Combination

## Dependencies:

- 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:

- Existence of Modular Inverse Used in proof
- Product of coprime divisors is divisor
- Euclid's lemma Used in proof
- If x divides ab and x is coprime to a, then x divides b
- Common divisor divides GCD
- Subgroups of a cyclic group

## Info:

- Depth: 1
- Number of transitive dependencies: 1