최대공약수

• 상위 항목: 수학, 수학 관련 정보

Greatest Common Divisor, Highest Common factor

1 개요

초등학교 때 배우는 숫자의 관련된 성질 중 하나. 약수에 대해서 먼저 배운 뒤, 바로 배우게 될 것이다. 먼저 공약수란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 당연히 공약수 중 가장 큰 것. 두 수 $$a,b$$ 의 최대공약수를 수학적 기호로 표시하면, $$\gcd\left(a,b\right)$$ 이며, 더욱 줄여서 $$\left(a,b\right)$$ 로 표기하기도 한다. 특히, $$\gcd\left(a,b\right)=1$$ 이면 두 수 $$a,b$$ 는 서로소(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 성질

두 정수 $$a,b$$ 에 대해서,

1. $$\gcd\left(a,b\right)\geq1$$
2. $$\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right)$$
3. $$\gcd\left(a,0\right)=\left|a\right|$$
4. $$d=\gcd\left(a,b\right)$$ 라 하면, $$\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1$$
5. 임의의 정수 $$k$$ 에 대하여, $$\gcd\left(a,b\right)=\gcd\left(a+kb,b\right)$$
6. 임의의 양의 정수 $$a,b$$ 에 대해서, $$ax+by=\gcd\left(a,b\right)$$ 를 만족하는 정수 $$x,y$$ 가 존재한다.

4 증명

1. $$1\mid a,1\mid b$$ 이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, $$\gcd\left(a,b\right)\geq1$$ .
2. $$x\mid a$$ 와 $$x\mid -a$$ 는 동치이다. 그런데 $$\left|a\right|$$ 는 $$a$$ 또는 $$-a$$ 이므로 $$a$$ 와 $$\left|a\right|$$ 는 같은 약수를 갖는다. 마찬가지로, $$b$$ 와 $$\left|b\right|$$ 는 같은 약수를 갖는다. 따라서, $$x$$ 가 $$a$$ 와 $$b$$ 의 공약수라는 것은 $$\left|a\right|$$ 와 $$\left|b\right|$$ 의 공약수라는 사실과 동치이다. $$\therefore\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right)$$
3. 2번으로 부터, $$\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)$$ 이다. $$\left|a\right|\cdot0=0$$ 이므로, $$\left|a\right|\mid0$$ . 또한, $$\left|a\right|\mid\left|a\right|$$ 이므로, $$\left|a\right|$$ 는 $$\left|a\right|$$ 와 0의 공약수이다. 그러므로 $$\left|a\right|\leq\gcd\left(\left|a\right|,0\right)$$ 이다. 그런데 $$\gcd\left(\left|a\right|,0\right)\mid\left|a\right|$$ 이므로, $$\gcd\left(\left|a\right|,0\right)\leq\left|a\right|$$ . 위 두 부등식으로 부터 $$\gcd\left(\left|a\right|,0\right)=\left|a\right|$$ . 다시 한번 2번으로 부터, $$\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)=\left|a\right|$$ .
4. $$a=dm, b=dn$$ 라 하면, $$\gcd\left(\frac{a}{d},\frac{b}{d}\right)=\gcd\left(m,n\right)$$ 이다. 양의 정수 $$p$$ 가 $$p\mid m,p\mid n$$ 를 만족한다고 하자. 그러면 $$m=pe,n=pf$$ 를 만족하는 정수 $$e,f.$$ 가 존재한다. 따라서, $$a=dpe,b=dpf$$ 이고 $$dp$$ 는 $$a,b$$ 의 공약수이다. 한편, $$d$$ 는 최대공약수이므로, $$d\geq dp$$ . 따라서 $$p\leq1$$ 이고 $$p=1$$ 일 수 밖에 없다. 이로써 보이고자 하는 바가 증명되었다.
5. 만약 $$x$$ 가 $$a,b$$ 의 공약수라면, $$x\mid a,x\mid b$$ 이다. 따라서 $$x\mid kb$$ 이고, $$x\mid a+kb$$ 이다. 따라서 $$x$$ 는 $$a+kb$$ 와 $$b$$ 의 공약수이다.
   역으로, $$x$$ 가 $$a+kb$$ 와 $$b$$ 의 공약수라면, $$x\mid a+kb, x\mid b$$ 이다. 따라서 $$x\mid kb$$ 이고, $$x\mid\left(\left(a+kb\right)-kb\right)=a$$ 이다. 즉, $$x$$ 는 $$a,b$$ 의 공약수이다. 따라서 $$a,b$$ 와 $$a+kb,b$$ 는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다.
6. 집합 $$A=\left\{ax+by\gt0|x,y\in Z\right\}$$ 를 생각하자. 집합 $$A$$ 는 자연수의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 $$d$$ 라 하면 적당한 정수 $$x,y$$ 에 대해 $$d=ax+by$$ 이다. 여기서 $$d$$ 가 최대공약수임을 보이면 증명이 끝난다.
   $$d\gt0$$ 이므로, 나눗셈 정리에 의하여 $$a=qd+r,\,0\leq r\ltd$$ 인 정수 $$q,r$$ 가 존재한다. 그러면 $$r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right)$$ 이므로 $$r\gt0$$ 이면 $$r\in A$$ 이고, $$r\ltd$$ 가 되어 $$d$$ 가 가장 작은 원소라는 사실에 모순된다. 따라서 $$r=0$$ 이고, $$d\mid a$$ 이다. 마찬가지로 $$d\mid b$$ 이다. 즉, $$d\mid\gcd\left(a,b\right)$$ .
   한편 $$e$$ 가 $$a,b$$ 의 공약수라면 $$e\mid\left(ax+by\right)$$ 이고, $$ax+by=d$$ 이므로 $$e\mid d$$ , 즉 $$e\leq d$$ 이다. 이는 곧 $$d$$ 가 최대공약수임을 보인다.

5 관련 항목

• 약수
• 나눗셈 정리
• 유클리드 호제법
• 최소공배수