Least common multiple

Original article: w:Least common multiple

A Venn diagram showing the least common multiples of combinations of 2, 3, 4, 5 and 7 (6 is skipped as it is 2 × 3, both of which are already represented).
For example, a card game which requires its cards to be divided equally among up to 5 players requires at least 60 cards, the number at the intersection of the 2, 3, 4, and 5 sets, but not the 7 set.

산술(arithmetic)과 숫자 이론(number theory)에서, 두 정수(integer) a와 b의 최소 공통 배수(least common multiple, lowest common multiple, 또는 smallest common multiple)는, 보통 LCM(a, b)에 의해 표시되며, a와 b 둘 다로 나뉠(divisible) 수 있는 가장-작은 양의 정수입니다. 영에 의한 정수의 나눗셈은 정의되지 않기 때문에, 이 정의는 만약 a와 b가 둘 다 영과 다르면 오직 의미를 가집니다. 어쨌든, 일부 저자는 LCM (a,0)을 모든 a에 대해 0으로 정의하며, 이것은 LCM을 나눔가능성의 격자(lattice)에서 최소 위쪽 경계(least upper bound)로 취하는 결과입니다.

LCM은 분수(fractions)가 더해저거나, 빼지거나 비교될 수 있기 전에 사용될 수 있는 "최소 공통 분모(lowest common denominator)" (LCD)입니다. 둘보다 많은 정수의 LCM은 역시 잘 정의됩니다: 그것은 각 정수로 나뉠 수 있는 가장-작은 양의 정수입니다.

Overview

숫자의 배수(multiple)는 해당 숫자와 정수의 곱입니다. 예를 들어, 10은 5 × 2 = 10이기 때문에 5의 배수이므로, 10은 5와 2로 나뉠 수 있습니다. 10은 5와 2 둘 다로 나뉠 수 있는 가장-작은 양의 정수이기 때문에, 그것은 5와 2의 최소 공통 배수입니다. 같은 원리에 의해, 10은 마찬가지로 −5와 −2의 최소 공통 배수입니다.

Notation

두 정수 a와 b의 최소 공통 배수는 lcm(a, b)로 표현됩니다. 일부 이전 교과서는 [a, b]를 사용합니다.

Example

$\operatorname {lcm} (4,6)$

4의 배수는 다음입니다:

$4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...$

6의 배수는 다음입니다:

$6,12,18,24,30,36,42,48,54,60,66,72,...$

4와 6의 공통 배수는 목록 둘 다에 있는 숫자들입니다:

$12,24,36,48,60,72,...$

이 목록에서, 가장 작은 숫자는 12입니다. 따라서, 최소 공통 배수는 12입니다.

Applications

단순 분수(simple fraction)를 더하거나, 빼거나, 비교할 때, 분모의 최소 공통 배수 (종종 최소 공통 분모(lowest common denominator)라고 불림)가 사용되는데, 왜냐하면 각 분수는 이 분모를 갖는 분수로 표현될 수 있기 때문입니다. 예를 들어,

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

여기서 분모 42가 사용되는데, 왜냐하면 그것이 21과 6의 최소 공통 배수이기 때문입니다.

Gears problem

기계(machine)에서 각각 m과 n 톱니를 가지는 둘의 맞물림 기어(meshing gears)가 있고, 기어는 첫 번째 기어의 중심에서 두 번째 기어의 중심까지 그려진 선분으로 표시되어 있다고 가정합니다. 기어가 회전하기 시작할 때, 선분을 재정렬하기 위해 첫 번째 기어가 완료해야 하는 회전의 숫자는 $\operatorname {lcm} (m,n)$을 사용함으로써 계산될 수 있습니다. 첫 번째 기어는 재정렬에 대해 $\operatorname {lcm} (m,n) \over m$ 회전을 완료해야 합니다. 해당 시간까지, 두 번째 기어는 $\operatorname {lcm} (m,n) \over n$ 회전을 만들어야 할 것입니다.

Planetary alignment

See also: Planetary alignment

행성의 궤도를 완성하기 위해, 각각 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$ 궤도를 완료할 것입니다.

Calculation

Using the greatest common divisor

다음 공식은 최소 공통 배수 계산 문제를, 역시 최대 공통 인수로 알려져 있는 최대 공통 약수(greatest common divisor) (gcd)의 계산 문제로 축소합니다:

$\operatorname {lcm} (a,b)={\frac {|ab|}{\gcd(a,b)}}.$

이 공식은 역시 gcd(a, 0) = |a|이기 때문에 a와 b 중 정확하게 하나가 0일 때 유효합니다. 어쨌든, 만약 a와 b 둘 다가 0이면, 이 공식은 영에 의한 나눗셈(division by zero)을 초래할 것입니다; lcm(0, 0) = 0은 특별한 경우입니다.

