맨위로가기

최소공배수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

최소공배수는 0이 아닌 두 정수 또는 다항식의 공배수 중에서 가장 작은 양의 정수 또는 가장 낮은 차수의 다항식을 의미한다. 두 정수 a, b의 최소공배수는 lcm(a, b)로 표기하며, 최대공약수와 밀접한 관련이 있다. 최소공배수는 소인수분해 또는 최대공약수를 이용하여 계산할 수 있으며, 분수의 통분, 톱니바퀴 문제, 행성 정렬 등 다양한 분야에 응용된다. 가환환에서도 최소공배수를 정의할 수 있으며, 일의적 인수분해 정역에서는 임의의 두 원소가 최소공배수를 갖는다.

더 읽어볼만한 페이지

  • 산수 - 계산
    계산은 수나 식을 이용해 연산을 하거나 주어진 정보로 결과를 내는 행위로, 어원은 각각 석회에서 유래한 'calculation'과 '함께 계산하다'라는 뜻의 'computation'이며, 계산기나 컴퓨터 등의 도구를 통해 수행된다.
  • 산수 - 받아올림
    받아올림은 덧셈에서 자릿수 합이 10을 넘을 때 윗자리로 1을 올리는 것이며, 뺄셈에서는 윗자리에서 10을 빌려오는 빌림이 발생하는 개념이다.
  • 수론 - 타원곡선
    타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
  • 수론 - 디리클레 합성곱
    디리클레 합성곱은 두 수론적 함수를 이용하여 새로운 수론적 함수를 생성하는 연산으로, n의 모든 양의 약수에 대한 함수값의 곱의 합으로 정의되며, 교환, 결합, 분배 법칙을 만족하고 곱셈적 함수의 곱셈성을 보존하며, 디리클레 급수 연구에 활용된다.
최소공배수
수학적 정보
정의두 개 이상의 자연수의 공통된 배수 중에서 가장 작은 수
기호lcm(a, b) 또는 최소공배수(a, b)
특징
계산 방법소인수분해를 이용
유클리드 호제법을 이용 (최대공약수와 함께)
성질lcm(a, b) * gcd(a, b) = a * b (gcd는 최대공약수)
a, b가 서로소이면 lcm(a, b) = a * b
활용
분수 계산분수의 덧셈, 뺄셈에서 통분에 활용
정수론다양한 정수론적 문제 해결에 활용

2. 정의

두 정수 ${\displaystyle n,m\in \mathbb {Z} :nm\neq 0}$의 최소공배수 ${\displaystyle \operatorname {lcm} \{n,m\}}$는 다음과 같이 정의될 수 있으며, 이들 정의는 서로 동치이다.


  • ${\displaystyle n}$, ${\displaystyle m}$의 음이 아닌 공배수 가운데 가장 작은 하나
  • ${\displaystyle n}$, ${\displaystyle m}$의 음이 아닌 공배수이자, ${\displaystyle n}$, ${\displaystyle m}$의 모든 공배수의 약수

여러 개의 정수 ${\displaystyle n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z} :n_{k}\neq 0}$의 최소공배수 ${\displaystyle \operatorname {lcm} \{n_{1},n_{2},\dots ,n_{k}\}}$는 다음과 같이 정의될 수 있으며, 이들 정의는 서로 동치이다.

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

어떤 수의 배수는 그 수와 정수의 곱이다. 예를 들어, 10은 5의 배수이다. 왜냐하면 5 × 2 = 10이기 때문이다. 따라서 10은 5와 2로 나눌 수 있다. 10은 5와 2 모두로 나눌 수 있는 가장 작은 양의 정수이므로, 5와 2의 최소공배수이다. 같은 원리로, 10은 −5와 −2의 최소공배수이기도 하다.

2개 이상의 정수 $a_1, \ldots, a_n$의 최소공배수는 $a_1, \ldots, a_n$의 공배수 중 가장 작은 양의 정수이다.

즉, $a_1, \ldots, a_n$을 소수 $p$를 이용하여

:$a_{j}=\varepsilon _{j}\prod _{p:\,\mathrm {prime} }p^{e_{p}(j)}\ \ (e_{p}(j)\geq 0,\ \ \varepsilon _{j}=\pm 1)$

로 소인수분해했을 때, $a_1, \ldots, a_n$의 최소공배수는

:$\prod _{p:\,\mathrm {prime} }p^{\max\{e_{p}(1),\ldots ,e_{p}(n)\}}$

로 주어진다.

예를 들어, 12와 16의 최소공배수는 48이다.

: 12 = 22×31

: 16 = 24

: 48 = 24×31

2. 1. 정수의 최소공배수

