VII 권
명제
명제 3
서로소가 아닌 세 수에 대하여 이 세 수의 최대공약수를 구할 수 있다.
서로소가 아닌 세 수 \(a\), \(b\), \(c\)에 대하여, 세 수 \(a\), \(b\), \(c\)의 최대공약수를 구할 수 있다.
VII 권
명제
서로소가 아닌 세 수에 대하여 이 세 수의 최대공약수를 구할 수 있다.
서로소가 아닌 세 수 \(a\), \(b\), \(c\)에 대하여, 세 수 \(a\), \(b\), \(c\)의 최대공약수를 구할 수 있다.
주어진 세 수 \(a\), \(b\), \(c\)는 서로소가 아니다.
그러면 세 수 \(a\), \(b\), \(c\)의 공약수 중 가장 큰 수 즉, 최대공약수를 구하여야 한다.
두 수 \(a\), \(b\)의 최대공약수를 d라고 하자. [VII권 명제 2] 그러면 \(d\)는 \(c\)에 약수이거나 약수가 아니다.
1) \(d\)가 \(c\)의 약수라 하자.
\(d\)는 \(a\), \(b\)의 공약수(최대공약수)이다. 그러므로 \(d\)는 \(a\), \(b\), c의 공약수이다.
\(a\), \(b\), \(c\)의 공약수 수 중 \(d\)가 가장 큰 수(최대공약수)임 보여야 한다.
\(d\)가 최대공약수가 아니라고 가정하자. 그러면 \(d\) 보다 더 큰 어떤 수가 \(a\), \(b\), \(c\)의 공약수라 하자. 그 수를 \(e\) 라고 하자.
e는 \(a\), \(b\), \(c\)의 공약수이다. 그러므로 \(e\)는 \(a\), \(b\)의 최대공약수의 약수이다. [VII권 명제 2 따름 명제] 그런데 \(a\), \(b\)의 최대공약수가 \(d\)이므로 \(e\)는 \(d\)의 약수이다. 그런데 \(e>d\)인 \(e\)가 \(d\)의 약수인 것은 모순이다. 그러므로 \(d\) 보다 더 큰 수는 \(a\), \(b\), \(c\)의 약수일 수 없다. 따라서 \(d\)는 \(a\), \(b\), \(c\)의 약수 중 가장 큰 수로, 최대공약수이다.
2) \(d\)는 \(c\)의 약수가 아니라고 하자.
이 경우에는 \(c\), \(d\)가 서로소가 아님을 먼저 보여야 한다.
\(a\), \(b\), \(c\)가 서로소가 아니기 때문에 이 세 수의 어떤 공약수가 존재한다.
\(a\), \(b\), \(c\)의 어떤 공약수는 \(a\), \(b\)의 공약수이며, \(a\), \(b\)의 최대공약수 \(d\)의 약수이다. [VII권 명제 2 따름 명제] 그런데 이 어떤 공약수는 \(c\)의 약수이기도 하다. 그러므로 \(c\), \(d\)는 서로소가 아니다.
이들의 최대공약수를 \(e\)라 하자. [VII권 명제 2]
\(e\)는 \(d\)의 약수이고, \(d\)는 \(a\), \(b\)의 공약수이므로 \(e\)는 \(a\), \(b\)의 약수이다. 그런데 \(d\)는 \(c\)의 약수이다. 그러므로 \(e\)는 \(a\), \(b\), \(c\)의 각각에 대해 약수이다. 그러므로 \(e\)는 \(a\), \(b\), \(c\)의 공약수이다.
\(e\)가 \(a\), \(b\), \(c\)의 공약수 중 가장 큰 수(최대공약수)임을 보여야 한다.
\(e\)가 \(a\), \(b\), \(c\)의 최대공약수가 아니라고 하자. 그러면 \(e\) 보다 큰 \(a\), \(b\), \(c\)의 공약수가 존재한다. 그 수를 \(f\)라 하자.
\(f\)는 \(a\), \(b\), \(c\)의 약수이므로 \(f\)는 \(a\), \(b\)의 공약수이다. 그러므로 \(f\)는 \(a\), \(b\)의 최대공약수의 약수이다. [VII권 명제 2 따름 명제] 그런데 \(a\), \(b\)의 최대공약수는 \(d\)이므로 \(f\)는 \(d\)의 약수이다.
그리고 \(f\)는 \(c\)의 약수이다. 따라서 \(f\)는 \(c\), \(d\)의 약수이다. 그러므로 \(f\)는 \(c\), \(d\)의 최대공약수의 약수이다. \(c\), \(d\)의 최대공약수는 \(e\)이다. 그러므로 \(f\)는 \(e\)의 약수이다. 그런데 \(f>e\)이므로 f가 \(e\)의 약수인 것은 모순이다.
그러므로 \(e\) 보다 큰 \(a\), \(b\), \(c\)의 공약수는 존재하지 않는다. 그러므로 \(a\), \(b\), \(c\)의 최대공약수는 \(e\)이다.
그러므로 서로소가 아닌 세 수에 대하여 이 세 수의 최대공약수를 구할 수 있다.
Q.E.D.
현대적인 기법으로 증명을 하여 보자.
두 숫자 \(a\)와 \(b\)의 최대 공약수에 대한 일반적인 현대 표기법 은 \(\gcd\left(a,\, b\right)\)이다. 또한 표기법 \(a|b\) 는 \(b\)가 \(a\)에 의하여 나누어떨어진다는 의미로 사용한다.
이 명제는 \(\gcd\left(a,\, b,\, c\right)\)를 \(\gcd\left(\gcd\left(a,\, b\right), \,c\right)\)로 구하였다.
\(d=\gcd\left(a,\,b\right)\), \(e=\gcd\left(d,\,c\right)\)라 하자. \(e|d\), \(d|a\), \(d|b\)이므로 \(e|a\), \(e|b\)이다. 그리고 \(e\)는 \(a\), \(b\), \(c\)의 공약수이다.
\(e\)가 공약수 중 최댓값임을 보이기 위해서 \(f\)를 \(a\), \(b\), \(c\)의 임의의 공약수라고 하자. 그러면 \(f|a\), \(f|b\)이므로 \(f|\gcd\left(a,\,b\right)\) 즉 \(f|d\)이다. \(f|d\), \(f|c\)이므로 \(f|\gcd\left(c,\,d\right)\) 즉, \(f|e\)이다. 그러므로 \(e=\gcd\left(a,\,b,\,c\right)\)이다.
이것은 [X권 명제 4]와 같은 명제이다. 이 명제는 [VII권 명제 33]에서 사용된다.