유클리드 알고리듬(Euclidean algorithm)과 같은 인수화(factored)될 숫자를 요구하지 않은 gcd를 계산하기 위한 빠른 알고리듬(algorithm)이 있습니다. 위의 예제로 돌아가기 위해,

$\operatorname {lcm} (21,6)={21\cdot 6 \over \gcd(21,6)}={21\cdot 6 \over \gcd(3,6)}={21\cdot 6 \over 3}={\frac {126}{3}}=42.$

gcd(a, b)가 a와 b 둘 다의 약수이기 때문에, 곱하기 전에 나눔으로써 lcm를 계산하는 것이 더 효율적입니다:

$\operatorname {lcm} (a,b)=\left({|a| \over \gcd(a,b)}\right)\cdot |b|=\left({|b| \over \gcd(a,b)}\right)\cdot |a|.$

이것은 나눗셈과 곱셈 둘 다에 대해 하나의 입력 크기를 줄이고, 중간 결과 (즉, axb 계산에서 오버플로)에 필요된 요구된 저장 공간을 줄입니다. gcd(a, b)는 a와 b 둘 다의 약수이기 때문에, 나눗셈은 정수를 산출하도록 보장되므로, 중간 결과는 정수로 저장될 수 있습니다. 이러한 방법으로 구현된, 이전 예제는 다음이 됩니다:

$\operatorname {lcm} (21,6)={21 \over \gcd(21,6)}\cdot 6={21 \over \gcd(3,6)}\cdot 6={21 \over 3}\cdot 6=7\cdot 6=42.$

Using prime factorization

고유한 인수분해 정리(unique factorization theorem)는 1보다 큰 모든 각 양의 정수는 소수(prime number)의 곱으로 유일한 한 가지 방법으로 쓸 수 있음을 나타냅니다. 소수는, 결합될 때, 합성수(composite number)를 구성하는 원자 원소로 고려될 수 있습니다.

예를 들어:

$90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.$

여기서, 합성수 90은 소수 2의 원자 1개, 소수 3의 원자 2개, 및 소수 5의 원자 1개로 구성됩니다.

이 사실은 숫자의 집합의 lcm을 찾기 위해 사용될 수 있습니다.

예제: lcm(8,9,21)

각 숫자를 인수분해하고 그것을 소수 거듭제곱(powers)의 곱으로 표현합니다.

${\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}$

lcm은 각 소수의 가장 높은 거듭제곱을 함께 곱한 결과일 것입니다. 세 소수 2, 3, 및 7의 가장 높은 거듭제곱은 각각 2³, 3², 및 7¹입니다. 따라서,

$\operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.$

이 방법은 정수 인수분해(integer factorization)에 대해 알려진 일반적인 효율적인 알고리듬이 없기 때문에 최대 공통 약수로 줄이는 것만큼 효율적이지 않습니다.

같은 방법은 역시 다음과 같이 벤 다이어그램(Venn diagram)으로 설명될 수 있으며, 두 숫자 각각의 소수 인수분해(prime factorization)는 각 원에 표시되고 그것들이 공통으로 갖는 모든 인수는 교집합에서 공유합니다. lcm는 그런-다음 다이어그램에서 모든 소수를 곱함으로써 구할 수 있습니다.

다음은 예제입니다:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5,

둘의 "2"와 하나의 "3"으로 공통으로 공유합니다:

최소 공통 배수 = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

최대 공통 약수 = 2 × 2 × 3 = 12

이것은 역시 벤다이어그램에서 모든 숫자를 곱하는 대신, 교집합에 있는 소수 인수만 곱한다는 점을 제외하고는 최대 공통 약수(greatest common divisor) (gcd)에 적용됩니다. 따라서 48과 180의 gcd는 2 × 2 × 3 = 12입니다.

Using a simple algorithm

이 방법은 여러 정수의 lcm를 찾는 데 쉽게 작동합니다.

양의 정수의 유한 수열 X = (x₁, x₂, ..., x_n), n > 1이 있다고 놓습니다. 알고리듬은 다음과 같은 단계로 진행합니다: 각 단계 m에서 수열 X^(m) = (x₁^(m), x₂^(m), ..., x_n^(m)), X⁽¹⁾ = X을 검사하고 업데이트하며, 여기서 X^(m)은 X의 m번째 반복, 즉 알고리듬의 m 단계에서 X, 등입니다. 검사의 목적은 수열 X^(m)의 최소 원소 (아마도, 많은 것 중 하나)를 선택하는 것입니다. x_k0^(m)이 선택된 원소라고 가정하면, 수열 X^(m+1)은 다음으로 정의됩니다:

x_k^(m+1) = x_k^(m), k ≠ k₀

x_k0^(m+1) = x_k0^(m) + x_k0⁽¹⁾.

