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$는 서로소이기 때문에 나눗셈이라는 연산의 관점에서 서로 공유하는 부분이 없다. 따라서 $a$가 $bc$를 나눌 때 $a$의 기여는 오직 $c$에만 해당되므로 $a$는 $c$를 나눈다고 할 수 있다.