두 정수 ${\displaystyle n,m\in \mathbb {Z} :nm\neq 0}$의 최소공배수 ${\displaystyle \operatorname {lcm} \{n,m\}}$는 다음과 같이 정의될 수 있으며, 이들 정의는 서로 동치이다.

  • ${\displaystyle n}$, ${\displaystyle m}$의 음이 아닌 공배수 가운데 가장 작은 하나
  • ${\displaystyle n}$, ${\displaystyle m}$의 음이 아닌 공배수이자, ${\displaystyle n}$, ${\displaystyle m}$의 모든 공배수의 약수

여러 개의 정수 ${\displaystyle n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z} :n_{k}\neq 0}$의 최소공배수 ${\displaystyle \operatorname {lcm} \{n_{1},n_{2},\dots ,n_{k}\}}$는 다음과 같이 정의될 수 있으며, 이들 정의는 서로 동치이다.

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

2개 이상의 정수 $a_1, \ldots, a_n$의 최소공배수는 $a_1, \ldots, a_n$의 공배수 중 가장 작은 양의 정수이다.

즉, $a_1, \ldots, a_n$을 소수 $p$를 이용하여

:${\displaystyle a_{j}=\varepsilon _{j}\prod _{p:\,\mathrm {prime} }p^{e_{p}(j)}\ \ (e_{p}(j)\geq 0,\ \ \varepsilon _{j}=\pm 1)}$

로 소인수분해했을 때, $a_1, \ldots, a_n$의 최소공배수는

:${\displaystyle \prod _{p:\,\mathrm {prime} }p^{\max\{e_{p}(1),\ldots ,e_{p}(n)\}}}$

로 주어진다.

예를 들어, 12와 16의 최소공배수는 48이다.

: 12 = 22×31

: 16 = 24

: 48 = 24×31

2. 2. 다항식의 최소공배수

다항식의 0이 아닌 공배수 중에서 차수가 가장 낮은 것을 최소공배수라고 한다. 예를 들어, x³-x와 x³+x²-x-1의 최소공배수는 x(x+1)²(x-1)이다. 다항식의 최소공배수는 상수배를 제외하고 유일하게 결정된다.

3. 표기법

두 정수 ''a''와 ''b''의 최소공배수는 lcm(''a'', ''b'')로 표기한다.[1] 일부 오래된 교과서에서는 [''a'', ''b'']를 사용하기도 한다.[3][4]

4. 성질

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

:N_1 = \operatorname{gcd}\{N_1,N_2 \} \cdot n_1

:N_2 = \operatorname{gcd}\{N_1,N_2 \} \cdot n_2일 때,


  • :

:\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 \implies\operatorname{lcm}\{N_1,N_2\}=N_1 N_2

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

:n,m\mid M\iff\operatorname{lcm}\{n,m\}\mid M

:n_i\mid M\quad(i=1,\dots,k)\iff\operatorname{lcm}\{n_i\}_{i=1,\dots,k}\mid M

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

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

소인수분해가 주어진 정수들의 최소공배수는 공통된 소인수의 최대 지수 거듭제곱의 곱이다. 두 정수의 경우, 소인수분해가

: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_i,f_i\in\mathbb Z_{\ge0}

라면, 최소공배수는

::\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\}}

이다.

산술의 기본 정리에 따르면, 1보다 큰 모든 정수는 소수의 곱으로 유일하게 나타낼 수 있으며, 인수의 순서는 고려하지 않는다.

:n = 2^{n_2} 3^{n_3} 5^{n_5} 7^{n_7} \cdots = \prod_p p^{n_p},

여기서 지수 ''n''2, ''n''3, ...는 음이 아닌 정수이다. 예를 들어, 84 = 22 31 50 71 110 130 ...

두 양의 정수 a = \prod_p p^{a_p} 와 b = \prod_p p^{b_p}가 주어지면, 최소공배수는 다음 공식으로 주어진다.

:\operatorname{lcm}(a,b) = \prod_p p^{\max(a_p, b_p)}.

D를 ω(D)개의 서로 다른 소수의 곱이라고 하자 (즉, D는 무자승수이다).

그러면[7]

:|\{(x,y) \;:\; \operatorname{lcm}(x,y) = D\}| = 3^{\omega(D)},

여기서 절댓값 기호 ||는 집합의 원소의 개수를 나타낸다.

a_1, a_2, \ldots , a_r 중 어느 것도 0이 아니면,

:\operatorname{lcm}(a_1, a_2, \ldots , a_r) = \operatorname{lcm}(\operatorname{lcm}(a_1, a_2, \ldots , a_{r-1}), a_r). [8][9]

정수 a, b에 대해, a와 b의 최대공약수 gcd(a, b)와 최소공배수 lcm(a, b) 사이에는

:

\mathrm{gcd}(a,\ b)\cdot\mathrm{lcm}(a,\ b) = ab



의 관계가 있다.

