최대공약수

수론에서, 정수들의 공약수(公約數, 영어: common factor)는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common factor, 약자 GCF)는 공약수 가운데 가장 큰 하나다. 다항식이나 환의 원소에 대해서도 정의할 수 있다.

정의

두 정수 $n,m\in \mathbb {Z}$ 의 공약수는 $n$ 의 약수이자 $m$ 의 약수인 정수이다. 모두 0이 아닌 두 정수 $n,m\in \mathbb {Z}$ 의 최대공약수는 다음과 같은 여러 정의가 있으며, 이들은 서로 동치이다.

$n$ , $m$ 의 가장 큰 공약수
$n$ , $m$ 의 공약수이자, $n$ , $m$ 의 모든 공약수의 배수인 양의 정수
$n$ , $m$ 의 정수 계수 선형 결합인 최소 양의 정수

모두 0이지는 않은 두 정수의 최대공약수는 항상 존재하며, 항상 유일하다. 기호는 $\gcd\{n,m\}$ 또는 $(n,m)$ .

비슷하게, 여러 정수 $n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z}$ 의 공약수는 공통 약수이며, 모두 0이지는 않은 여러 정수 $n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z}$ 의 최대공약수 $\gcd\{n_{1},n_{2},\dots ,n_{k}\}$ 는 다음과 같은 서로 동치인 정의가 있다. 이는 항상 유일하게 존재한다.

가장 큰 공약수
공약수이자, 모든 공약수의 배수인 양의 정수
정수 계수 선형 결합인 최소 양의 정수
(재귀적 정의) $\gcd\{\gcd\{\gcd\{\cdots \gcd\{\gcd\{n_{1},n_{2}\},n_{3}\}\cdots \},n_{k-1}\}n_{k}\}$

최대공약수가 1인 정수들을 서로소라고 한다.

성질

최대공약수는 다음과 같은 성질들을 가진다. (여기서 최대공약수를 취하는 정수들은 적어도 하나가 0이 아니라고 가정한다.)

약수 관계는 최대공약수를 통해 다음과 같이 나타낼 수 있다.

n\mid m\iff \gcd\{n,m\}=n

공약수는 최대공약수의 약수와 동치이다.

k\mid n,m\iff k\mid \gcd\{n,m\}

k\mid n_{1},n_{2},\dots ,n_{t}\iff k\mid \gcd\{n_{1},n_{2},\dots ,n_{t}\}

최대공약수는 정수 계수 선형 결합으로 나타낼 수 있는 최소 양의 정수이다.

\gcd\{n,m\}=\min\{an+bm>0\colon a,b\in \mathbb {Z} \}

\gcd\{n_{1},n_{2},\dots ,n_{t}\}=\min\{a_{1}n_{1}+a_{2}n_{2}+\cdots +a_{t}n_{t}>0\colon a_{1},a_{2},\dots ,a_{t}\in \mathbb {Z} \}

최대공약수는 음이 아닌 정수 $k$ 에 대하여 다음과 같다.

\gcd\{nk,mk\}=\gcd\{n,m\}k

\gcd\{n_{1}k,n_{2}k,\dots ,n_{t}k\}=\gcd\{n_{1},n_{2},\dots ,n_{k}\}k

\gcd \left\{{\frac {n}{k}},{\frac {m}{k}}\right\}={\frac {\gcd\{n,m\}}{k}}\qquad (k\mid n,m)

\gcd \left\{{\frac {n_{1}}{k}},{\frac {n_{2}}{k}},\dots ,{\frac {n_{t}}{k}}\right\}={\frac {\gcd\{n_{1},n_{2},\dots ,n_{t}\}}{k}}\qquad (k\mid n_{1},n_{2},\dots ,n_{t})

특히, 정수들을 최대공약수로 나눈 몫들은 서로소다.

\gcd \left\{{\frac {n}{\gcd\{n,m\}}},{\frac {m}{\gcd\{n,m\}}}\right\}=1

\gcd \left\{{\frac {n_{1}}{\gcd\{n_{1},n_{2},\dots ,n_{t}\}}},{\frac {n_{2}}{\gcd\{n_{1},n_{2},\dots ,n_{t}\}}},\dots ,{\frac {n_{t}}{\gcd\{n_{1},n_{2},\dots ,n_{t}\}}}\right\}=1

정수들 가운데 하나에서 다른 하나와 서로소인 약수를 지워도 최대공약수가 변하지 않는다.

\gcd\{m,k\}=1\implies \gcd\{nm,k\}=\gcd\{n,k\}

\gcd\{m,k\}=1\implies \gcd\{n_{1},\dots ,n_{j}m,\dots ,n_{t},k\}=\gcd\{n_{1},\dots ,n_{t},k\}

소인수분해가 주어진 정수들의 최대공약수는 공통된 소인수의 최소 지수 거듭제곱의 곱이다. 두 정수의 경우 소인수분해가 다음과 같다고 하자.

n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{t}^{e_{t}}

m=p_{1}^{f_{1}}p_{2}^{f_{2}}\cdots p_{t}^{f_{t}}

e_{1},e_{2},\dots ,e_{t},f_{1},f_{2},\dots ,f_{t}\in \mathbb {Z} _{\geq 0}

그렇다면, 최대공약수는 다음과 같다.

\gcd\{n,m\}=p_{1}^{\min\{e_{1},f_{1}\}}p_{2}^{\min\{e_{2},f_{2}\}}\cdots p_{t}^{\min\{e_{t},f_{t}\}}

두 정수의 최대공약수와 최소공배수의 관계는 다음과 같다.

\gcd\{n,m\}\operatorname {lcm} \{n,m\}=nm

계산

최대공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 12와 18의 경우, 12의 모든 약수는 (±) 1, 2, 3, 4, 6, 12이며, 18의 모든 약수는 (±) 1, 2, 3, 6, 9, 18이므로, 공약수는 (±) 1, 2, 3, 6이다. 가장 큰 6이 바로 최대공약수이다. 최대공약수를 구하는 방법은 그 밖에 소인수분해를 통한 방법과 유클리드 호제법을 통한 방법이 있다.