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.