Euclid’s lemma

Euclid’s lemma is a key step for proving the Fundamental theorem of arithmetic: Given $𝑝 ∣ 𝑎 𝑏$ where $𝑝, 𝑎, 𝑏 \in ℕ$ and $𝑝$ is prime, then $𝑝 ∣ 𝑎$ and/or $𝑝 ∣ 𝑏$ . num We may generalize this to

[𝑛 ∣ 𝑎 𝑏] \land [g c d (𝑛, 𝑎) = 1] ⟹ 𝑛 ∣ 𝑏

Proof

Since $𝑛$ and $𝑎$ are relatively prime, by Bézout’s lemma there exists $𝑠, 𝑡 \in ℤ$ such that $1 = 𝑠 𝑛 + 𝑡 𝑎$ . Multiplying both sides by $𝑏$ , we have $𝑏 = 𝑠 𝑛 𝑏 + 𝑡 𝑎 𝑏$ , and since $𝑛 ∣ 𝑠 𝑛 𝑏$ and $𝑛 ∣ 𝑡 𝑎 𝑏$ , $𝑛 ∣ 𝑏$ .

tidy | en | SemBr

Euclid’s lemma

Graph View

Backlinks