Not Coprime means Common Prime Factor

Theorem

Let $a, b \in \Z$.

If $d \backslash a$ and $d \backslash b$ such that $d > 1$, then $a$ and $b$ have a common divisor which is prime.

Proof

As $d > 1$, it has a prime decomposition.

Thus there exists a prime $p$ such that $p \backslash d$.

From Divides is Ordering on Positive Integers, we have $p \backslash d, d \backslash a \implies p \backslash a$, and similarly for $b$.

The result follows.

$\blacksquare$