Number theory MOC

Euclid’s lemma

Euclid’s lemma is a key step for proving the Fundamental theorem of arithmetic: Given where and is prime, then and/or . num We may generalize this to

Proof

Since and are relatively prime, by Bézout’s lemma there exists such that . Multiplying both sides by , we have , and since and , .

---

tidy | en | sembr