In Number Theory, the result that
A positive integer is a prime number if and only if or
is attributed to Euclid
Proof of Euclid's lemma
There are two proofs of Euclid's lemma.
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.
We have , so , with an integer. Dividing both sides by , we have . But implies is only an integer if . So , which means must divide .