최소공배수

최근 수정 시각: (5년 전)
분류
목차
1. 개요2. 찾는 법3. 성질4. 증명5. 관련 문서

1. 개요 [편집]

Least Common Multiple, LCM · 最小公倍數

초등학교에서 약수 (divisor or factor) 와 배수 (multiple) 를 배운 뒤에 최대공약수 (greatest common divisor or greatest common factor) 와 함께 배우게 되는 내용. 공배수 (common multiple) 란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수 (least common multiple) 는 당연히 공배수 중에서 가장 작은 것. 두 수 a,ba,b의 최소공배수를 기호로 lcm(a,b)\text{lcm}\left(a,b\right)로 표기하며,[1] 더욱 줄이면 [a, b]\left[a,\,b\right]로 표기하기도 한다.[2]

간혹 최대공배수로 잘못 부르는 경우가 있는데, 최대공배수는 존재하지 않는다. 공배수는 한없이 커지므로, 가장 큰 숫자를 정의할 수 없기 때문.

2. 찾는 법 [편집]

예시로 두 수 10, 12의 공배수를 찾고 싶다고 하자. 먼저 두 수의 배수를 쭉 나열한다.
10: 10, 20, 30, 40, 50, 60, 70, ...
12: 12, 24, 36, 48, 60, 72, ...
여기서 위아랫줄 동시에 나타나는 수가 바로 공배수이다. 최소공배수는 앞서 설명했듯이 공배수 중 가장 작은 것. 이 예시의 경우에는 60이 최소공배수가 된다. 예로 60갑자는 10갑(갑을병정...)과 12자(자축인묘...)의 조합을 의미하는 것으로, 60가지의 조합이 있어 60갑자라고 부르는 것이다. 이처럼 최소공배수는 나열에 해당하는 경우의 수를 구할 때 사용한다.

하지만 숫자를 나열하는 방법으로 최소공배수를 찾는게 힘들다면? 이 때는 소인수분해를 이용해서 최소공배수를 찾는다. 10과 12를 각각 소인수분해하면,
10=2⋅510=2\cdot5
12=22⋅312=2^2\cdot3
이제 중복되는 소인수는 차수가 큰 횟수만큼, 그리고 나머지 소인수를 모두 곱해주면 그 값이 최소공배수이다. 위 예시에서는 2를 두 번,[3] 3을 한 번, 그리고 5를 한 번 곱한 값, 즉 60이 최소공배수가 된다. 특히, 숫자가 서로소이면, 그냥 아무런 생각도 하지않고 두 수를 곱해주기만 하면 그 값이 최소공배수가 됨을 알 수 있다.

위에서 봤듯이 최소공배수는 대수학적으로는 그 성질을 다루기가 매우 까다롭기 때문에 특수함수에 속한다.

최대공약수 gcd⁡\gcd를 이용하는 방법도 있다. 최대공약수와 다음과 같은 관계가 성립한다:
lcm(a, b)=∣ab∣gcd⁡(a, b)\mathrm{lcm}(a,\,b) = \dfrac{|ab|}{\gcd(a,\,b)}
단, 최대공약수도 최소공배수도 모를 경우 순환논법이 될 수 있음을 주의해야 한다.

3. 성질 [편집]

두 정수 a,ba,b에 대하여,
  1. lcm(a,b)∣ab\text{lcm}\left(a,b\right)\mid ab
  2. lcm(a,b)gcd⁡(a,b)=ab\text{lcm}\left(a,b\right)\gcd\left(a,b\right)=ab
  3. a∣lcm(a,b)a\mid \text{lcm}\left(a,b\right)
  4. b∣lcm(a,b)b\mid \text{lcm}\left(a,b\right)
최대공약수는 성질이 많은데 얘는... 그나마 있는 하나도 최대공약수가 끼어있다.

4. 증명 [편집]

1. gcd⁡(a,b)=G\gcd\left(a,b\right)=G라 하자. 그럼 적당한 정수 mm, nn에 대해 a=Gm,b=Gna=Gm,b=Gn, (m,nm,n은 서로소)가 성립한다. 이 때, lcm(a,b)=Gmn\left(a,b\right)=Gmn이다. 따라서, lcm(a,b)=Gmn∣G2mn=ab\text{lcm}\left(a,b\right)=Gmn\mid G^2mn=ab

2. gcd⁡(a,b)=G\gcd\left(a,b\right)=G라 하자. 그럼 적당한 정수 m,nm,n에 대해 a=Gma=Gm, b=Gnb=Gn, (m,nm,n은 서로소)가 성립한다. 이 때, lcm(a,b)=Gmn\text{lcm}\left(a,b\right)=Gmn이다. 따라서, lcm(a,b)gcd⁡(a,b)=G2mn=ab\text{lcm}\left(a,b\right)\gcd\left(a,b\right)=G^{2}mn=ab

5. 관련 문서 [편집]

[1] lcm\text{lcm}은 Least Common Multiple의 줄임말[2] 다만 [a, b]\left[a,\,b\right]은 폐구간 표현과 겹치므로 사용에 주의할 필요가 있다.[3] 2는 중복되는 소인수인데, 12쪽의 2가 차수가 크므로 그 차수만큼(2번) 곱해준다. 콩까지마

라이선스를 별도로 명시하지 않은 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다.
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

문서의 기여자는 역사 탭에서 확인할 수 있습니다.
접두어의 N: - 나무위키 사용자, R: - 리그베다 위키의 사용자를 뜻합니다.
자세한 사항은 나무위키에서 동일한 문서의 역사를 참고하시기 바랍니다.