Lemma. Euclid's Lemma [0050]

Let and prime with then or .

Proof. We only need to show the case where . Because is prime, it has exactly the divisors . does not divide so their only common divisor is . Thus . We are done by applying this corollary.