Prime not Divisor implies Coprime/Proof 1
Jump to navigation
Jump to search
Theorem
Let $p, a \in \Z$.
If $p$ is a prime number then:
- $p \nmid a \implies p \perp a$
where:
It follows directly that if $p$ and $q$ are primes, then:
- $p \divides 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 \set {a, p} = 1$.
Let $\gcd \set {a, p} = d$.
As $d \divides p$, we must have $d = 1$ or $d = p$ by GCD with Prime.
But if $d = p$, then $p \divides a$ by definition of greatest common divisor.
So $d \ne p$ and therefore $d = 1$.
$\blacksquare$