최대공약수와 최소공배수 // cublr's warehouse

이런 것들은 초등학교 때 배웠던 건데, 은근히 프로그래밍 퀴즈에서 많이 나오니까 정리를 해 두는 것이 좋겠다.

약수, 공약수, 최대공약수

먼저 약수(divisor)에 대해 생각해 보자. 약수는 어떤 수가 있을때, 그 어떤 수를 나누어 떨어지게 하는 수를 말한다. 예를 들어 4의 약수는 1,2,4가 있는데 4를 이 약수들로 나누어 보면 나머지가 0이 되는 것을 알 수 있다.

그러면 공약수(common divisor)에 대해 생각해 보자. 두 수가 있을때, 두 수 모두를 나누어 떨어지게 하는 “공통인 약수"가 있을 것이다. 이를 공약수라고 부른다. 예를 들어 2와 4의 공약수는 [1,2]가 된다.

그렇다면 최대공약수(greatest common divisor)는 또 무엇인지에 대해 생각해 보자. 이는 두 수의 공약수 중 제일 큰 약수를 말한다. 2와 4의 최대공약수는 2가 된다.

24의 약수: [2, 3, 4, 6, 8, 12, 24]
36의 약수: [2, 3, 4, 6, 8, 9, 12, 18, 36]
두 수의 공약수: [2, 3, 4, 6, 8, 12]
최대공약수: [12]

이런 정의에 비추어보았을 때 최소공약수는 별로 의미가 없다는걸 알 수 있다. 항상 1이 될테니까.

먼저 배수(multiple)을 생각해 보자. 배수는 어떤 수에 “정수"를 곱한 수이다. 즉 어떤 수 n에 대해 대해서 1, 2, 3, …, m을 곱해나가는 결과를 말하는 것이다. 즉 2의 배수는 [2, 4, 6, 8, …] 이 될 것이다.

그러면 공배수(common multiple)에 대해 생각해 보자. 공약수와 비슷하게도, 두 수의 배수 중에서 공통된 배수를 말한다. 2와 4의 공배수는 [4, 8, 12, …]가 될 것이다.

그렇다면 최소공배수(least common multiple/lowest common multiple)은 무엇인가? 공배수 중 제일 작은 것을 말한다. 2와 4의 최소공배수는 당연히 4가 된다.

24의 배수: [24, 48, 72, 96, 120, 144, ...]
36의 배수: [36, 72, 108, 144, ...]
공배수: [72, 144, ...]
최소공배수: [72]

마찬가지로 이렇게 두고 보면 최대공배수는 큰 의미가 없다는 것을 알 수 있다. 무한대가 될 테니까.

이번에는 소인수분해에 대해서 생각해 보자. 소인수분해란 어떤 수를 소수에 대한 곱으로 나타내는 것을 말한다. 예를 들어 6은 소수 2와 3의 곱으로 나타낼 수 있다.

6의 소인수분해 결과: 2*3
15의 소인수분해 결과: 3*5
...

소인수분해 24: 2*2*2*3
소인수분해 36: 2*2*3*3

숫자의 출현을 테이블로 그럴듯하게 배치해 보자. 그러면 최대공약수와 최소공배수를 계산할 수 있다.

최소공약수는 중복해서 출현하는 수만 곱하면 알 수 있다. 최대공약수는 한 번이라도 출현하면 곱하는 것으로 한다. 따라서 최대공약수는 2*2*3=12, 최소공배수는 2*2*2*3*3=72가 된다.

24와 36의 곱은 864이다. 최소공배수와 최대공약수의 곱은 두 수의 곱과 같다. 그러니까 두 수 A와 B의 곱은 A와 B의 최대공약수 G와 최소공배수 L의 곱과 같다는 것이다.

A * B = G * L

따라서 최대공약수를 알고 두 수의 곱을 아는 경우, 최소공배수도 알 수 있다.

뭐 이런 식으로 알 수 있겠다…