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\text{or}p\mid b\mathrm{.}$

• 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.