최소 공배수

수론에서, 여러 개의 정수의 최소 공배수(最小公倍數, 영어: least/lowest common multiple, 약자 lcm)는 그들 모두의 배수가 되는 음이 아닌 정수 가운데 가장 큰 하나이다. 정수 집합의 약수 관계에 대한 원격자에서의 상한이다. 기호는 $\operatorname {lcm} \{m,n\}$ 또는 $[m,n]$ .

최소 공배수는 모든 정수에 대해서 정의된다.^[1]^{:22, Exercise 21} 일부 문헌에서는 최소 공배수의 정의를 0이 아닌 정수 또는 양의 정수 따위로 제한한다.

최소 공배수 값을 음이 아닌 정수로 정하는 것은 일종의 표준화 작업이다. 체 계수 다항식의 최소 공배수도 정의할 수 있으며, 흔히 최소 공배수 값을 (0 또는) 일계수 다항식으로 정한다. 가환환의 원소에 대해서도 정의할 수 있는데, 추가적인 데이터가 없는 한 최소 공배수 값을 표준적으로 선택하는 방법은 정해져 있지 않다.

정의

두 정수 $m,n\in \mathbb {Z}$ 의 공배수(영어: common multiple)는 $m$ 의 배수이자 $n$ 의 배수인 정수이다. 두 정수 $m,n\in \mathbb {Z}$ 의 최소 공배수 $\operatorname {lcm} \{m,n\}$ 는 다음과 같이 정의할 수 있으며, 이들 정의는 서로 동치이다.^[1]^{:22, Exercise 21}

$m$ , $n$ 의 공배수인 음이 아닌 정수 가운데 가장 작은 하나
$m$ , $n$ 의 공배수이며, $m$ , $n$ 의 모든 공배수의 약수인 유일한 음이 아닌 정수

유한 개의 정수 $n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z}$ 의 최소 공배수 $\operatorname {lcm} \{n_{1},n_{2},\dots ,n_{k}\}$ 는 다음과 같이 정의할 수 있으며, 이들 정의는 서로 동치이다.

가장 작은 음이 아닌 공배수
공배수이며, 모든 공배수의 약수인 유일한 음이 아닌 정수
(재귀적 정의) $\operatorname {lcm} \{\operatorname {lcm} \{n_{1},n_{2},\dots ,n_{k-1}\},n_{k}\}$

마찬가지로, 임의의 정수 집합 $S\subseteq \mathbb {Z}$ 의 최소 공배수 $\operatorname {lcm} S$ 를 정의할 수 있다. 일부 문헌의 경우, 0이 아닌 정수들에 대해서만 최대 공배수를 정의한다. 일부 문헌의 경우, 양의 정수에 대해서만 정의한다.

성질

약수 관계와의 관계

공배수는 최소 공배수의 배수와 동치이다.

m,n\mid a\iff \operatorname {lcm} \{m,n\}\mid a

n_{1},\dots ,n_{k}\mid a\iff \operatorname {lcm} \{n_{1},\dots ,n_{k}\}\mid a

약수 관계는 최소 공배수를 통해 다음과 같이 기술할 수 있다.

m\mid n\iff \operatorname {lcm} \{m,n\}=|n|

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

항등식

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

