GCD of Integer and Divisor

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b \in \Z_{>0}$, i.e. integers such that $a, b > 0$.


Then:

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


Proof

$a \divides b$ by hypothesis, $a \divides a$ from Integer Divides Itself.

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


Note that 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