Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$) and let $a, b \in \mathbb{Z}$. If $p \mid ab$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$) then

$p \mid a \qquad \text{or} \qquad p \mid b .$

• This is a two-line consequence, and that is the point. The work was done one page earlier: If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$; and if $a \mid c$, $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ proves that $\gcd(u,v) = 1$ together with $u \mid vw$ forces $u \mid w$, and its own Remarks record that "no primality is used" in it — the proof is pure Bézout. The summary of the page carrying it says in as many words that "primes, Euclid's lemma and unique factorisation are not proved here; they belong to a later page". This is that page, and the only new ingredient is For a prime $p$ and any integer $a$, $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime, which converts primality into the coprimality that lemma actually consumes.

• The hypothesis cannot be weakened to $p > 1$. For a composite modulus the conclusion fails, and the published witness is $6 \mid 4 \cdot 9$ while $6 \nmid 4$ and $6 \nmid 9$: dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails: $6 \mid 4 \cdot 9$ while $6 \nmid 4$ and $6 \nmid 9$. Its Remarks identify the failure as exactly the failure of coprimality, which is what primality supplies here.

• The converse holds too. For $p > 1$ the property proved here characterises primality; that is For an integer $p > 1$: $p$ is prime if and only if, for all integers $a$ and $b$, $p \mid ab$ implies $p \mid a$ or $p \mid b$, next on this page.