이곳은 개발을 위한 베타 사이트 입니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
최소공배수
덤프버전 :
1. 개요[편집]
最小公倍數 · least common multiple, LCM
초등학교 5학년 때 약수(divisor or factor)와 배수(multiple)를 배운 뒤에 최대공약수(greatest common divisor or greatest common factor) 와 함께 배우게 되는 내용. 공배수(common multiple)란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수(least common multiple)는 당연히 공배수 중에서 가장 작은 것. 두 수 [math(a,b)]의 최소공배수를 기호로 [math(\text{lcm}\left(a,b\right))] 혹은 [math(\text{LCM}\left(a,b\right))]로 표기하며,[1] 더욱 줄이면 [math(\left[a,\,b\right])]로 표기하기도 한다.[2]
간혹 최대공배수로 잘못 부르는 경우가 있는데, 최대공배수는 존재하지 않는다. 공배수는 한없이 커지므로, 가장 큰 숫자를 정의할 수 없기 때문. 마찬가지로 최소공약수 또한 어떤 수 집합이든 무조건 1이므로 의미가 없다.
2. 찾는 법[편집]
예시로 두 수 10, 12의 공배수를 찾고 싶다고 하자. 먼저 두 수의 배수를 쭉 나열한다.
여기서 위아랫줄 동시에 나타나는 수가 바로 공배수이다. 최소공배수는 앞서 설명했듯이 공배수 중 가장 작은 것. 이 예시의 경우에는 60이 최소공배수가 된다. 같은 방법으로 세 수 이상의 최소공배수도 구할 수 있다.10: 10, 20, 30, 40, 50, 60, 70, ...
12: 12, 24, 36, 48, 60, 72, ...
하지만 숫자를 나열하는 방법으로 최소공배수를 찾는게 힘들다면? 이 때는 소인수분해를 이용해서 최소공배수를 찾는다. 10과 12를 각각 소인수분해하면,
이제 중복되는 소인수는 차수가 큰 횟수만큼, 그리고 나머지 소인수를 모두 곱해주면 그 값이 최소공배수이다. 위 예시에서는 2를 두 번,[3] 3을 한 번, 그리고 5를 한 번 곱한 값, 즉 60이 최소공배수가 된다. 특히, 숫자가 서로소이면, 그냥 아무런 생각도 하지않고 두 수를 곱해주기만 하면 그 값이 최소공배수가 됨을 알 수 있다.[math(10=2\cdot5)]
[math(12=2^2\cdot3)]
위에서 봤듯이 최소공배수는 대수학적으로는 그 성질을 다루기가 매우 까다롭기 때문에 특수함수에 속한다.
최대공약수 [math(\gcd)]를 이용하는 방법도 있다. 최대공약수와 다음과 같은 관계가 성립한다:
[math(\mathrm{lcm}(a,\,b) = \dfrac{|ab|}{\gcd(a,\,b)})]
단, 최대공약수도 최소공배수도 모를 경우 순환논법이 될 수 있음을 주의해야 한다.
세 수 이상의 최소공배수를 구하려면 다음과 같이 함수를 계속 취해주면 된다.
세 수 [math(a,\,b,\,c)]에 대해서
[math(\mathrm{lcm}(a,\, b,\, c) = \mathrm{lcm}(\mathrm{lcm}(a,\, b),\, c) \equiv \dfrac{| abc |}{\gcd\left( \frac{| ab |}{\gcd(a,\,b)},\, c \right)})]
이 성립한다.
3. 성질[편집]
두 정수 [math(a,b)]에 대하여,
- [math(\text{lcm}\left(a,b\right)\mid ab)]
- [math(\text{lcm}\left(a,b\right)\gcd\left(a,b\right)=ab)]
- [math(a\mid \text{lcm}\left(a,b\right))]
- [math(b\mid \text{lcm}\left(a,b\right))]
4. 증명[편집]
1. [math(\gcd\left(a,b\right)=G)]라 하자. 그럼 적당한 정수 [math(m)], [math(n)]에 대해 [math(a=Gm,b=Gn)], ([math(m,n)]은 서로소)가 성립한다. 이때, lcm[math(\left(a,b\right)=Gmn)]이다. 따라서, [math(\text{lcm}\left(a,b\right)=Gmn\mid G^2mn=ab)]
2. [math(\gcd\left(a,b\right)=G)]라 하자. 그럼 적당한 정수 [math(m,n)]에 대해 [math(a=Gm)], [math(b=Gn)], ([math(m,n)]은 서로소)가 성립한다. 이때, [math(\text{lcm}\left(a,b\right)=Gmn)]이다. 따라서, [math(\text{lcm}\left(a,b\right)\gcd\left(a,b\right)=G^{2}mn=ab)]