GCD of Integer and Divisor

Theorem

Let $a, b \in \Z_{>0}$ be strictly positive integers.

Then:

$a \divides b \implies \gcd \set {a, b} = a$

Proof

We have:

$a \divides b$ by hypothesis

$a \divides a$ from Integer Divides Itself.

Thus $a$ is a common divisor of $a$ and $b$.

Then from Absolute Value of Integer is not less than Divisors:

$\forall x \in \Z: x \divides a \implies x \le \size a$

As $a$ and $b$ are both positive, the result follows.

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Example $\text {2-6}$