최대 공약수

수론에서, 정수들의 최대 공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common divisor/factor, 약자 GCD/GCF)는 모든 정수들의 약수가 되는 양의 정수 가운데 가장 큰 하나다. (가장 큰 하나가 없는 경우는 모든 정수가 0인 경우뿐이며, 이 경우 최대 공약수를 0으로 정의한다.) 정수 집합의 약수 관계에 대한 (완비) 원격자에서의 상한이다. 기호는 $\gcd\{m,n\}$ 또는 $(m,n)$.

최대 공약수는 임의의 정수에 대하여 정의된다.^{:14, Theorem 1.2} 일부 문헌에서는 0이 아닌 정수를 하나 이상 포함하는 경우에만 최대 공약수를 정의한다. (이는 최대 공약수가 문자 그대로 가장 큰 공통의 약수가 되는 경우이다.) 일부 문헌에서는 0이 아닌 정수를 요구하며, 다른 일부 문헌에서는 양의 정수를 요구하기도 한다.

다항식이나 가환환의 원소에 대해서도 정의할 수 있다. 정수의 최대 공약수를 음이 아닌 정수로 정하는 것처럼, 다항식의 최대 공약수는 (0 또는) 일계수 다항식으로 정한다. 가환환의 원소의 경우, 추가적인 데이터가 없는 한 최대 공약수를 표준적으로 고르는 방법은 정해져 있지 않다.

정의

정수들의 공약수(公約數, 영어: common divisor/factor)는 동시에 그들 모두의 약수인 정수다. 두 정수 $m,n\in \mathbb {Z}$의 공약수는 $m$의 약수이자 $n$의 약수인 정수이다. 두 정수 $m,n\in \mathbb {Z}$의 최대 공약수는 다음과 같은 여러 정의가 있으며, 이들은 서로 동치이다.^{:14, Theorem 1.2}

• $m\neq 0$이거나 $n\neq 0$인 경우, $m$, $n$의 가장 큰 공약수. $m=n=0$인 경우, 0.
  • 1은 공약수이므로 공약수 집합은 공집합이 아니다. 0이 아닌 정수의 약수 집합은 유한 집합이므로, 0이 아닌 정수를 하나 이상 포함하는 두 정수의 공약수 집합도 유한 집합이다. 따라서, 최대 원소가 존재한다. 두 정수 모두 0인 경우, 공약수 집합은 모든 정수의 집합이므로 최대 원소가 존재하지 않으며, 따라서 별도로 정의한다.
• $m$, $n$의 공약수이며, $m$, $n$의 모든 공약수의 배수인 유일한 음이 아닌 정수
  • $m$, $n$의 공약수이며, $m$, $n$의 모든 공약수의 배수인 정수는 항상 $d,-d$의 꼴로 나타난다. 따라서, 이 가운데 음이 아닌 정수는 유일하다. 이 정의는 임의의 두 정수에 대하여 유효하므로, 경우를 나눌 필요가 없다.
• $m$, $n$의 공약수이며, $m$, $n$의 정수 계수 선형 결합으로 나타낼 수 있는 유일한 음이 아닌 정수
  • 마찬가지로, $m$, $n$의 공약수이며, $m$, $n$의 정수 계수 선형 결합으로 나타낼 수 있는 정수는 $d,-d$의 꼴로 나타나며, 이 가운데 음이 아닌 하나를 고른다. 이 정의는 유클리드 호제법에 의한다. 이 정의는 임의의 두 정수에 대하여 유효하므로, 경우를 나눌 필요가 없다.
• $m\neq 0$이거나 $n\neq 0$인 경우, $m$, $n$의 정수 계수 선형 결합인 최소 양의 정수. $m=n=0$인 경우, 0.
  • 이는 베주 항등식을 통한 정의이다. 두 정수 모두 0인 경우, $m$, $n$의 정수 계수 선형 결합은 0뿐이므로, 별도로 정의한다.

보다 일반적으로, 유한 개의 정수 $n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z}$의 공약수는 모든 $n_{i}$의 배수인 정수이다. 유한 개의 정수 $n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z}$의 최대 공약수 $\gcd\{n_{1},n_{2},\dots ,n_{k}\}$는 다음과 같은 서로 동치인 정의가 있다. 이는 항상 유일하게 존재한다.

• 가장 큰 공약수. (단, $n_{1}=\cdots =n_{k}=0$인 경우 $\gcd\{n_{1},n_{2},\dots ,n_{k}\}=0$.)
• 공약수이며, 모든 공약수의 배수인 유일한 음이 아닌 정수
• 공약수이며, 정수 계수 선형 결합인 유일한 음이 아닌 정수
• 0이 아닌 정수를 포함하는 경우, 정수 계수 선형 결합인 최소 양의 정수. (단, $n_{1}=\cdots =n_{k}=0$인 경우 $\gcd\{n_{1},n_{2},\dots ,n_{k}\}=0$.)
• $\gcd\{\gcd\{\gcd\{\cdots \gcd\{\gcd\{n_{1},n_{2}\},n_{3}\}\cdots \},n_{k-1}\}n_{k}\}$
  • 이 정의는 재귀적이며, 두 정수의 최대 공약수의 정의에 의존한다.

보다 일반적으로, (무한 집합일 수 있는) 임의의 정수 집합 $S\subseteq \mathbb {Z}$의 최대 공약수 $\gcd S$를 정의할 수 있다. 유한 개의 정수에 대한 정의들은 재귀적 정의를 제외하면 무한 개의 정수에 대해서도 (적절한 수정을 거치면) 유효하다. 이 경우, 모든 정수가 0인 경우는 $S=\{0\}$이거나 $S=\varnothing$인 경우에 해당한다.

