Euclid's Lemma
Euclid's Lemma is a result in number theory attributed to Euclid. It states that:
A positive integer 
is a prime number if and only if 
implies that 
or 
, for all integers 
and 
.
Proof of Euclid's Lemma
Without loss of generality, suppose 
(otherwise we are done). By Bezout's Lemma, there exist integers such that 
such that 
. Hence 
and 
. Since 
and (by hypothesis), 
, as desired.
On the other hand, if is not prime, then it must be composite, i.e., 
, for integers 
both greater than 1. Then, 
and 
.
This completes the proof.
