애플릿

---

---

증명

---

\(\overline{\rm AB}\), \(\overline{\rm CD}\)는 \(\overline{\rm AB}\ne\overline{\rm CD}\)이고 \(\overline{\rm AB}>\overline{\rm CD}\)라 하자. 큰 수를 작은 수로 나누어 나머지 수를 구하고, 이전의 작은 수를 큰 수로 놓고 이전의 나머지 수를 작은 수로 놓아 이전 방법을 반복해서 하자. 마지막 나머지수가 \(1\)이라고 하자.

그러면 두 수 \(\overline{\rm AB}\), \(\overline{\rm CD}\)가 서로소임을 보여야 한다. 즉, \(\overline{\rm AB}\), \(\overline{\rm CD}\)를 공통으로 나눌 수 있는 수는 \(1\) 밖에 없음을 보여야 한다.

---

\(\overline{\rm AB}\), \(\overline{\rm CD}\)가 서로소가 아니라고 하자. \(e\ne1\)인 \(e\)에 대하여 \(\overline{\rm AB}=me\), \(\overline{\rm CD}=ne\)인 수 \(m\), \(n\)이 존재한다. \(\overline{\rm CD}\)는 \(\overline{\rm BF}\)의 약수이며 어떤 수 \(k_1\)에 대하여 \(\overline{\rm BF}=k_1\overline{\rm CD}< \overline{\rm AB}\)인 \(\overline{\rm BF}\)를 잡자. \(\overline{\rm AB}-\overline{\rm BF}=\overline{\rm AB}-k_1\overline{\rm CD}=\overline{\rm FA} < \overline{\rm CD}\)라 하자. \(\overline{\rm AF}\)가 DG의 약수이며 어떤 수 \(k_2\)에 대하여 \(\overline{\rm DG}=k_2\overline{\rm AF}\)인 \(\overline{\rm DG}\)를 잡자. \(\overline{\rm CD}-\overline{\rm DG}=\overline{\rm CD}-k_2\overline{\rm AF}=\overline{\rm CG}< \overline{\rm AF}\)라 하자. \(\overline{\rm GC}\)가 \(\overline{\rm DG}\)의 약수이며 어떤 수 \(k_3\)에 대하여 \(\overline{\rm FH}=k_3\overline{\rm GC}\)인 \(\overline{\rm FH}\)를 잡자. \(\overline{\rm AF}-\overline{\rm FH}=\overline{\rm AF}-k_3\overline{\rm GC}=\overline{\rm AH}=1\)이라고 하자. [VII권 명제 12]

\(e\)는 \(\overline{\rm CD}\)의 약수이고, \(\overline{\rm CD}\)는 \(\overline{\rm BF}\)의 약수이므로, \(e\)는 \(\overline{\rm BF}\)의 약수이다.

그런데 \(e\)는 \(\overline{\rm AB}\)의 약수이다. 그러므로 나머지 수 \(\overline{\rm AF}\)는 \(\overline{\rm AF}=\overline{\rm AB}-\overline{\rm BF}\)이므로 \(e\)는 나머지 수 \(\overline{\rm AF}\)의 약수이다. 그런데 \(\overline{\rm AF}\)는 \(\overline{\rm DG}\)의 약수이다. 그러므로 \(e\)는 \(\overline{\rm DG}\)의 약수이다. 그러므로 나머지 수 \(\overline{\rm CG}\)는 \(\overline{\rm CG}=\overline{\rm DC}-\overline{\rm DG}\)이므로 \(e\)는 또한 나머지 수 \(\overline{\rm CG}\)의 약수이다.

그런데 \(\overline{\rm CG}\)는 \(\overline{\rm FH}\)의 약수이다. 그러므로 \(e\)는 또한 \(\overline{\rm FH}\)의 약수이다. 그런데 \(e\)는 \(\overline{\rm FA}\)의 약수이다

그러므로 나머지 수 \(\overline{\rm AH}\)는 \(\overline{\rm AH}=\overline{\rm FA}-\overline{\rm FH}\)이므로 \(e\)는 \(\overline{\rm AH}\)의 약수이다.

그런데 \(e\ne1\)인 \(e\)는 \(\overline{\rm AH}=1\)인 약수이다. 이것은 모순이다.

그러므로 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 공약수는 \(1\) 외에는 어떤 수도 없다. \(\overline{\rm AB}\), \(\overline{\rm CD}\)가 서로소가 아니라고 하는 것은 불가능하다. 그러므로 \(\overline{\rm AB}\), \(\overline{\rm CD}\)는 서로소이다. [VII권 명제 12]

---

서로 다른 두 수에 대하여, 큰 수를 작은 수로 나누어 나머지 수를 구하고, 이전의 작은 수를 큰 수로 놓고 이전의 나머지 수를 작은 수로 놓아 이전 방법을 반복해서 하자. 만약 나머지 수가 그 전의 수를 잴 수 없으면 즉, 나머지 수가 \(1\)이면 원래 두 수는 서로소이다.

Q.E.D.

부연설명

---

두 수 \(54\)와 \(85\)는 서로소임을 이 명제를 사용하여 다음과 같이 보일 수 있다.

\(85-2\times 31=23\)

\(31-1\times 23=8\)

\(23-2\times8=7\)

\(8-1\times7=1\)

유클리드는 측정한다(measure)라고 하였는데 여기서는 나눈다(divide)로 사용하였다. 이 명제는 유클리드 호제법이라 알려져 있다.

이 명제는 다음 명제에서 사용된다.