일부 문헌에서는 최대 공약수의 정의를 적어도 하나 이상의 정수가 0이 아닌 경우로 제한한다. 일부 문헌은 0이 아닌 정수의 경우로 제한한다. 일부 문헌은 양의 정수로 제한한다.

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

성질

약수 관계와의 관계

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

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

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

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

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

이는 격자의 순서론적 구조와 대수적 구조 사이의 관계의 특수한 경우이다.

항등식

임의의 정수들에 대하여, 다음과 같은 항등식들이 성립한다.

• (멱등 법칙) $\gcd\{n,n\}=|n|$
• (교환 법칙) $\gcd\{m,n\}=\gcd\{n,m\}$
• (결합 법칙) $\gcd\{\gcd\{m,n\},k\}=\gcd\{m,\gcd\{n,k\}\}$
• (흡수 법칙) $\operatorname {lcm} \{m,\gcd\{m,n\}\}=m$
• (흡수 법칙) $\gcd\{m,\operatorname {lcm} \{m,n\}\}=m$
• $\gcd\{1,n\}=1$
  • 즉, 1은 격자 $(\mathbb {Z} _{\geq 0},\mid )$의 최소 원소이다.
• $\gcd\{0,n\}=|n|$^{:22, Exercise 21}
  • 즉, 0은 격자 $(\mathbb {Z} _{\geq 0},\mid )$의 최대 원소이다.
  • 이들 항등식에 따라, $(\mathbb {Z} _{\geq 0},\mid )$는 유계 격자를 이룬다.
• (곱에 대한 분배 법칙) $\gcd\{mk,nk\}=\gcd\{m,n\}|k|$
  • 특히, $m\neq 0$이거나 $n\neq 0$인 경우

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

• $\gcd\{m,n\}\operatorname {lcm} \{m,n\}=|mn|$
• (최소 공배수에 대한 분배 법칙) $\operatorname {lcm} \{m,\gcd\{n,k\}\}=\gcd\{\operatorname {lcm} \{m,n\},\operatorname {lcm} \{m,k\}\}$
• (최소 공배수에 대한 분배 법칙) $\gcd\{m,\operatorname {lcm} \{n,k\}\}=\operatorname {lcm} \{\gcd\{m,n\},\gcd\{m,k\}\}$
  • 이 두 항등식에 따라, $(\mathbb {Z} _{\geq 0},\mid )$는 분배 격자이다.
• $a\neq 0$이거나 $b\neq 0$이며, 또한 $m\neq 0$이거나 $n\neq 0$인 경우,

  $\gcd\{am,bn\}=\gcd\{a,b\}\gcd\{m,n\}\gcd \left\{{\frac {a}{\gcd\{a,b\}}},{\frac {n}{\gcd\{m,n\}}}\right\}\gcd \left\{{\frac {b}{\gcd\{a,b\}}},{\frac {m}{\gcd\{m,n\}}}\right\}$

  • 특히, $\gcd\{a,b\}=\gcd\{m,n\}=1$인 경우

    $\gcd\{am,bn\}=\gcd\{a,n\}\gcd\{b,m\}$

• $\gcd\{m,n\}=1$인 경우,

  $\gcd\{mn,k\}=\gcd\{m,k\}\gcd\{n,k\}$

  • 즉, $\gcd\{-,k\}$는 곱셈적 함수다. 반면, $\operatorname {lcm} \{-,k\}$는 곱셈적 함수가 아니다.

소인수 분해와의 관계

소인수분해가 주어진 양의 정수들의 최대 공약수는 소인수의 최소 지수를 취하여 얻어진다. 두 정수의 경우, 두 양의 정수의 소인수분해가 다음과 같다고 하자.

$m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$

$n=p_{1}^{f_{1}}p_{2}^{f_{2}}\cdots p_{k}^{f_{k}}$

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

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

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

계산

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

소인수분해

 이 부분의 본문은 소인수분해입니다.

두 수 192와 72의 최대 공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.

$192=2^{6}\times 3=2\times 2\times 2\times 2\times 2\times 2\times 3$

$72=2^{3}\times 3^{2}=2\times 2\times 2\times 3\times 3$

구하고 나면, 두 소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉 $2\times 2\times 2\times 3=24$ 최대 공약수가 24라는 결론이 나온다.

그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.

유클리드 호제법

 이 부분의 본문은 유클리드 호제법입니다.

똑같이 두 수 192와 72의 최대 공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.

$192=72\times 2+48$

이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.

$72=48\times 1+24$

이와 같은 연산을 나머지가 0이 될 때까지 반복한다.

$48=24\times 2+0$

나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대 공약수가 된다.

이를 수식화 한 것은 호제법 문서를 참조하라.

예

임의의 양의 정수 $a,m,n\in \mathbb {Z} ^{+}$에 대하여,

$\gcd\{a^{m}-1,a^{n}-1\}=a^{\gcd\{m,n\}}-1$

이다.

관련 개념

임의의 환 위에서 최대 공약수를 정의할 수 있다. 가환 환에서 두 원소 $a$와 $b$에 대하여 $d$가 최대 공약수라 함은 $d$가 두 원소의 약수이며 동시에 임의의 공약수는 $d$의 약수가 됨을 말한다. 그러나 이렇게 정의할 경우 최대 공약수는 유일하지 않을 수도 있고 두 원소가 영이아니라 하더라도 존재하지 않을 수도 있다. 정역에서는 일단 존재한다면 최대 공약수들은 서로 동반된(associated)다. 또한 유일 인수분해정역에서는 영이 아닌 두 원소의 경우 항상 최대 공약수가 존재한다.

같이 보기

• 최소 공배수

외부 링크

• 서보억 (2011년 10월 10일). “최대 공약수”. 《네이버캐스트》. 2018년 5월 10일에 확인함.