최대 공약수

최대 공약수(最大公約數, 영어: greatest common divisor, GCD)는 두 개 이상의 정수의 공통된 약수 중에서 가장 큰 양의 정수이다. 약수(divisor)는 어떤 정수를 나누어떨어지게 하는 수를 의미하며, 공약수(common divisor)는 여러 정수의 공통된 약수를 말한다.

정의

정수 $a$에 대하여 $a$를 나누어떨어지게 하는 정수 $d$를 $a$의 약수라고 한다. 두 개 이상의 정수 $a_1, a_2, \dots, a_n$ 각각의 약수들 중에서 공통되는 약수를 이 수들의 공약수라고 한다. 이 공약수들 중에서 가장 큰 양의 정수를 이 수들의 최대 공약수라고 한다.

예를 들어, 12의 약수는 ${\displaystyle {\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12}}$ 이고, 18의 약수는 ${\displaystyle {\pm 1, \pm 2, \pm 3, \pm 6, \pm 9, \pm 18}}$ 이다. 12와 18의 공약수는 ${\displaystyle {\pm 1, \pm 2, \pm 3, \pm 6}}$ 이며, 이 중 가장 큰 양의 정수는 6이다. 따라서 12와 18의 최대 공약수는 6이다.

최대 공약수는 ${\displaystyle \operatorname {gcd} (a,b)}$, ${\displaystyle \mathrm {GCD} (a,b)}$, 또는 단순히 정수론에서 $(a,b)$와 같이 표기한다.

구하는 방법

최대 공약수를 구하는 대표적인 방법은 다음과 같다.

공약수 나열 각 수의 모든 약수를 구하여 공통된 약수를 찾고 그중 가장 큰 수를 선택한다. 작은 수에서는 유용하나 수가 커지면 비효율적이다.
소인수 분해 각 수를 소인수 분해한 후, 공통된 소인수들의 최저 차수를 곱한다. 예: 12와 18의 최대 공약수 12 = ${\displaystyle 2^2 \times 3^1}$ 18 = ${\displaystyle 2^1 \times 3^2}$ 공통된 소인수는 2와 3이다. 2의 최저 차수는 1 ($2^1$), 3의 최저 차수는 1 ($3^1$)이다. 따라서 최대 공약수는 ${\displaystyle 2^1 \times 3^1 = 6}$ 이다.
유클리드 호제법 두 정수 $a, b$ ($a > b$)에 대해 $a$를 $b$로 나눈 나머지를 $r$이라 할 때, $\operatorname{gcd}(a,b) = \operatorname{gcd}(b,r)$이 성립한다는 성질을 이용한다. 나머지가 0이 될 때까지 나눗셈을 반복하며, 마지막으로 0이 아닌 나머지가 두 수의 최대 공약수이다. 이는 가장 효율적인 방법으로 알려져 있다. 예: 1071과 1029의 최대 공약수 ${\displaystyle \operatorname {gcd}(1071, 1029)}$ 1071을 1029로 나눈 나머지: $1071 = 1029 \times 1 + 42$. $\operatorname{gcd}(1071, 1029) = \operatorname{gcd}(1029, 42)$ 1029를 42로 나눈 나머지: $1029 = 42 \times 24 + 21$. $\operatorname{gcd}(1029, 42) = \operatorname{gcd}(42, 21)$ 42를 21로 나눈 나머지: $42 = 21 \times 2 + 0$. 나머지가 0이 되었으므로, 마지막 0이 아닌 나머지인 21이 최대 공약수이다. 따라서 $\operatorname{gcd}(1071, 1029) = 21$ 이다.

세 개 이상의 정수에 대한 최대 공약수는 두 수씩 차례로 구하면 된다. 예를 들어 $\operatorname{gcd}(a,b,c) = \operatorname{gcd}(\operatorname{gcd}(a,b), c)$ 와 같이 계산한다.

성질

최대 공약수는 공약수들의 배수이다. 즉, 어떤 수가 $a$와 $b$의 공약수이면, 그 수는 $\operatorname{gcd}(a,b)$의 약수이다.
두 수의 곱은 최대 공약수와 최소 공배수의 곱과 같다: ${\displaystyle |ab| = \operatorname{gcd}(a,b) \cdot \operatorname{lcm}(a,b)}$ (단, ${\displaystyle \operatorname {lcm}}$은 최소 공배수).
만약 $d = \operatorname{gcd}(a,b)$이면, ${\displaystyle a = da'}$ 이고 ${\displaystyle b = db'}$ 인 정수 $a', b'$이 존재하며, 이때 $a'$와 $b'$는 서로소, 즉 $\operatorname{gcd}(a',b') = 1$ 이다.
임의의 정수 $k$에 대해 $\operatorname{gcd}(ka, kb) = |k| \operatorname{gcd}(a,b)$ 이 성립한다.
${\displaystyle \operatorname{gcd}(a, \operatorname{gcd}(b,c)) = \operatorname{gcd}(\operatorname{gcd}(a,b), c)}$ (결합 법칙).
${\displaystyle \operatorname{gcd}(a, b) = \operatorname{gcd}(b, a)}$ (교환 법칙).
${\displaystyle \operatorname{gcd}(a, 0) = |a|}$ (단, $a \neq 0$).

응용

분수 약분 분수의 분자와 분모의 최대 공약수로 각각 나누면 기약분수(더 이상 약분되지 않는 분수)를 얻을 수 있다. 예: ${\displaystyle \frac{12}{18}}$. $\operatorname{gcd}(12, 18) = 6$ 이므로 ${\displaystyle \frac{12 \div 6}{18 \div 6} = \frac{2}{3}}$ 로 약분한다.
최소 공배수 계산 두 수의 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 값이다.
정수론 선형 디오판토스 방정식 $ax + by = c$ 가 정수해를 가질 조건은 $c$가 $\operatorname{gcd}(a,b)$의 배수일 때이다.

📖 WIPIVERSE

최대 공약수

정의

구하는 방법

성질

응용

관련 개념