Euclid's Lemma
In Number Theory, the result that
A positive integer is a prime number if and only iff
or
is attributed to Euclid
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
.