Greatest Common Divisor, Highest Common factor
1 개요
초등학교 때 배우는 숫자의 관련된 성질 중 하나. 약수에 대해서 먼저 배운 뒤, 바로 배우게 될 것이다. 먼저 공약수란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 당연히 공약수 중 가장 큰 것. 두 수 [math]a,b[/math]의 최대공약수를 수학적 기호로 표시하면, [math]\gcd\left(a,b\right)[/math]이며,[1] 더욱 줄여서 [math]\left(a,b\right)[/math]로 표기하기도 한다. 특히, [math]\gcd\left(a,b\right)=1[/math]이면 두 수 [math]a,b[/math]는 서로소(relatively prime, coprime)라고 한다.
가끔 최소공약수라고 잘못 부르는 경우가 있는데, 최소공약수는 무조건 1이므로 논할 가치도 없다. (...)
2 찾는 법
예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다.
12: 1, 2, 3, 4, 6, 12
18: 1, 2, 3, 6, 9, 18
여기서 위아랫줄 모두 같이 있는 숫자가 공약수가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. 최대공약수는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. 참 쉽죠?
하지만 두 수의 약수를 찾는게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 약수를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다. 이 문제를 해결하기 위한 방법이 바로 유클리드 호제법. 놀랍게도 기원전에 발견된 인류 최초의 알고리즘이라고 한다. 자세한 것은 항목 참조.
3 성질
두 정수 [math]a,b[/math]에 대해서,
- [math]\gcd\left(a,b\right)\geq1[/math]
- [math]\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right)[/math]
- [math]\gcd\left(a,0\right)=\left|a\right|[/math]
- [math]d=\gcd\left(a,b\right)[/math]라 하면, [math]\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1[/math]
- 임의의 정수 [math]k[/math]에 대하여, [math]\gcd\left(a,b\right)=\gcd\left(a+kb,b\right)[/math]
- 임의의 양의 정수 [math]a,b[/math]에 대해서, [math]ax+by=\gcd\left(a,b\right)[/math]를 만족하는 정수 [math]x,y[/math]가 존재한다.[2]
4 증명
- [math]1\mid a,1\mid b[/math]이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, [math]\gcd\left(a,b\right)\geq1[/math].
- [math]x\mid a[/math]와 [math]x\mid -a[/math]는 동치이다. 그런데 [math]\left|a\right|[/math]는 [math]a[/math] 또는 [math]-a[/math]이므로 [math]a[/math]와 [math]\left|a\right|[/math]는 같은 약수를 갖는다. 마찬가지로, [math]b[/math]와 [math]\left|b\right|[/math]는 같은 약수를 갖는다. 따라서, [math]x[/math]가 [math]a[/math]와 [math]b[/math]의 공약수라는 것은 [math]\left|a\right|[/math]와 [math]\left|b\right|[/math]의 공약수라는 사실과 동치이다. [math]\therefore\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right)[/math]
- 2번으로 부터, [math]\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)[/math]이다. [math]\left|a\right|\cdot0=0[/math]이므로, [math]\left|a\right|\mid0[/math]. 또한, [math]\left|a\right|\mid\left|a\right|[/math]이므로, [math]\left|a\right|[/math]는 [math]\left|a\right|[/math]와 0의 공약수이다. 그러므로 [math]\left|a\right|\leq\gcd\left(\left|a\right|,0\right)[/math]이다. 그런데 [math]\gcd\left(\left|a\right|,0\right)\mid\left|a\right|[/math]이므로, [math]\gcd\left(\left|a\right|,0\right)\leq\left|a\right|[/math]. 위 두 부등식으로 부터 [math]\gcd\left(\left|a\right|,0\right)=\left|a\right|[/math]. 다시 한번 2번으로 부터, [math]\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)=\left|a\right|[/math].
- [math]a=dm, b=dn[/math]라 하면, [math]\gcd\left(\frac{a}{d},\frac{b}{d}\right)=\gcd\left(m,n\right)[/math]이다. 양의 정수 [math]p[/math]가 [math]p\mid m,p\mid n[/math]를 만족한다고 하자. 그러면 [math]m=pe,n=pf[/math]를 만족하는 정수 [math]e,f.[/math]가 존재한다. 따라서, [math]a=dpe,b=dpf[/math]이고 [math]dp[/math]는 [math]a,b[/math]의 공약수이다. 한편, [math]d[/math]는 최대공약수이므로, [math]d\geq dp[/math]. 따라서 [math]p\leq1[/math]이고 [math]p=1[/math]일 수 밖에 없다. 이로써 보이고자 하는 바가 증명되었다.
- 만약 [math]x[/math]가 [math]a,b[/math]의 공약수라면, [math]x\mid a,x\mid b[/math]이다. 따라서 [math]x\mid kb[/math]이고, [math]x\mid a+kb[/math]이다. 따라서 [math]x[/math]는 [math]a+kb[/math]와 [math]b[/math]의 공약수이다.
역으로, [math]x[/math]가 [math]a+kb[/math]와 [math]b[/math]의 공약수라면, [math]x\mid a+kb, x\mid b[/math]이다. 따라서 [math]x\mid kb[/math]이고, [math]x\mid\left(\left(a+kb\right)-kb\right)=a[/math]이다. 즉, [math]x[/math]는 [math]a,b[/math]의 공약수이다. 따라서 [math]a,b[/math]와 [math]a+kb,b[/math]는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다. - 집합 [math]A=\left\{ax+by\gt0|x,y\in Z\right\}[/math]를 생각하자. 집합 [math]A[/math]는 자연수의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 [math]d[/math]라 하면 적당한 정수 [math]x,y[/math]에 대해 [math]d=ax+by[/math]이다. 여기서 [math]d[/math]가 최대공약수임을 보이면 증명이 끝난다.
[math]d\gt0[/math]이므로, 나눗셈 정리에 의하여 [math]a=qd+r,\,0\leq r\ltd[/math]인 정수 [math]q,r[/math]가 존재한다. 그러면 [math]r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right)[/math]이므로 [math]r\gt0[/math]이면 [math]r\in A[/math]이고, [math]r\ltd[/math]가 되어 [math]d[/math]가 가장 작은 원소라는 사실에 모순된다. 따라서 [math]r=0[/math]이고, [math]d\mid a[/math]이다. 마찬가지로 [math]d\mid b[/math]이다. 즉, [math]d\mid\gcd\left(a,b\right)[/math].
한편 [math]e[/math]가 [math]a,b[/math]의 공약수라면 [math]e\mid\left(ax+by\right)[/math]이고,[3] [math]ax+by=d[/math]이므로 [math]e\mid d[/math], 즉 [math]e\leq d[/math]이다. 이는 곧 [math]d[/math]가 최대공약수임을 보인다.