Euclid's lemma
If a prime
divides the product of two integers and , then must divide at least one of those integers and .
A stronger formulation of Euclid’s lemma is the following:
Eucild's lemma
Proof
Since
, there exist integers and such that . Multiplying both sides by gives . Since , such that . Substituting this into the previous equation gives , which can be rewritten as . Therefore, .