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$ . Thus the lemma's converse holds as well. $\blacksquare$

Page

Toolbox

Search

Euclid's Lemma

Proof of Euclid's Lemma

See Also