GCD iff Divisible by Common Divisor

From ProofWiki

Jump to: navigation, search

Theorem

Let $a, b \in \Z$ such that not both of $a$ and $b$ are zero.

Let $d \in \Z: d > 0$.

Then $d = \gcd \left\{{a, b}\right\}$ iff:

$(1): \quad d \backslash a \land d \backslash b$

$(2): \quad c \backslash a \land c \backslash b \implies c \backslash d$

That is, in the set of positive integers, $d$ is the GCD of $a$ and $b$ if and only if $d$ is a common divisor of $a$ and $b$, and any other common divisor of $a$ and $b$ also divides $d$.

Then from Common Divisor Divides GCD, $c \backslash a \land c \backslash b \implies c \backslash d$.

Now suppose $d \backslash a \land d \backslash b$, and any $c$ that divides both $a$ and $b$ also divides $d$.

From $d \backslash a \land d \backslash b$, we see that $d$ is a common divisor of $a$ and $b$.

From $c \backslash a \land c \backslash b$, we see that $c$ is also a common divisor of $a$ and $b$.

Also, we have that $c \backslash d$.

From Integer Absolute Value Greater than Divisors, we see that (in the domain of $\Z_{>0}$) $c \backslash d \implies c \le d$.

Thus, whatever $c$ may be, it is no larger than $d$. Therefore, $d$ must be the greatest of all the common divisors of $a$ and $b$.

$\blacksquare$

Thus it is seen that the two definitions of a GCD are logically equivalent.