(멱등 법칙) $\operatorname {lcm} \{n,n\}=|n|$
(교환 법칙) $\operatorname {lcm} \{m,n\}=\operatorname {lcm} \{n,m\}$
(결합 법칙) $\operatorname {lcm} \{\operatorname {lcm} \{m,n\},k\}=\operatorname {lcm} \{m,\operatorname {lcm} \{n,k\}\}$
(흡수 법칙) $\operatorname {lcm} \{m,\operatorname {lcm} \{m,n\}\}=m$
(흡수 법칙) $\operatorname {lcm} \{m,\operatorname {lcm} \{m,n\}\}=m$
$\operatorname {lcm} \{1,n\}=|n|$ $\operatorname {lcm} \{1,n\}=|n|$
- 즉, 1은 격자 $(\mathbb {Z} _{\geq 0},\mid )$ 의 최소 원소이다.
$\operatorname {lcm} \{0,n\}=0$ $\operatorname {lcm} \{0,n\}=0$ ^[1]^{:22, Exercise 21}
- 즉, 0은 격자 $(\mathbb {Z} _{\geq 0},\mid )$ 의 최대 원소이다.
- 이들 항등식에 따라, $(\mathbb {Z} _{\geq 0},\mid )$ 는 유계 격자를 이룬다.
(곱에 대한 분배 법칙) $\operatorname {lcm} \{mk,nk\}=\operatorname {lcm} \{m,n\}|k|$
$\gcd\{m,n\}\operatorname {lcm} \{m,n\}=|mn|$ $\gcd\{m,n\}\operatorname {lcm} \{m,n\}=|mn|$
- 특히, 적어도 하나가 0이 아닌 두 정수의 최소 공배수는 최대 공약수를 통해 다음과 같이 나타낼 수 있다.
  $\operatorname {lcm} \{m,n\}={\frac {|mn|}{\gcd\{m,n\}}}$
- 특히, 두 서로소 정수 $\gcd\{m,n\}=1$ 의 최소 공배수는 다음과 같다.
  $\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\}\}$ $\gcd\{m,\operatorname {lcm} \{n,k\}\}=\operatorname {lcm} \{\gcd\{m,n\},\gcd\{m,k\}\}$
- 이 두 항등식에 따라, 격자 $(\mathbb {Z} _{\geq 0},\mid )$ 는 분배 격자이다.

소인수 분해와의 관계

소인수분해가 주어진 양의 정수들의 최소 공배수는 소인수의 지수의 최댓값을 취하여 얻는다. 두 정수의 경우, 소인수분해가

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_{i},f_{i}\in \mathbb {Z} _{\geq 0}

라면, 최소 공배수는

\operatorname {lcm} \{m,n\}=p_{1}^{\max\{e_{1},f_{1}\}}p_{2}^{\max\{e_{2},f_{2}\}}\cdots p_{k}^{\max\{e_{k},f_{k}\}}

이다.

계산법

두 수 a와 b의 최소 공배수를 구하는 방법은 소인수 분해를 사용하는 방법이 있다.

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

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

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

구하고 나면, 두 소인수 분해 결과의 한 소인수 중에서 지수가 가장 큰 수를 찾아 서로 곱한다. 두 결과에서 2가 여섯 번 3이 두 번 한 소인수 중에서 가장 큰 수를 찾아서 나왔다. 즉 $2^{6}\times 3^{2}=576$ 최소 공배수가 576이라는 결론이 나온다.

응용

통분

통분은 분수끼리 더하거나 뺄 때 사용되는 기법이다. 통분 과정에서 최소공분모(=분모의 최소 공배수)를 공분모로서 사용하면, 분모의 곱을 사용하는 경우보다 더 쉽게 계산할 수 있다. 예를 들어,

{2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}

는 최소공분모 $\operatorname {lcm} \{21,6\}=42$ 를 사용하여 계산한 것이다.

같이 보기

인수 분해

참고 문헌

↑ ^가 ^나 ^다 Apostol, Tom Mike (1976). 《Introduction to analytic number theory》. Undergraduate Texts in Mathematics (영어). 뉴욕: Springer-Verlag. doi:10.1007/978-1-4757-5579-4. ISBN 978-1-4419-2805-4. ISSN 0172-6056. MR 0434929. Zbl 0335.10001.

[Apostol-1] 가 ^나 ^다 Apostol, Tom Mike (1976). 《Introduction to analytic number theory》. Undergraduate Texts in Mathematics (영어). 뉴욕: Springer-Verlag. doi:10.1007/978-1-4757-5579-4. ISBN 978-1-4419-2805-4. ISSN 0172-6056. MR 0434929. Zbl 0335.10001.

[1]