다시 말해서, 최소 원소는 해당하는 x만큼 증가하는 반면 나머지 원소는 변경되지 않고 X^(m)에서 X^(m+1)로 전달됩니다.

알고리듬은 수열 X^(m)에서 모든 원소가 같을 때 중지합니다. 그것들의 공통 값 L은 정확히 lcm(X)입니다.

예를 들어, 만약 X = X⁽¹⁾ = (3, 4, 6)이면, 알고리듬에서 단계는 다음을 생성합니다:

X⁽²⁾ = (6, 4, 6)

X⁽³⁾ = (6, 8, 6)

X⁽⁴⁾ = (6, 8, 12) - 두 번째 6을 선택함으로써

X⁽⁵⁾ = (9, 8, 12)

X⁽⁶⁾ = (9, 12, 12)

X⁽⁷⁾ = (12, 12, 12) 따라서 lcm = 12.

Using the table-method

이 방법은 숫자의 임의의 개수에 대해 작동합니다. 우리는 테이블에 세로로 모든 숫자를 나열함으로써 시작합니다 (이 예제에서, 4, 7, 12, 21, 및 42).

4

7

12

21

42

그 과정은 모든 숫자를 2로 나눔으로써 시작됩니다. 만약 2가 그것들 중 임의의 것을 균등하게 나누면, 테이블의 상단에서 새로운 열에 2를 쓰고, 이 새로운 열에서 오른쪽에 공백에서 각 숫자를 2에 의한 나눗셈의 결과입니다. 만약 한 숫자가 균등하게 나누어지지 않으면, 단지 그 숫자를 다시 쓰십시오. 만약 2가 어떤 숫자로도 균등하게 나누지 않으면, 다음으로 큰 소수, 3을 사용하여 이 절차를 반복하십시오 (아래를 참조).

×	2
4	2
7	7
12	6
21	21
42	21

이제, 2가 적어도 하나의 숫자를 나눴다고 가정하고 (이 예에서와 같이), 2가 다시 나누는지 확인하십시오:

×	2	2
4	2	1
7	7	7
12	6	3
21	21	21
42	21	21

2가 더 이상 현재 열에서 임의의 숫자를 나누지 않으면, 다음으로 더 큰 소수 3으로 나눔으로써 절차를 반복하십시오. 3이 더 이상 나누지 않으면, 다음으로 더 큰 소수, 5, 그 다음 7, 등을 시도하십시오. 그 절차는 모든 숫자가 1로 줄어들었을 때 끝납니다 (마지막 소수 약수 아래의 열은 1로만 구성됩니다).

×	2	2	3	7
4	2	1	1	1
7	7	7	7	1
12	6	3	1	1
21	21	21	7	1
42	21	21	7	1

이제, 맨 위 행에서 숫자를 곱하여 lcm를 구합니다. 이 경우에서, 그것은 2 × 2 × 3 × 7 = 84입니다.

일반적인 계산 알고리듬으로서, 위의 것은 상당히 비효율적입니다. 우리는 소프트웨어에서 그것을 구현하고 싶지 않을 것입니다: 그것은 너무 많은 단계가 취하고 너무 많은 저장 공간을 요구합니다. 훨씬 더 효율적인 수치적 알고리듬은 먼저 유클리드 알고리듬(Euclid's algorithm)을 사용을 gcd를 계산하고, 그런-다음 나눗셈으로 lcm를 구함으로써 얻어질 수 있습니다.

Formulas

Fundamental theorem of arithmetic

산술의 기본 정리(fundamental theorem of arithmetic)에 따르면, 1보다 큰 모든 각 정수는 인수의 순서까지(up to) 소수의 곱으로 고유하게 나타낼 수 있습니다:

$n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod _{p}p^{n_{p}},$

여기서 지수 n₂, n₃, ...는 비-음의 정수입니다; 예를 들어, 84 = 2² 3¹ 5⁰ 7¹ 11⁰ 13⁰ ...

두 양의 정수 ${\textstyle a=\prod _{p}p^{a_{p}}}$와 ${\textstyle b=\prod _{p}p^{b_{p}}}$가 주어지면, 그것들의 최소 공통 배수와 최대 공통 약수는 다음 공식에 의해 제공됩니다:

$\gcd(a,b)=\prod _{p}p^{\min(a_{p},b_{p})}$

및

$\operatorname {lcm} (a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.$

다음이기 때문에,

$\min(x,y)+\max(x,y)=x+y,$

이것은 다음을 제공합니다:

$\gcd(a,b)\operatorname {lcm} (a,b)=ab.$

사실, 모든 각 유리수는 만약 음의 지수가 허용되면 소수의 곱으로 고유하게 쓸 수 있습니다:

${\begin{aligned}4&=2^{2}3^{0},&6&=2^{1}3^{1},&\gcd(4,6)&=2^{1}3^{0}=2,&\operatorname {lcm} (4,6)&=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}&=2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}&=2^{1}3^{0}5^{-1},&\gcd \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{0}3^{-1}5^{-1}={\tfrac {1}{15}},&\operatorname {lcm} \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{1}3^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{4}}&=2^{-2}3^{1},&\gcd \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{aligned}}$

