홍라이프 계산기최대공약수·최소공배수 계산 쉽게 이해하기 — 개념과 원리
최대공약수는 여러 수를 모두 나누어떨어지게 하는 가장 큰 자연수이고, 최소공배수는 여러 수의 공통인 배수 중 가장 작은 자연수입니다. 최대공약수는 분수를 약분하거나 물건을 남김없이 똑같이 나눌 때, 최소공배수는 통분하거나 12분, 18분 간격으로 출발하는 두 버스가 언제 다시 함께 출발하는지 구할 때처럼 주기가 겹치는 때를 찾을 때 씁니다.
계산 방법
- 최대공약수는 유클리드 호제법으로 구합니다. GCD(a, b) = GCD(b, a를 b로 나눈 나머지)를 나머지가 0이 될 때까지 되풀이하며, 마지막으로 0이 아닌 수가 답입니다.
- 최소공배수는 두 수일 때 LCM(a, b) = |a × b| ÷ GCD(a, b)입니다.
- 수가 세 개 이상이면 두 수씩 차례로 적용합니다. GCD(a, b, c) = GCD(GCD(a, b), c)이고 최소공배수도 같습니다.
입력값은 정수로 반올림합니다.
원리
a와 b를 모두 나누는 수는 a − b도 나누므로, a를 b로 나눈 나머지도 나눕니다. 따라서 (a, b)와 (b, 나머지)는 공약수가 완전히 같고, 수는 단계마다 작아지다가 답에 이릅니다. 최소공배수 공식은 소인수분해로 이해할 수 있습니다. 최대공약수는 각 소인수의 작은 지수를, 최소공배수는 큰 지수를 택하는데, 작은 지수와 큰 지수의 합은 두 지수의 합과 같으므로 최대공약수 × 최소공배수 = a × b가 됩니다.
예제 풀이
- 입력값: 12, 18, 30입니다.
- GCD(12, 18): 18 = 1 × 12 + 6, 12 = 2 × 6 + 0이므로 6입니다. 이어서 GCD(6, 30) = 6이므로 최대공약수는 6입니다.
- LCM(12, 18) = 216 ÷ 6 = 36입니다.
- LCM(36, 30) = 1080 ÷ GCD(36, 30) = 1080 ÷ 6 = 180이므로 최소공배수는 180입니다.
- 소인수분해로 검산하면 12 = 2²·3, 18 = 2·3², 30 = 2·3·5입니다. 작은 지수끼리 곱하면 2·3 = 6, 큰 지수끼리 곱하면 2²·3²·5 = 180입니다.
결과 해석
최대공약수가 1이면 두 수는 서로소이며, 그 두 수로 만든 분수는 이미 기약분수입니다. 최소공배수는 항상 가장 큰 입력값 이상이고, 어느 두 수도 서로소일 때에만 모든 수의 곱과 같아집니다. 앞의 버스 예에서는 12와 18의 최소공배수인 36분마다 두 버스가 함께 출발합니다.
흔한 실수
- 두 개념을 혼동합니다. 최대공약수는 가장 작은 수보다 클 수 없고, 최소공배수는 가장 큰 수보다 작을 수 없습니다.
- 최대공약수 × 최소공배수 = 두 수의 곱이라는 관계를 세 수 이상에 적용합니다. 두 수일 때만 성립합니다.
- 약수를 손으로 나열하다가 빠뜨립니다. 호제법을 쓰면 이런 실수를 막을 수 있습니다.
자주 묻는 질문
어떤 수와 0의 최대공약수는 무엇인가요?
모든 수는 0을 나누므로 GCD(a, 0) = |a|입니다. 0이 포함된 최소공배수는 보통 0으로 정의합니다.
큰 두 수의 최대공약수를 손으로 구하려면 어떻게 하나요?
큰 수를 작은 수로 나누고, 큰 수를 나머지로 바꾸는 과정을 나머지가 0이 될 때까지 반복하면 됩니다.
공약수와 공배수는 몇 개나 있나요?
공약수는 최대공약수의 약수이므로 개수가 정해져 있고, 공배수는 최소공배수의 배수이므로 끝없이 많습니다.
출처: Euclid, Elements, Book VII 명제 1–3, 34 · D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 4.5.2절