Prime Not Divisor then Coprime

Theorem

Let $p, a \in \Z$.

If $p$ is a prime number then:

$p \nmid a \implies p \perp a$

where:

• $p \nmid a$ denotes that $p$ does not divide $a$
• $p \perp a$ denotes that $p$ and $a$ are coprime.

It follows directly that if $p$ and $q$ are primes, then:

• $p \backslash q \implies p = q$;
• $p \ne q \implies p \perp q$.

Proof

Let $p \in \Bbb P, p \nmid a$. We need to show that $\gcd \left\{{a, p}\right\} = 1$.

Let $\gcd \left\{{a, p}\right\} = d$.

As $d \backslash p$, we must have $d = 1$ or $d = p$ by GCD with Prime.

But if $d = p$, then $p \backslash a$ by definition of greatest common divisor.

So $d \ne p$ and therefore $d = 1$.

$\blacksquare$

Sources

• George E. Andrews: Number Theory (1971): $\S 2.2$: Example $2.11$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 12.1$