최대공약수

1. 개요2. 찾는 법3. 성질4. 증명5. 관련 문서

1. 개요 [편집]

Greatest Common Divisor(Factor), GCD · 最大公約數

초등학교 때 배우는 숫자의 관련된 성질 중 하나. 약수 (divisor or factor) 에 대해서 먼저 배운 뒤, 바로 배우게 될 것이다. 먼저 공약수 (common divisor or common factor) 란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수 (greatest common divisor) 는 당연히 공약수 중 가장 큰 것. 두 수

a,b

의 최대공약수를 수학적 기호로 표시하면,

\gcd\left(a,b\right)

이며,[1] 더욱 줄여서

\left(a,b\right)

로 표기하기도 한다.[2] 특히,

\gcd\left(a,b\right)=1

이면 두 수

a,b

는 서로소(relatively prime, coprime)라고 한다.

가끔 최소공약수라고 잘못 부르는 경우가 있는데, 최소공약수는 무조건 1이므로 논할 가치도 없다(...).[3]

2. 찾는 법 [편집]

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

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

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

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

최소공배수

\mathrm{lcm}

를 이용하는 방법도 있다. 최소공배수와 다음과 같은 관계가 성립한다:

$\gcd(a,\,b) = \dfrac{|ab|}{\mathrm{lcm}(a,\,b)}$

단, 최대공약수도 최소공배수도 모를 경우 순환논법이 될 수 있음을 주의해야 한다.

해석적인 방법[5]으로는 이렇게 된다.

$\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$

여기서

c_n(t)

는 라마누잔합 함수이다.

3. 성질 [편집]

두 정수

a,b

에 대해서,

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

4. 증명 [편집]

$1\mid a,1\mid b$ 이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, $\gcd\left(a,b\right)\geq1$ .
$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)$
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|$ .
$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$ 일 수밖에 없다. 이로써 보이고자 하는 바가 증명되었다.
만약 $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$ 는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다.
집합 $A=\left\{ax+by>0|x,y\in Z\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)$ 이고,[7] $ax+by=d$ 이므로 $e\mid d$ , 즉 $e\leq d$ 이다. 이는 곧 $d$ 가 최대공약수임을 보인다.

5. 관련 문서 [편집]

[1] gcd는 Greatest Common Divisor, 영어로 최대공약수의 약자이다.[2] 다만

\left(a,\,b\right)

은 개구간 표현과 겹치므로 사용에 주의할 필요가 있다.[3] 반대로 최대공배수도 결국 무한으로 발산하므로 논할 가치 자체가 없다.[4] 이 점 때문에 특수함수에 속한다. 참고로 최대공약수/최소공배수는 교과과정상 가장 처음으로 접하는 특수함수이다.[5] 복소수까지 범위가 확장된다.[6] 베주 항등식이라고 불리는 정리이다. 자세한 증명과 내용은 베주 항등식 문서에서 볼 수 있다. 만약 a와 b가 서로소이면,

ax+by=1

를 만족하는 정수

x,y

가 존재함을 의미한다. 역도 성립한다.[7] 5번 성질 참조