GCD of Integer and Divisor

Theorem

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

Then:

$a \backslash b \implies \gcd \left\{{a, b}\right\} = a$

Proof

• $a \backslash b$ by hypothesis, $a \backslash a$ from Every Integer Divides Itself.

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

• Note that $\forall x \in \Z: x \backslash a \implies x \le \left|{a}\right|$ from Integer Absolute Value Greater than Divisors.

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

$\blacksquare$

Sources

• George E. Andrews: Number Theory (1971): $\S 2.2$: Example $2.6$