Euclid's Lemma
Theorem 1. (Euclid's Lemma) Let , not both zero. If for , with gcd() = 1, then .
Proof. By Theorem 3, for some . Let for some . Then .
와 는 서로소이기 때문에 나눗셈이라는 연산의 관점에서 서로 공유하는 부분이 없다. 따라서 가 를 나눌 때 의 기여는 오직 에만 해당되므로 는 를 나눈다고 할 수 있다.
Theorem 1. (Euclid's Lemma) Let , not both zero. If for , with gcd() = 1, then .
Proof. By Theorem 3, for some . Let for some . Then .
와 는 서로소이기 때문에 나눗셈이라는 연산의 관점에서 서로 공유하는 부분이 없다. 따라서 가 를 나눌 때 의 기여는 오직 에만 해당되므로 는 를 나눈다고 할 수 있다.