최소공배수 구하는 법 - 여러가지 방법 비교

지난 번에는 최대공약수에 대해 알아보았습니다. 이번에는 최소공배수에 대해 생각해 봅시다.

 

최소공배수란?

최소공배수는 한자로 最小公倍數라고 씁니다.

• 最小: 가장 작은
• 公倍數: 공통의 배수
• 倍數: 곱한 수

즉, 공배수(곱한 수들 중 같은 수, 배수중 공통이 되는 수) 중 가장 작은 수라는 뜻입니다.
한편, 최소공배수를 영어로는 Least Common Multiple이라고 부릅니다. (줄여서, LCM)

• Multiple = 곱한 수 = 배수
• Common = 공통의
• Least = 최소의

마찬가지로, 공통의 배수 중 가장 작은 값이라는 의미가 되겠습니다.

 

최대공약수, 최소공약수, 최소공배수, 최대공배수

우리가 아는 용어는 최대공약수와 최소공배수입니다. 그런데, 개념적으로 보면 최대/최소라는 말을 붙여도 되긴 하지만 왜 최대공약수와 최소공배수만 의미가 있는지 짚어보죠.

8이라는 숫자를 예로 들어 살펴보겠습니다.

• 8의 약수: 1, 2, 4, 8
• 8의 배수: 8, 16, 24, 32, 40, 48, ...

약수의 집합은 끝이 정해져 있습니다. 반면 배수의 집합은 끝이 정해져 있지 않습니다. 끝이 정해져 있는 집합에서는 최소와 최대를 찾을 수 있지만, 끝이 정해져 있지 않은 집합에서는 최소만 의미를 부여할 수 있겠죠. 그런데, 약수의 특성상 최소는 항상 1입니다. 따라서, 최대값이 유의미합니다. 이 내용은 공약수와 공배수에도 적용됩니다. 결국, 공약수에서는 최대공약수가, 공배수에는 최소공배수가 중요합니다.

 

방법-1

각각의 배수를 적어보고, 가장 첫번째 나오는 공배수가 최소공배수입니다.

• 30의 배수: 30, 60, 90, 120, 150, 180, ...
• 12의 배수: 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, ...

따라서,

• 30과 12의 공배수: 60, 120, ...

첫번째 나오는 수가 최소공배수이므로, 최소공배수는 30입니다.

 

방법-2

각 숫자를 소인수분해합니다. 큰 수를 포함해야 하므로, 같은 수가 공통으로 나타난다면 지수가 더 큰 수를 택하고, 한 쪽에만 나타난다면 그 수를 택해서 곱해줍니다. (약수에서는 공통된 수가 나타나면 지수가 작은 수를 택했고, 한 쪽에만 나타나면 제외했었습니다.)

$ 30 = 2 \times 3 \times 5 $
$ 12 = 2^2 \times 3 $

위에 언급한 2와 $ 2^2$ 를 두고 생각해 보면, 2와 4의 관계는 4가 2를 두 개 품고 있는 숫자입니다. 따라서, 공약수를 구할 때는 2를 택해야 하지만, 공배수를 구할 때는 $2^2$를 택하는 것이라 생각하면 됩니다. 따라서, $ 2^2 \times 3 \times 5 = 60 $ 가 됩니다.

 

방법-3

다음 방법은 소인수분해로 풀기입니다.

2 ) 30 12
3 ) 15   6
       5   2

서로 소인 두 수가 나올 때까지 소인수분해를 반복한 후, 모든 수(약수들과 서로소인 나머지 수들)를 곱합니다.
$ 2 \times 3 \times 5 \times 2 = 2^2 \times 3 \times 5 = 60 $ 이 최소공배수가 됩니다.

 

방법-4

최대공약수와의 최소공배수가 어떤 관계인지를 알면, 다음과 같이 구할 수도 있습니다.

$ A = a \times b \times c $
$ B = a^2 \times b $

라고 하면, 두 수를 곱하면 좌변의 곱 = 우변의 곱이므로,

$ A \times B = a \times b \times c \times a^2 b $ 가 됩니다.

그런데, 정의에 따라
$ gcd = a \times b $
$ lcm = a^2 \times b \times c $

따라서, $ A \times B = gcd \times lcm $ 이고,

$ lcm = A \times B \div gcd $ 가 됩니다.

즉, 최소공배수 = 두 수를 곱한 값을 최대공약수로 나눈 값입니다.
위에서 예로 든 숫자로 확인해 봅시다.

• 30과 12의 최대공약수 = 6
• 30과 12의 최소공배수 = 두 수의 곱/ 최대공약수 = $ 30 \times 12 \div 6 = 60 $

이상 여러가지 방법으로 최소공배수 구하는 법을 정리해봤습니다.

 

참고

최대공약수 구하는법 - 여러가지 방법 비교

서로소, 소수 (prime number) - 다시 생각해 봅시다