그러나 이 관계식은 3개 이상의 정수에 대해서는 일반적으로 성립하지 않는다. 예를 들어, a = 2, b = 6, c = 15라고 하면, gcd(a, b, c) = 1, lcm(a, b, c) = 30이지만, abc = 180이다.

5. 계산

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

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

:192=2^6\times 3

:72=2^3 \times 3^2

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

최소공배수를 계산하는 방법은 여러 가지가 있다.

5. 1. 소인수분해

소인수 분해를 통해 주어진 정수들의 최소공배수를 구할 수 있다. 이 방법은 공통된 소인수의 최대 지수 거듭제곱을 곱하는 방식으로 이루어진다.

두 정수 192와 72의 최소공배수를 구하는 과정은 다음과 같다.

  • 192와 72를 소인수분해한다:

::192=2^6\times 3

::72=2^3 \times 3^2

  • 각 소인수의 지수 중 가장 큰 값을 찾아 곱한다: 2^6 \times 3^2=576. 따라서 최소공배수는 576이다.


산술의 기본 정리에 따르면, 1보다 큰 모든 양의 정수는 소수의 곱으로 유일하게 표현 가능하다. 이 원리를 이용하면 여러 수의 최소공배수도 구할 수 있다. 예를 들어, lcm(8, 9, 21)을 구하기 위해 각 수를 소인수분해하면 다음과 같다.

:

\begin{align}

8 & = 2^3 \\

9 & = 3^2 \\

21 & = 3^1 \cdot 7^1

\end{align}



최소공배수는 각 소수의 가장 높은 거듭제곱을 모두 곱한 값인 2^3 \cdot 3^2 \cdot 7^1 = 504이다.

두 양의 정수 a = \prod_p p^{a_p} 와 b = \prod_p p^{b_p}의 최소공배수는 \operatorname{lcm}(a,b) = \prod_p p^{\max(a_p, b_p)}로 주어진다.

5. 2. 최대공약수 이용

최소공배수는 최대공약수(gcd)를 이용하여 다음 공식으로 계산할 수 있다.

:\operatorname{lcm}(a,b)=\frac

{\gcd(a,b)}.

결과보다 큰 정수를 도입하지 않으려면 다음과 같은 동등한 공식을 사용하는 것이 편리하다.

:\operatorname{lcm}(a,b)=|a|\,\frac

{\gcd(a,b)} = |b|\,\frac

{\gcd(a,b)} ,

여기서 나눗셈의 결과는 항상 정수이다.

유클리드 호제법과 같이 수를 소인수분해할 필요가 없는 최대공약수를 계산하는 빠른 알고리즘이 존재한다.

6. 응용

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

:{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42}}

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

맞물린 두 기어가 기계에 있는데, 각각 ''m''개와 ''n''개의 이빨을 가지고 있다고 가정한다. 첫 번째 기어의 중심에서 두 번째 기어의 중심으로 선분을 그어 기어에 표시하고 기어가 회전하기 시작했을 때, 선분이 다시 일직선으로 정렬되도록 첫 번째 기어가 완료해야 하는 회전 수는 최소공배수를 사용하여 계산할 수 있다. 이 때 첫 번째 기어는 {m, n}over m 회전을 완료해야 하고, 두 번째 기어는 {m, n}over n 회전을 한다.

합(천문학)

별 주위를 공전하는 세 개의 행성이 각각 ''l'', ''m'', ''n'' 단위 시간에 궤도를 완료한다고 가정했을 때(이때, ''l'', ''m'', ''n''은 정수이다), 모든 행성은 최소공배수 {l, m, n} 단위 시간 후에 다시 직선 정렬을 이룬다. 이때, 첫 번째, 두 번째, 세 번째 행성은 각각 {l, m, n}over l, {l, m, n}over m, {l, m, n}over n 궤도를 완료하게 된다.[5]

6. 1. 통분

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

:{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42}

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

6. 2. 톱니바퀴 문제

맞물린 두 기어가 기계에 있는데, 각각 ''m''개와 ''n''개의 이빨을 가지고 있다고 가정한다. 첫 번째 기어의 중심에서 두 번째 기어의 중심으로 선분을 그어 기어에 표시하고 기어가 회전하기 시작했을 때, 선분이 다시 일직선으로 정렬되도록 첫 번째 기어가 완료해야 하는 회전 수는 최소공배수를 사용하여 계산할 수 있다. 이 때 첫 번째 기어는 \operatorname{lcm}(m, n)\over m 회전을 완료해야 하고, 두 번째 기어는 \operatorname{lcm}(m, n)\over n 회전을 한다.

6. 3. 행성 정렬

합(천문학)

