Euclid's Lemma
·
Mathematics/Number Thoery
Euclid's Lemma Theorem 1. (Euclid's Lemma) Let $a, b \in \mathbb{Z}$, not both zero. If $a \,|\, bc$ for $c \in \mathbb{Z}$, with gcd($a, b$) = 1, then $a \,|\, c$. Proof. By Theorem 3, $1 = ax + by$ for some $x, y \in \mathbb{Z}$. Let $bc = ka$ for some $k \in \mathbb{Z}$. Then $c = c \cdot 1 = c(ax + by) = acx + bcy = acx + kay = a(cx + ky) \Longrightarrow a \,|\, c$. $\blacksquare$ $a$와 $b$는 ..