Euclid's Lemma
Euclid's Lemma is a result in number theory, that is attributed to Euclid. It states that:
A positive integer is a prime number if and only if
or
Proof of Euclid's Lemma
There are two proofs of Euclid's lemma.
First Proof
By assumption , thus we can use Bezout's lemma to find integers
such that
. Hence
and
. Since
and
(by hypothesis), we conclude that
as claimed.
Second Proof
We have , so
, with
an integer. Dividing both sides by
, we have
. But
implies
is only an integer if
. So
,
which means
must divide
.