수론 에서, 여러 개의 정수 /다항식 /환 의 원소의 공배수 (公倍數, 영어 : common multiple )는 그들 모두의 배수 가 되는 정수/다항식/환의 원소이다. 최소공배수 (最小公倍數, 영어 : least common multiple/ lowest common multiple , 약자 LCM)는 양의 공배수 가운데 가장 작은 하나이다. 유클리드 정역 에서 0으로 나누기를 정의하지 않으므로, 이 정의는 오직 다루고자 하는 정수들이 0이 아닐 때 의미가 있다. 그러나 일부 저자는
lcm
{
a
,
0
}
{\displaystyle \operatorname {lcm} \{a,0\}}
격자 에서 최소공배수를 최소 상한 으로 간주한 것이다.
두 정수
n
,
m
∈
Z
:
n
m
≠
0
{\displaystyle n,m\in \mathbb {Z} :nm\neq 0}
최소공배수
lcm
{
n
,
m
}
{\displaystyle \operatorname {lcm} \{n,m\}}
동치 이다.
n
{\displaystyle n}
m
{\displaystyle m}
n
{\displaystyle n}
m
{\displaystyle m}
n
{\displaystyle n}
m
{\displaystyle m}
약수 여러 개의 정수
n
1
,
n
2
,
…
,
n
k
∈
Z
:
n
k
≠
0
{\displaystyle n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z} :n_{k}\neq 0}
최소공배수
lcm
{
n
1
,
n
2
,
…
,
n
k
}
{\displaystyle \operatorname {lcm} \{n_{1},n_{2},\dots ,n_{k}\}}
동치 이다.
음이 아닌 가장 작은 공배수
음이 아닌 공배수이자, 모든 공배수의 약수
(재귀적 정의)
lcm
{
lcm
{
n
1
,
n
2
,
…
,
n
k
−
1
}
,
n
k
}
{\displaystyle \operatorname {lcm} \{\operatorname {lcm} \{n_{1},n_{2},\dots ,n_{k-1}\},n_{k}\}}
두 정수의 최소공배수는 최대공약수 와 다음과 같은 관계를 가진다.
N
1
=
gcd
{
N
1
,
N
2
}
⋅
n
1
{\displaystyle N_{1}=\operatorname {gcd} \{N_{1},N_{2}\}\cdot n_{1}}
N
2
=
gcd
{
N
1
,
N
2
}
⋅
n
2
{\displaystyle N_{2}=\operatorname {gcd} \{N_{1},N_{2}\}\cdot n_{2}}
lcm
{
N
1
,
N
2
}
=
gcd
{
N
1
,
N
2
}
⋅
n
1
n
2
{\displaystyle \operatorname {lcm} \{N_{1},N_{2}\}=\operatorname {gcd} \{N_{1},N_{2}\}\cdot n_{1}n_{2}}
특히, 두 서로소 정수 의 최소공배수는 그 두 정수의 곱이다.
gcd
{
N
1
,
N
2
}
=
1
,
n
1
n
2
=
N
1
N
2
⟹
lcm
{
N
1
,
N
2
}
=
N
1
N
2
{\displaystyle \gcd\{N_{1},N_{2}\}=1,\ n_{1}n_{2}=N_{1}N_{2}\implies \operatorname {lcm} \{N_{1},N_{2}\}=N_{1}N_{2}}
공배수는 최소공배수의 배수와 동치 이다.
n
,
m
∣
M
⟺
lcm
{
n
,
m
}
∣
M
{\displaystyle n,m\mid M\iff \operatorname {lcm} \{n,m\}\mid M}
n
i
∣
M
(
i
=
1
,
…
,
k
)
⟺
lcm
{
n
i
}
i
=
1
,
…
,
k
∣
M
{\displaystyle n_{i}\mid M\quad (i=1,\dots ,k)\iff \operatorname {lcm} \{n_{i}\}_{i=1,\dots ,k}\mid M}
약수 관계는 최소공배수를 통해 다음과 같이 기술할 수 있다.
n
∣
m
⟺
lcm
{
n
,
m
}
=
m
{\displaystyle n\mid m\iff \operatorname {lcm} \{n,m\}=m}
소인수분해 가 주어진 정수들의 최대공배수는 공통된 소인수의 최대 지수 거듭제곱의 곱이다. 두 정수의 경우, 소인수분해가
n
=
p
1
e
1
p
2
e
2
⋯
p
t
e
t
{\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{t}^{e_{t}}}
m
=
p
1
f
1
p
2
f
2
⋯
p
t
f
t
{\displaystyle m=p_{1}^{f_{1}}p_{2}^{f_{2}}\cdots p_{t}^{f_{t}}}
e
i
,
f
i
∈
Z
≥
0
{\displaystyle e_{i},f_{i}\in \mathbb {Z} _{\geq 0}}
라면, 최소공배수는
lcm
{
n
,
m
}
=
p
1
max
{
e
1
,
f
1
}
p
2
max
{
e
2
,
f
2
}
⋯
p
t
max
{
e
t
,
f
t
}
{\displaystyle \operatorname {lcm} \{n,m\}=p_{1}^{\max\{e_{1},f_{1}\}}p_{2}^{\max\{e_{2},f_{2}\}}\cdots p_{t}^{\max\{e_{t},f_{t}\}}}
이다.
두 수 a와 b의 최소공배수를 구하는 방법은 소인수 분해 를 사용하는 방법이 있다.
두 수 192와 72의 최소공배수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.
192
=
2
6
×
3
{\displaystyle 192=2^{6}\times 3}
72
=
2
3
×
3
2
{\displaystyle 72=2^{3}\times 3^{2}}
구하고 나면, 두 소인수 분해 결과의 한 소인수 중에서 지수가 가장 큰 수를 찾아 서로 곱한다. 두 결과에서 2가 여섯 번 3이 두 번 한 소인수 중에서 가장 큰 수를 찾아서 나왔다. 즉
2
6
×
3
2
=
576
{\displaystyle 2^{6}\times 3^{2}=576}
통분 은 분수 끼리 더하거나 뺄 때 사용되는 기법이다. 통분 과정에서 최소공분모(=분모의 최소공배수)를 공분모로서 사용하면, 분모의 곱을 사용하는 경우보다 더 쉽게 계산할 수 있다. 예를 들어,
2
21
+
1
6
=
4
42
+
7
42
=
11
42
{\displaystyle {2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}}
는 최소공분모
lcm
{
21
,
6
}
=
42
{\displaystyle \operatorname {lcm} \{21,6\}=42}
