Not Coprime means Common Prime Factor
Jump to navigation
Jump to search
Theorem
Let $a, b \in \Z$.
If $d \divides a$ and $d \divides 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 \divides d$.
From Divisor Relation on Positive Integers is Partial Ordering, we have $p \divides d, d \divides a \implies p \divides a$, and similarly for $b$.
The result follows.
$\blacksquare$