최대공약수

최대공약수(greatest common divisor, GCD 또는 gcd)는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, ${\mathbb {Q} }[x]$에서 정의하기도 한다. 기호로는 $\gcd \left(a,b\right)$로 표시하며, 더욱 줄이면 $\left(a,b\right)$로만 표시하는 경우도 있다.

정의

최대공약수는 다음과 같이 정의된다.

$\gcd \left(a,b\right)=\left(a,b\right):=\max\{d:\;d\in {\mathbb {N}},\;d|a{\text{ and }}d|b\}$

정의에 따라 $d=\gcd \left(a,b\right)$는

• $d\geq 1,d|a,d|b$
• $k|a,\;k|b\Leftrightarrow k|d$

를 만족한다.

찾는 법

예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다.

12: 1, 2, 3, 4, 6, 12 18: 1, 2, 3, 6, 9, 18

여기서 위아랫줄 모두 같이 있는 숫자가 공약수가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. 최대공약수는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. 참 쉽죠?

하지만 두 수의 약수를 찾는 게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 약수를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다. 이 문제를 해결하기 위한 방법이 바로 유클리드 호제법. 놀랍게도 기원전에 발견된 인류 최초의 알고리즘이라고 한다. 자세한 것은 유클리드 호제법의 활용 참조.

성질

1. 최대공약수는 유일하다

2. $\gcd \left(a,b\right)\geq 1$

3. $\gcd \left(a,b\right)=\gcd \left(\left|a\right|,\left|b\right|\right)$

4. $\gcd \left(a,0\right)=\left|a\right|$

5. $d=\gcd \left(a,b\right)$라 하면, $\gcd \left({\frac {a}{d}},{\frac {b}{d}}\right)=1$

6. 임의의 정수 $k$에 대하여, $\gcd \left(a,b\right)=\gcd \left(a+kb,b\right)$

7. 정수 $a,b$에 대하여 $ax+by=\gcd \left(a,b\right)$를 만족하는 정수 $x,y$가 존재한다. 또한 $x,y$가 임의의 정수일 때 $\gcd \left(a,b\right)|ax+by$이다.

증명

2. $1\mid a,1\mid b$이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, $\gcd \left(a,b\right)\geq 1$.

3. $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)$

4. 3번으로 부터, $\gcd \left(a,0\right)=\gcd \left(\left|a\right|,0\right)$이다. $\left|a\right|\cdot 0=0$이므로, $\left|a\right|\mid 0$. 또한, $\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|$.

5. $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\leq 1$이고 $p=1$일 수밖에 없다. 이로써 보이고자 하는 바가 증명되었다.

6. 만약 $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$는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다.

7. 집합 $A=\left\{ax+by|x,y\in \right.$ℤ, $\left.ax+by>0\right\}$를 생각하자. 집합 $A$는 자연수의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 $d$라 하면 적당한 정수 $x,y$에 대해 $d=ax+by$이다. 여기서 $d$가 최대공약수임을 보이면 증명이 끝난다. $d>0$이므로, 나눗셈 정리에 의하여 $a=qd+r,\,0\leq r<d$인 정수 $q,r$가 존재한다. 그러면 $r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right)$이므로 $r>0$이면 $r\in A$이고, $r<d$가 되어 $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$가 최대공약수임을 보인다.

관련 항목

• 약수
• 나눗셈 정리
• 최소공배수