최소공배수

Least common multiple
2, 3, 4, 5 및 7의 최소 공통 배수를 보여주는 벤 다이어그램(6은 2 × 3으로 생략되며, 둘 다 이미 표현되어 있음)
예를 들어 최대 5명의 플레이어 간에 카드를 균등하게 분배해야 하는 카드게임은 적어도 60장의 카드가 필요하며, 이 숫자는 7세트가 아니라 2, 3, 4, 5세트의 교차점에 있어야 한다.

산술과 수론에서, 보통 lcm(a, b)로 나타나는 두 정수 a와 b의 최소공배수, 최소공배수 또는 최소공배수는 a[1][2]b로 나누어질 수 있는 가장 작은 양의 정수이다.정수를 0으로 나눈다는 것은 정의되어 있지 않기 때문에 이 정의는 a와 b가 모두 [3]0과 다른 경우에만 의미가 있습니다.그러나 일부 저자는 0이 a와 0의 유일한 공통배수이기 때문에 lcm(a,0)를 모든 a에 대해 0으로 정의한다.

lcm는 분수를 더하거나 빼거나 비교하기 에 사용할 수 있는 "가장 낮은 공통분모"(lcd)이다.

일반적으로 lcm(a, b, c, . .)로 표시되는 두 개 이상의 정수 a, b, c, . .의 최소공배수도 적절하게 정의됩니다.이것은 a, b, c, ...[1] 각각으로 나누어질 수 있는 최소 양의 정수입니다.

개요

숫자의 배수는 해당 숫자와 정수의 입니다.예를 들어, 5 × 2 = 10이므로 10은 5와 2로 나누어집니다.10은 5와 2로 나눌 수 있는 최소 양의 정수이므로 5와 2의 최소 공배수입니다.같은 원리로 10은 -5와 -2의 최소공배수이기도 하다.

표기법

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

4의 배수:

6의 배수:

4와 6의 공통배수는 두 목록에 있는 숫자입니다.

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

적용들

단순 분수를 더하거나, 빼거나, 비교할 때, 분모의 최소 공배수(종종 최소 공분모라고 함)가 사용됩니다. 왜냐하면 각 분수는 이 분모로 분수로 표현될 수 있기 때문입니다.예를들면,

분모 42는 21과 6의 최소공배수이기 때문에 사용된 것입니다.

기어 문제

