Euclid's Lemma

Euclid's Lemma is a result in number theory attributed to Euclid. It states that:

A positive integer $p>1$ is a prime number if and only if $p \mid ab$ implies that $p \mid a$ or $p\mid b$, for all integers $a$ and $b$.


Proof of Euclid's Lemma

Without loss of generality, suppose $\gcd(p,a)=1$ (otherwise we are done). By Bezout's Lemma, there exist integers such that $x,y$ such that $px+ay=1$. Hence $b(px+ay)=b$ and $pbx+aby=b$. Since $p\mid p$ and $p \mid ab$ (by hypothesis), $p \mid pbx + aby =b$, as desired.

On the other hand, if $p>1$ is not prime, then it must be composite, i.e., $p=ab$, for integers $a,b$ both greater than 1. Then, $p\nmid a$ and $p\nmid b$.

This completes the proof.

See Also