Lattice-theoretic

양의 정수는 나눔가능성에 의해 부분적으로 순서화(partially ordered)될 수 있습니다: 만약 a가 b를 나누면 (즉, 만약 b가 a의 정수 배수(integer multiple)이면), a ≤ b라고 씁니다 (또는 동등하게, b ≥ a라고 씁니다). (≤의 보통의 크기-기반 정의는 여기사 사용되지 않음에 주목하십시오.)

이 순서화 아래에서, 양의 정수는 gcd에 의해 제공된 만남(meet)과 lcm에 의해 제공된 접합(join)을 갖는 격자(lattice)가 됩니다. 그 증명은 약간 지루하더라도 간단합니다; 그것은 lcm 및 gcd가 만남과 접합에 대해 공리를 만족하는지 확인하는 것과 같습니다. lcm 및 gcd를 보다 일반적인 컨텍스트에 넣으면 둘 사이에 이중성(duality)을 설정합니다:

만약 정수 변수, gcd, lcm, ≤ 및 ≥를 포함하는 공식이 참이면, gcd를 lcm로 전환하고 ≥를 ≤로 전환함으로써 얻어진 공식은 역시 참입니다. (≤는 나누기로 정의됨을 기억하십시오).

다음 쌍의 이중 공식은 일반 격자-이론적 항등식의 특수한 경우입니다.

교환 법칙(Commutative laws) $\operatorname {lcm} (a,b)=\operatorname {lcm} (b,a),$ $\gcd(a,b)=\gcd(b,a).$

결합 법칙(Associative laws) $\operatorname {lcm} (a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\operatorname {lcm} (a,b),c),$ $\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c).$

흡수 법칙(Absorption law) $\operatorname {lcm} (a,\gcd(a,b))=a,$ $\gcd(a,\operatorname {lcm} (a,b))=a.$

거듭상등 법칙(Idempotent laws) $\operatorname {lcm} (a,a)=a,$ $\gcd(a,a)=a.$

lcm과 gcd의 관점에서 나누기를 정의합니다 $a\geq b\iff a=\operatorname {lcm} (a,b),$ $a\leq b\iff a=\gcd(a,b).$

역시 이 격자가 분배적(distributive)임을 보일 수 있습니다; 즉, lcm은 gcd에 걸쳐 분배되고 gcd는 lcm에 걸쳐 분배됩니다:

$\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)).$

Other

• D를 ω(D) 구별되는 소수의 곱으로 놓습니다 (즉, D는 제곱-없음(squarefree)입니다).

그런-다음

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

여기서 절댓값 막대 ||는 집합의 카디널리티를 나타냅니다.

• 만약 $a_{1},a_{2},\ldots ,a_{r}$의 어떤 것도 영이 아니면, 다음입니다:

$\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r-1}),a_{r}).$

In commutative rings

최소 공통 배수는 일반적으로 교환 링(commutative ring)에 걸쳐 다음과 같이 정의될 수 있습니다: a와 b를 교환 링 R의 원소라고 놓습니다. a와 b의 공통 배수는 a와 b 둘 다가 m을 나눔을 만족하는 R의 원소 m입니다 (즉, ax = m와 by = m를 만족하는 R의 원소 x와 y가 존재합니다). a와 b의 최소 공통 배수는 a와 b의 임의의 다른 공통 배수 n에 대해, m이 n을 나눈다는 의미에서 최소인 공통 배수입니다.

일반적으로, 교환 링에서 두 원소는 최소 공통 배수를 가지지 않거나 하나보다 많이 가질 수 있습니다. 어쨌든, 같은 원소 쌍의 둘의 최소 공통 배수는 동료(associates)입니다. 고유한 인수분해 도메인(unique factorization domain)에서, 임의의 두 원소는 최소 공통 배수를 가집니다. 주요 아이디얼 도메인(principal ideal domain)에서, a와 b의 최소 공통 배수는 a와 b에 의해 생성된 아이디얼의 교집합의 생성기로 특성화될 수 있습니다 (아이디얼 집합의 교집합은 항상 아이디얼입니다).

See also

• Anomalous cancellation
• Coprime integers
• Chebyshev function

References

• Crandall, Richard; Pomerance, Carl (2001), Prime Numbers: A Computational Perspective, New York: Springer, ISBN 0-387-94777-9
• Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
• Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766