별 주위를 공전하는 세 개의 행성이 각각 ''l'', ''m'', ''n'' 단위 시간에 궤도를 완료한다고 가정했을 때(이때, ''l'', ''m'', ''n''은 정수이다), 모든 행성은 최소공배수 \operatorname{lcm}(l, m, n) 단위 시간 후에 다시 직선 정렬을 이룬다. 이때, 첫 번째, 두 번째, 세 번째 행성은 각각 \operatorname{lcm}(l, m, n)\over l, \operatorname{lcm}(l, m, n)\over m, \operatorname{lcm}(l, m, n)\over n 궤도를 완료하게 된다.[5]

7. 기타 성질

양의 정수는 나눗셈에 의해 부분 순서 집합으로 정의될 수 있으며, 이 순서에 따라 양의 정수는 격자가 된다.[6] 이때 최소공배수는 교를 나타낸다. 만약 ''a''가 ''b''를 나누면(즉, ''b''가 ''a''의 정수 배수이면) ''a'' ≤ ''b'' (또는 동등하게 ''b'' ≥ ''a'')라고 쓴다. 이러한 정의에 따르면, 최대공약수(gcd)는 합을, 최소공배수(lcm)는 교를 나타낸다.

최소공배수와 최대공약수를 이러한 더 일반적인 맥락에 적용하면 이들 사이의 쌍대성이 확립된다.[6]

:''정수 변수, 최대공약수, 최소공배수, ≤ 및 ≥를 포함하는 공식이 참이라면, 최대공약수와 최소공배수를 바꾸고 ≥와 ≤를 바꿈으로써 얻은 공식도 참이다.'' (≤는 나눈다는 것을 의미한다는 것을 기억하라.)

다음 쌍대 공식 쌍은 일반적인 격자 이론적 항등식의 특수한 경우이다.[6]

교환 법칙결합 법칙흡수 법칙
||



멱등 법칙최소공배수와 최대공약수를 이용한 나눗셈 정의
|



이 격자는 분배 격자이며, 최소공배수는 최대공약수에 대해 분배되고, 최대공약수는 최소공배수에 대해 분배된다.[6]

:\operatorname{lcm}(a,\gcd(b,c)) = \gcd(\operatorname{lcm}(a,b),\operatorname{lcm}(a,c)),

:\gcd(a,\operatorname{lcm}(b,c)) = \operatorname{lcm}(\gcd(a,b),\gcd(a,c)).

이 항등식은 자기 쌍대이다.

:\gcd(\operatorname{lcm}(a,b),\operatorname{lcm}(b,c),\operatorname{lcm}(a,c))=\operatorname{lcm}(\gcd(a,b),\gcd(b,c),\gcd(a,c)).

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


  • N_1 = \operatorname{gcd}\{N_1,N_2 \} \cdot n_1
  • N_2 = \operatorname{gcd}\{N_1,N_2 \} \cdot n_2일 때,
  • :
  • \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 \implies\operatorname{lcm}\{N_1,N_2\}=N_1 N_2

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

  • n,m\mid M\iff\operatorname{lcm}\{n,m\}\mid M
  • n_i\mid M\quad(i=1,\dots,k)\iff\operatorname{lcm}\{n_i\}_{i=1,\dots,k}\mid M

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

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

소인수분해가 주어진 정수들의 최소공배수는 공통된 소인수의 최대 지수 거듭제곱의 곱이다. 두 정수의 경우, 소인수분해가

  • 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_i,f_i\in\mathbb Z_{\ge0}

:라면, 최소공배수는

::\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\}}

:이다.

8. 가환환에서의 최소공배수

가환환에서도 최소공배수를 정의할 수 있다. 가환환 아르/R영어의 원소 에이/a영어, 비/b영어의 공배수 엠/m영어은, 에이엑스/ax영어 = 엠/m영어 및 비와이/by영어 = 엠/m영어인 아르/R영어의 원소 엑스/x영어와 와이/y영어가 존재함을 뜻한다. 최소공배수는 다른 모든 공배수 엔/n영어에 대해 엠/m영어이 엔/n영어을 나누는 공배수이다.

일반적인 가환환에서는 두 원소가 최소공배수를 갖지 않거나, 여러 개의 최소공배수를 가질 수 있다. 그러나 같은 두 원소의 임의의 두 최소공배수는 결합원이다. 일의적 인수분해 정역에서는 임의의 두 원소가 최소공배수를 가지며, 주 아이디얼 정역에서 에이/a영어와 비/b영어의 최소공배수는 에이/a영어와 비/b영어에 의해 생성된 아이디얼들의 교집합의 생성원으로 특징지을 수 있다.

참조

[1] 웹사이트 Least Common Multiple https://mathworld.wo[...] 2020-08-30
[2] 서적 Hardy & Wright
[3] 논문
[4] 논문
[5] 웹사이트 nasa spacemath https://spacemath.gs[...]
[6] 서적 Landau
[7] 서적 Crandall & Pomerance
[8] 논문
[9] 논문


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com