[include(틀:특수함수의 목록)] [include(틀:정수론)] [목차] == 개요 == {{{+1 Greatest Common Divisor(Factor), GCD · [[最]][[大]][[公]][[約]][[數]]}}} 초등학교 때 배우는 숫자의 관련된 성질 중 하나. [[약수(수학)|약수]] (divisor or factor) 에 대해서 먼저 배운 뒤, 바로 배우게 될 것이다. 먼저 공약수 (common divisor or common factor) 란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 '''공통인 약수'''라는 뜻이다. 최대공약수 (greatest common divisor) 는 당연히 공약수 중 가장 큰 것. 두 수 [math(a,b)]의 최대공약수를 수학적 기호로 표시하면, [math(\gcd\left(a,b\right))]이며,[* gcd는 Greatest Common Divisor, 영어로 최대공약수의 약자이다.] 더욱 줄여서 [math(\left(a,b\right))]로 표기하기도 한다.[* 다만 [math(\left(a,\,b\right))]은 [[구간|개구간]] 표현과 겹치므로 사용에 주의할 필요가 있다.] 특히, [math(\gcd\left(a,b\right)=1)]이면 두 수 [math(a,b)]는 [[서로소]](relatively prime, coprime)라고 한다. 가끔 최'''소'''공약수라고 잘못 부르는 경우가 있는데, 최소공약수는 무조건 1이므로 논할 가치도 없다(...).[* 반대로 최'''대'''공배수도 결국 무한으로 발산하므로 논할 가치 자체가 없다.] == 찾는 법 == 예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다. >12: 1, 2, 3, 4, '''6''', 12 [br] 18: 1, 2, 3, '''6''', 9, 18 여기서 위아랫줄 모두 같이 있는 숫자가 '''공약수'''가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. '''최대공약수'''는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. 하지만 두 수의 약수를 찾는 게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 [[약수(수학)|약수]]를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다.[* 이 점 때문에 [[특수함수]]에 속한다. 참고로 최대공약수/최소공배수는 교과과정상 가장 처음으로 접하는 특수함수이다.] 이 문제를 해결하기 위한 방법이 바로 [[유클리드 호제법]]. 놀랍게도 기원전에 발견된 인류 '''최초의 알고리즘'''이라고 한다. 자세한 것은 [[유클리드 호제법|항목]] 참조. [[최소공배수]] [math(\mathrm{lcm})]를 이용하는 방법도 있다. 최소공배수와 다음과 같은 관계가 성립한다: >[math(\gcd(a,\,b) = \dfrac{|ab|}{\mathrm{lcm}(a,\,b)})] 단, 최대공약수도 최소공배수도 모를 경우 [[순환 논법|순환논법]]이 될 수 있음을 주의해야 한다. 해석적인 방법[* [[복소수]]까지 범위가 확장된다.]으로는 이렇게 된다. >[math(\displaystyle \gcd(x,\,y) = \int_{n|x} \int_{1}^{x} e^{\frac{2}{x}i \pi ty} \frac{c_n(t)}{n}\ \mathrm{d}\lfloor t \rfloor \mathrm{d}\lfloor n \rfloor)] 여기서 [math(c_n(t))]는 [[라마누잔합]] 함수이다. == 성질 == 두 정수 [math(a,b)]에 대해서, 1. [math(\gcd\left(a,b\right)\geq1)] 1. [math(\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right))] 1. [math(\gcd\left(a,0\right)=\left|a\right|)] 1. [math(d=\gcd\left(a,b\right))]라 하면, [math(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1)] 1. 임의의 정수 [math(k)]에 대하여, [math(\gcd\left(a,b\right)=\gcd\left(a+kb,b\right))] 1. 임의의 양의 정수 [math(a,b)]에 대해서, [math(ax+by=\gcd\left(a,b\right))]를 만족하는 정수 [math(x,y)]가 존재한다.[* [[베주 항등식]]이라고 불리는 정리이다. 자세한 증명과 내용은 [[베주 항등식]] 문서에서 볼 수 있다. 만약 a와 b가 [[서로소]]이면, [math(ax+by=1)]를 만족하는 정수 [math(x,y)]가 존재함을 의미한다. 역도 성립한다.] == 증명 == 1. [math(1\mid a,1\mid b)]이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, [math(\gcd\left(a,b\right)\geq1)]. 1. [math(x\mid a)]와 [math(x\mid -a)]는 동치이다. 그런데 [math(\left|a\right|)]는 [math(a)] 또는 [math(-a)]이므로 [math(a)]와 [math(\left|a\right|)]는 같은 [[약수(수학)|약수]]를 갖는다. 마찬가지로, [math(b)]와 [math(\left|b\right|)]는 같은 약수를 갖는다. 따라서, [math(x)]가 [math(a)]와 [math(b)]의 공약수라는 것은 [math(\left|a\right|)]와 [math(\left|b\right|)]의 공약수라는 사실과 동치이다. [math(\therefore\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right))] 1. 2번으로 부터, [math(\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right))]이다. [math(\left|a\right|\cdot0=0)]이므로, [math(\left|a\right|\mid0)]. 또한, [math(\left|a\right|\mid\left|a\right|)]이므로, [math(\left|a\right|)]는 [math(\left|a\right|)]와 0의 공약수이다. 그러므로 [math(\left|a\right|\leq\gcd\left(\left|a\right|,0\right))]이다. 그런데 [math(\gcd\left(\left|a\right|,0\right)\mid\left|a\right|)]이므로, [math(\gcd\left(\left|a\right|,0\right)\leq\left|a\right|)]. 위 두 부등식으로 부터 [math(\gcd\left(\left|a\right|,0\right)=\left|a\right|)]. 다시 한번 2번으로 부터, [math(\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)=\left|a\right|)]. 1. [math(a=dm, b=dn)]라 하면, [math(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=\gcd\left(m,n\right))]이다. 양의 정수 [math(p)]가 [math(p\mid m,p\mid n)]를 만족한다고 하자. 그러면 [math(m=pe,n=pf)]를 만족하는 정수 [math(e,f.)]가 존재한다. 따라서, [math(a=dpe,b=dpf)]이고 [math(dp)]는 [math(a,b)]의 공약수이다. 한편, [math(d)]는 최대공약수이므로, [math(d\geq dp)]. 따라서 [math(p\leq1)]이고 [math(p=1)]일 수밖에 없다. 이로써 보이고자 하는 바가 증명되었다. 1. 만약 [math(x)]가 [math(a,b)]의 공약수라면, [math(x\mid a,x\mid b)]이다. 따라서 [math(x\mid kb)]이고, [math(x\mid a+kb)]이다. 따라서 [math(x)]는 [math(a+kb)]와 [math(b)]의 공약수이다.[br]역으로, [math(x)]가 [math(a+kb)]와 [math(b)]의 공약수라면, [math(x\mid a+kb, x\mid b)]이다. 따라서 [math(x\mid kb)]이고, [math(x\mid\left(\left(a+kb\right)-kb\right)=a)]이다. 즉, [math(x)]는 [math(a,b)]의 공약수이다. 따라서 [math(a,b)]와 [math(a+kb,b)]는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다. 1. 집합 [math(A=\left\{ax+by>0|x,y\in Z\right\})]를 생각하자. 집합 [math(A)]는 [[자연수]]의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 [math(d)]라 하면 적당한 정수 [math(x,y)]에 대해 [math(d=ax+by)]이다. 여기서 [math(d)]가 최대공약수임을 보이면 증명이 끝난다.[br][math(d>0)]이므로, [[나눗셈 정리]]에 의하여 [math(a=qd+r,\,0\leq r<d)]인 정수 [math(q,r)]가 존재한다. 그러면 [math(r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right))]이므로 [math(r>0)]이면 [math(r\in A)]이고, [math(r<d)]가 되어 [math(d)]가 가장 작은 원소라는 사실에 모순된다. 따라서 [math(r=0)]이고, [math(d\mid a)]이다. 마찬가지로 [math(d\mid b)]이다. 즉, [math(d\mid\gcd\left(a,b\right))].[br]한편 [math(e)]가 [math(a,b)]의 공약수라면 [math(e\mid\left(ax+by\right))]이고,[* 5번 성질 참조] [math(ax+by=d)]이므로 [math(e\mid d)], 즉 [math(e\leq d)]이다. 이는 곧 [math(d)]가 최대공약수임을 보인다. == 관련 문서 == * [[약수(수학)|약수]] * [[나눗셈 정리]] * [[유클리드 호제법]] * [[최소공배수]] * [[공약수]] * [[공배수]] [[분류:정수론]][[분류:비초등함수]]