VII 권
명제
명제 2
서로소가 아닌 두 수에 대하여 이 두 수를 공통으로 나눌 수 있는 최대공약수를 구할 수 있다.
서로소가 아닌 두 수 \(\overline{\rm AB}\), \(\overline{\rm CD}\)에 대하여, 이 두 수를 공통으로 나누는 최대공약수를 구할 수 있다.
VII 권
명제
서로소가 아닌 두 수에 대하여 이 두 수를 공통으로 나눌 수 있는 최대공약수를 구할 수 있다.
서로소가 아닌 두 수 \(\overline{\rm AB}\), \(\overline{\rm CD}\)에 대하여, 이 두 수를 공통으로 나누는 최대공약수를 구할 수 있다.
서로소가 아닌 두 수 \(\overline{\rm AB}\), \(\overline{\rm CD}\)가 있다.
그러면 두 수 \(\overline{\rm AB}\), \(\overline{\rm CD}\)를 공통으로 나누는 최대공약수를 구하여야 한다.
1) \(\overline{\rm CD}\)는 \(\overline{\rm AB}\)의 약수라고 하자.
\(\overline{\rm CD}\)는 자기 자신의 약수이므로 \(\overline{\rm CD}\)는 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 공약수이다. \(\overline{\rm CD}\) 보다 큰 수는 자기 자신 \(\overline{\rm CD}\)의 약수일 수 없으므로 \(\overline{\rm CD}\)가 가장 큰 수임을 명백하다.
2) \(\overline{\rm CD}\)가 \(\overline{\rm AB}\)의 약수가 아니라고 하자.
그러면 \(\overline{\rm AB}\)와 \(\overline{\rm CD}\) 중 큰 수를 작은 수로 나누어 나머지 수를 구하고, 이전의 작은 수를 큰 수로 놓고 이전의 나머지 수를 작은 수로 놓아 이전 방법을 반복해서 하자.
이 때 나머지 수는 1이 아니다. 왜냐하면 나머지 수가 \(1\)이면 \(\overline{\rm AB}\), \(\overline{\rm CD}\)가 서로소이어서[VI권 명제 1], 가정에 위배된다.[VII권 정의 12]
그러므로 어떤 나머지 수가 그 전 수의 약수이다. \(\overline{\rm AB}>\overline{\rm CD}\)라 하자.
\(\overline{\rm BE}\)의 \(\overline{\rm CD}\)의 배수이며 어떤 수 \(k_1\)에 대하여 \(\overline{\rm AB}-\overline{\rm BE}=\overline{\rm AB}-k_1\overline{\rm CD}=\overline{\rm AE}< \overline{\rm CD}\)이라 하자. \(\overline{\rm DF}\)는 \(\overline{\rm AE}\)의 배수이며 어떤 수 \(k_2\)에 대하여 \(\overline{\rm CD}-\overline{\rm DF}=\overline{\rm CF}=\overline{\rm CD}-k_2\overline{\rm AE}=\overline{\rm CF}< \overline{\rm AE}\)이라 하자. 그리고 나머지 수 \(\overline{\rm CF}\)는 \(\overline{\rm AE}\)의 약수라 가정하자. ---(*)
그러므로 \(\overline{\rm CF}\)는 \(\overline{\rm AE}\)의 약수이고 \(\overline{\rm AE}\)는 \(\overline{\rm DF}\)의 약수이므로 \(\overline{\rm CF}\)는 \(\overline{\rm DF}\)의 약수이다. 그런데 \(\overline{\rm CF}\)는 자기자신 \(\overline{\rm CF}\)의 약수이다. 그러므로 \(\overline{\rm CD}=\overline{\rm CF}+\overline{\rm DF}\)이므로 \(\overline{\rm CF}\)는 \(\overline{\rm CD}\)의 약수이다.
\(\overline{\rm CD}\)는 \(\overline{\rm BE}\)의 약수이다. 그러므로 \(\overline{\rm CF}\)는 \(\overline{\rm BE}\)의 약수이다. 그런데 \(\overline{\rm CF}\)는 \(\overline{\rm AE}\)의 약수이다. 그러므로 \(\overline{\rm AB}=\overline{\rm AE}+\overline{\rm BE}\)이므로 \(\overline{\rm CF}\)는 \(\overline{\rm AB}\)의 약수이다.
그런데 \(\overline{\rm CF}\)는 \(\overline{\rm CD}\)의 약수이다. 즉, \(\overline{\rm CF}\)는 \(\overline{\rm AB}\), \(\overline{\rm CD}\) 각각의 약수이다. 그러므로 \(\overline{\rm CF}\)는 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 공약수이다.
이제 \(\overline{\rm CF}\)가 가장 큰 수임을 보여야 한다.
\(\overline{\rm CF}\)가 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 최대공약수가 아니라면, \(\overline{\rm CF}\) 보다 큰 수 어떤 수가 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 공약수가 존재한다. 그 수를 \(g\)라 하자.
\(g\)는 \(\overline{\rm CD}\)의 약수이고, \(\overline{\rm CD}\)는 \(\overline{\rm BE}\)의 약수이므로 \(g\) 또한 \(\overline{\rm BE}\)의 약수이다. 그러므로 (*)에 의해서 \(g\) 또한 \(\overline{\rm AE}\)의 약수이다.
그런데 \(\overline{\rm AE}\)는 \(\overline{\rm DF}\)의 약수이다. 그러므로 \(g\)는 또한 \(\overline{\rm DF}\)의 약수이다. 그런데 \(g\)는 \(\overline{\rm CD}\)의 약수이다. 그러므로 \(\overline{\rm CF}=\overline{\rm CD}-\overline{\rm DF}\)이므로 \(g\) 또한 나머지 수 \(\overline{\rm CF}\)의 약수다. 그런데 \(g>\overline{\rm CF}\)인 \(g\)가 \(\overline{\rm CF}\)의 약수이므로 이건 모순이다.
그러므로 \(\overline{\rm CF}\) 보다 큰 수는 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 공약수일 수 없다. 그러므로 \(\overline{\rm CF}\)는 \(\overline{\rm AB}\), \(\overline{\rm CD}\)의 공약수 중 가장 큰 수인 최대공약수이다.
그러므로 서로소가 아닌 두 수에 대하여 이 두 수를 공통으로 나눌 수 있는 최대공약수를 구할 수 있다.
Q.E.D.
어떤 수가 두 수의 공약수라고 하면, 최대공약수는 그 공약수의 약수이다.
유클리드는 이 명제에서 유클리드 호제법을 다시 사용한다. 이번에는 서로소가 아닌 두 수의 최대공약수를 찾는 것이다. 유클리드가 단위(\(1\))을 숫자로 간주했다면 이 두 명제를 하나로 합쳤을 것이다.
두 수 \(m\)과 \(n\)의 최대공약수는 두 수를 나누는 가장 큰 수이다. 일반적으로 \(\gcd(m, n)\)로 표시한다. 그것은 큰 수가 작은 수에 의해서 나누어떨어질 때까지 큰 수를 작은 수로 나누는 것을 반복적으로 할 수 있다.
\(1\)이 아닌 이전 수 \(a_n\), 최종 나머지를 \(a_{n+1}\)인 것을 제외하고 [VII권 명제 1]과 동일하다.
\(a_1-m_1 a_2 = a_3\)
\(a_2-m_2 a_3 = a_4\)
\(\,\,\,\,\,\,\,\vdots\)
\(a_{n-1}-m_{n-1}a_n = a_{n+1}\)
유클리드는 이 명제에서 \(a_1=\overline{\rm AB}\), \(a_2=\overline{\rm CD}\), \(a_3=\overline{\rm AE}\), \(a_4=a_{n+1}=\overline{\rm CF}\)라 놓았다.
이 명제와 따름 명제는 다음 두 명제에서 사용된다.