애플릿

---

---

증명

---

$\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$는 $\overline{\mathrm{A}\mathrm{B}}\ne \overline{\mathrm{C}\mathrm{D}}$이고 $\overline{\mathrm{A}\mathrm{B}}>\overline{\mathrm{C}\mathrm{D}}$라 하자. 큰 수를 작은 수로 나누어 나머지 수를 구하고, 이전의 작은 수를 큰 수로 놓고 이전의 나머지 수를 작은 수로 놓아 이전 방법을 반복해서 하자. 마지막 나머지수가 $1$이라고 하자.

그러면 두 수 $\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$가 서로소임을 보여야 한다. 즉, $\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$를 공통으로 나눌 수 있는 수는 $1$ 밖에 없음을 보여야 한다.

---

$\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$가 서로소가 아니라고 하자. $e\ne 1$인 $e$에 대하여 $\overline{\mathrm{A}\mathrm{B}}=me$, $\overline{\mathrm{C}\mathrm{D}}=ne$인 수 $m$, $n$이 존재한다. $\overline{\mathrm{C}\mathrm{D}}$는 $\overline{\mathrm{B}\mathrm{F}}$의 약수이며 어떤 수 $k_1$에 대하여 $\overline{\mathrm{B}\mathrm{F}}=k_1\overline{\mathrm{C}\mathrm{D}}<\overline{\mathrm{A}\mathrm{B}}$인 $\overline{\mathrm{B}\mathrm{F}}$를 잡자. $\overline{\mathrm{A}\mathrm{B}}-\overline{\mathrm{B}\mathrm{F}}=\overline{\mathrm{A}\mathrm{B}}-k_1\overline{\mathrm{C}\mathrm{D}}=\overline{\mathrm{F}\mathrm{A}}<\overline{\mathrm{C}\mathrm{D}}$라 하자. $\overline{\mathrm{A}\mathrm{F}}$가 DG의 약수이며 어떤 수 $k_2$에 대하여 $\overline{\mathrm{D}\mathrm{G}}=k_2\overline{\mathrm{A}\mathrm{F}}$인 $\overline{\mathrm{D}\mathrm{G}}$를 잡자. $\overline{\mathrm{C}\mathrm{D}}-\overline{\mathrm{D}\mathrm{G}}=\overline{\mathrm{C}\mathrm{D}}-k_2\overline{\mathrm{A}\mathrm{F}}=\overline{\mathrm{C}\mathrm{G}}<\overline{\mathrm{A}\mathrm{F}}$라 하자. $\overline{\mathrm{G}\mathrm{C}}$가 $\overline{\mathrm{D}\mathrm{G}}$의 약수이며 어떤 수 $k_3$에 대하여 $\overline{\mathrm{F}\mathrm{H}}=k_3\overline{\mathrm{G}\mathrm{C}}$인 $\overline{\mathrm{F}\mathrm{H}}$를 잡자. $\overline{\mathrm{A}\mathrm{F}}-\overline{\mathrm{F}\mathrm{H}}=\overline{\mathrm{A}\mathrm{F}}-k_3\overline{\mathrm{G}\mathrm{C}}=\overline{\mathrm{A}\mathrm{H}}=1$이라고 하자. [VII권 명제 12]

$e$는 $\overline{\mathrm{C}\mathrm{D}}$의 약수이고, $\overline{\mathrm{C}\mathrm{D}}$는 $\overline{\mathrm{B}\mathrm{F}}$의 약수이므로, $e$는 $\overline{\mathrm{B}\mathrm{F}}$의 약수이다.

그런데 $e$는 $\overline{\mathrm{A}\mathrm{B}}$의 약수이다. 그러므로 나머지 수 $\overline{\mathrm{A}\mathrm{F}}$는 $\overline{\mathrm{A}\mathrm{F}}=\overline{\mathrm{A}\mathrm{B}}-\overline{\mathrm{B}\mathrm{F}}$이므로 $e$는 나머지 수 $\overline{\mathrm{A}\mathrm{F}}$의 약수이다. 그런데 $\overline{\mathrm{A}\mathrm{F}}$는 $\overline{\mathrm{D}\mathrm{G}}$의 약수이다. 그러므로 $e$는 $\overline{\mathrm{D}\mathrm{G}}$의 약수이다. 그러므로 나머지 수 $\overline{\mathrm{C}\mathrm{G}}$는 $\overline{\mathrm{C}\mathrm{G}}=\overline{\mathrm{D}\mathrm{C}}-\overline{\mathrm{D}\mathrm{G}}$이므로 $e$는 또한 나머지 수 $\overline{\mathrm{C}\mathrm{G}}$의 약수이다.

그런데 $\overline{\mathrm{C}\mathrm{G}}$는 $\overline{\mathrm{F}\mathrm{H}}$의 약수이다. 그러므로 $e$는 또한 $\overline{\mathrm{F}\mathrm{H}}$의 약수이다. 그런데 $e$는 $\overline{\mathrm{F}\mathrm{A}}$의 약수이다

그러므로 나머지 수 $\overline{\mathrm{A}\mathrm{H}}$는 $\overline{\mathrm{A}\mathrm{H}}=\overline{\mathrm{F}\mathrm{A}}-\overline{\mathrm{F}\mathrm{H}}$이므로 $e$는 $\overline{\mathrm{A}\mathrm{H}}$의 약수이다.

그런데 $e\ne 1$인 $e$는 $\overline{\mathrm{A}\mathrm{H}}=1$인 약수이다. 이것은 모순이다.

그러므로 $\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$의 공약수는 $1$ 외에는 어떤 수도 없다. $\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$가 서로소가 아니라고 하는 것은 불가능하다. 그러므로 $\overline{\mathrm{A}\mathrm{B}}$, $\overline{\mathrm{C}\mathrm{D}}$는 서로소이다. [VII권 명제 12]

---

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

Q.E.D.

부연설명

---

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

$85-2\times 31=23$

$31-1\times 23=8$

$23-2\times 8=7$

$8-1\times 7=1$

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

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