Common divisor divides GCD

Dependencies:

  1. GCD is the smallest Linear Combination

Common divisor of a set of numbers divides their GCD.

Proof

GCD of a set of numbers is a linear combination of those numbers, so a common divisor would divide it.

Dependency for:

  1. gcd is associative
  2. gcd(a1/d, a2/d, ..., an/d) = gcd(a1, a_2, ..., an)/d

Info:

Transitive dependencies:

  1. Integer Division Theorem
  2. GCD is the smallest Linear Combination