기계에 각각 m과 n개의 톱니가 있는개의 맞물림 기어가 있고 기어가 첫 번째 기어의 중심에서 두 번째 기어의 중심까지 그려진 선 세그먼트로 표시된다고 가정합니다.기어가 회전하기 시작하면 라인 세그먼트를 재정렬하기 위해 첫 번째 기어가 완료해야 하는 회전 수는 µ (를 사용하여 계산할 수 있습니다. 첫 번째 기어는 m( 스타일 ( m (\display style \operatorname {lcm} m, n 하여 계산해야 합니다.이때까지 두 번째 기어는 µ ( \ \n을 회전합니다.

유성 정렬

한 별 주위를 공전하는 세 개의 행성이 있다고 가정해 봅시다. 이 행성은 궤도를 완성하는 데 각각 l, m, n개의 시간 단위가 걸린다.l, mn정수라고 가정합니다.행성이 최초 선형 정렬 후 항성 주위를 움직이기 시작했다고 가정하면 모든 행성은 µ ( , ,)(\style \ (l , 단위 시간 후에 다시 선형 정렬에 도달합니다.이 시점에서 첫 번째, 두 번째 및 세 번째 행성은 ( , , ) }( , ,), ( , , ) style \} ( ,, )를 완료합니다.[5]주위를 돌다

계산

최대 공약수 사용

최소공배수는 다음 공식으로 최대공약수(gcd)에서 계산할 수 있다.

결과보다 큰 정수가 유입되지 않도록 동일한 공식을 사용하는 것이 편리합니다.

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

이러한 공식은 gcd(a, 0) = a이므로 a와 b 중 하나가 정확히 0일 때도 유효합니다. 그러나 a와 b가 모두 0이면 이러한 공식은 0으로 나눗셈을 일으키므로 lcm(0, 0) = 0을 특수한 경우로 간주해야 합니다.

위의 예시로 돌아가기 위해

gcd를 계산하기 위한 유클리드 알고리즘과 같이 인수가 필요하지 않은 빠른 알고리즘이 있다.매우 큰 정수의 경우 관련된 세 가지 연산(곱셈, gcd 및 나눗셈)에 대해 더 빠른 알고리즘이 있습니다. 빠른 곱셈을 참조하십시오.이러한 알고리즘은 유사한 크기의 인자로 더 효율적이기 때문에 위의 예시와 같이 lcm의 가장 큰 인수를 인수의 gcd로 나누는 것이 더 효율적입니다.

소인수분해 사용

독특한 인수분해 정리는 1보다 큰 모든 양의 정수는 소수의 곱으로 단 한 가지 방법으로만 쓸 수 있다는 것을 나타낸다.소수는 결합하면 합성수를 구성하는 원자 원소로 간주할 수 있다.

예를 들어 다음과 같습니다.

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

이 사실을 사용하여 숫자 집합의 lcm를 찾을 수 있습니다.

예: lcm(8,9,21)

각 숫자를 인수분해 소수 거듭제곱의 곱으로 표현합니다.

lcm는 각 소수의 최대 제곱을 곱한 곱입니다.3개의 소수 2, 3, 7의 최대 제곱은 각각3 2, 32, 7이다1.따라서,

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

동일한 방법은 각 원에서 시연된 두 숫자의 소인수 분해와 교차로에서 공통되는 모든 인자를 사용하여 다음과 같은 벤 다이어그램으로도 설명할 수 있다.lcm는 다이어그램의 모든 소수를 곱하면 알 수 있습니다.

다음은 예를 제시하겠습니다.

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

2개의 "2"와 "3"을 공유합니다.

Least common multiple.svg
최소공배수 = 2 × 2 × 2 × 3 × 5 = 720
최대 공약수 = 2 × 2 × 3 = 12

는 또한 최대공약수(gcd)에도 작용하지만, 벤 다이어그램의 모든 숫자를 곱하는 대신 교차점에 있는 소인수만 곱하는 것을 제외한다.따라서 48과 180의 gcd는 2 × 2 × 3 = 12이다.

단순 알고리즘 사용

이 방법은 여러 [citation needed]정수의 lcm를 쉽게 찾을 수 있습니다.

양의 정수 X = (x1, x2, ..., xn), n > 1의 유한한 수열이 있다고 가정하자.알고리즘은 다음과 같은 단계로 진행됩니다. 각 단계 m에서 X = (x1(m)2(m)n(m), x, ..., x(1)), X = X의 시퀀스(m) 검사하고 업데이트합니다. 여기(m) X는 X의 m번째 반복, 알고리즘의 단계 m에서의 X입니다.이 검사의 목적은 시퀀스(m) X에서 가장 작은(많은 요소 중 하나일 수 있음) 요소를 선택하는 것입니다.x가 선택된 요소라고 가정하면k0(m) 시퀀스(m+1) X는 다음과 같이 정의됩니다.

xk(m+1) = xk(m), kk0
xk0(m+1) = xk0(m) + xk0(1) 입니다.

즉, 최소 요소는 대응하는 x만큼 증가하지만 나머지 요소는 변경되지 않고 X에서(m) X로 전달됩니다(m+1).

시퀀스(m) X의 모든 요소가 동일하면 알고리즘은 정지합니다.이들의 공통값 L은 정확히 lcm(X)입니다.

예를 들어, X(1) = X = (3, 4, 6)인 경우 알고리즘의 단계는 다음을 생성합니다.

X(2) = (6, 4, 6 )
X(3) = (6, 8, 6 )
X(4) = (6, 8, 12) - 두 번째 6을 선택하여
X(5) = (9, 8, 12)
X(6) = (9, 12, 12)
X(7) = (12, 12, 12)이므로 lcm = 12.

테이블 방식 사용

이 방법은 임의의 숫자에 적용됩니다.우선 모든 번호를 테이블(이 예에서는 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가 적어도1개의 숫자를 나누었다고 가정하면(이 예시와 같이), 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이다.

일반적인 계산 알고리즘으로서 위의 것은 매우 비효율적입니다.소프트웨어에서는 구현하고 싶지 않습니다.이것에 너무 많은 스텝과 스토리지 공간이 필요하기 때문입니다.유클리드의 알고리즘을 사용하여 먼저 gcd를 계산한 후 lcm를 나눗셈으로 구함으로써 훨씬 더 효율적인 수치 알고리즘을 얻을 수 있다.

수식

산술의 기본 정리

산술의 기본정리에 따르면, 1보다 큰 모든 정수는 소수의 곱으로 다음과 같은 인자의 순서까지 고유하게 표현될 수 있다.

여기서 지수2 n, n3, ...은 음이 아닌 정수입니다. 예를 들어 84 = 221 30 51 7 110 130...

2개의 양의 a a \ _ { p } { _ {} b \ b = \ _ { p } p^ {}b = ∏ p p { p { { { div div and and div div div and div div div div and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and

그리고.

부터

이것은 준다

사실, 모든 유리수는 음의 지수를 허용한다면 소수들의 곱으로 독특하게 쓸 수 있다.이 작업을 수행해도 위의 공식은 계속 유효합니다.예를 들어 다음과 같습니다.

격자 이론

양의 정수는 부분적으로 나눗셈으로 정렬할 수 있습니다.a가 b를 나누면(즉, b가 a의 정수 배수인 경우) a b b(또는 동등하게 b a a)를 씁니다.(일반적인 매그니튜드 베이스의 정의는 여기서 사용되지 않습니다).

이 순서에서 양의 정수는 격자가 되고 gcd에 의해 만남이 주어지고 lcm에 의해 결합이 주어집니다.증명은 다소 지루하지만 간단합니다.lcm와 gcd가 meet와 join의 공리를 만족하는지 확인하는 것과 같습니다.lcm와 gcd를 보다 일반적인 콘텍스트에 포함시키면 이들 사이에 이중성이 확립됩니다.

정수 변수 gcd, lcm, θ θ를 포함하는 공식도 참일 경우 gcd를 lcm로 전환하고 θ를 θ로 전환한 공식도 참입니다(기억 is은 나눗셈으로 정의).

다음 이중 공식 쌍은 일반적인 격자-이론적 동일성의 특수한 경우이다.

가환법칙
연합법
흡수 법칙
등가법칙
lcm와 gcd의 관점에서 나눗셈을 정의합니다.

또한 이 격자가 분포임을 알[6] 수 있습니다.즉, lcm는 gcd에, gcd는 lcm에 걸쳐 분포합니다.

이 아이덴티티는 자기 이중화입니다.

다른.

  • D를 θ(D) 고유 소수(즉, D제곱 프리)의 곱이라고 하자.

그럼[7].

여기서 절대 막대는 세트의 카디널리티를 나타냅니다.

  • 1 , 가 0이 아닌 경우
[8][9]

가환환 내

최소공배수는 일반적으로 다음과 같이 가환환에 대해 정의할 수 있습니다.a와 b를 교환환 R의 원소로 한다.ab의 공통배수는 ab가 모두 m을 나누도록 하는 R의 원소 m이다(즉, Ax = m 및 = m만큼 R원소 x와 y가 존재한다).ab의 최소공배수는 a와 b의 다른 공통배수 n에 대해 mn을 나눈다는 점에서 최소공배수입니다.

일반적으로 교환 링 내의 2개의 요소는 적어도 공통의 복수 또는 복수의 요소를 가질 수 없습니다.단, 동일한 요소 쌍의 최소 공배수 2개가 관련지어집니다.하나의 인수분해 영역에서는 임의의 2개의 원소가 최소공배수를 가진다.주요 이상 영역에서 ab의 최소공배수는 a와 b에 의해 생성된 이상 교점의 발생원으로 특징지을 수 있다(이상 집합의 교점은 항상 이상이다).

「 」를 참조해 주세요.

메모들

  1. ^ a b c Weisstein, Eric W. "Least Common Multiple". mathworld.wolfram.com. Retrieved 2020-08-30.
  2. ^ Hardy & Wright, © 5.1, 페이지 48
  3. ^ a b (1972년, 페이지 39)
  4. ^ Pettofrezzo &, Byrkit(1970년 p. 56).
  5. ^ "nasa spacemath" (PDF).
  6. ^ 다음 3공식 란다우,. III.3, 254p. 출신이다.
  7. ^ Crandall&Pomerance, 전 남편 2.4페이지의 주 101.
  8. ^ 롱(1972년, p. 41)
  9. ^ Pettofrezzo &, Byrkit(1970년 p. 58).

레퍼런스