수학에서 자주 등장하는 최대공약수(GCD)와 최소공배수(LCM)는 수의 관계를 이해하고 문제를 해결하는 데 있어 중요한 개념입니다. 특히 중고등학교 수학, 수학 경시대회, 또는 코딩 테스트 등 다양한 상황에서 활용됩니다. 이번 글에서는 최대공약수와 최소공배수를 구하는 공식과 함께, 직접적인 예시를 통해 이해를 도와드리겠습니다.
최대공약수(GCD)란?
최대공약수(Greatest Common Divisor)는 두 수 또는 그 이상의 수에서 공통적으로 나누어지는 가장 큰 수를 말합니다. 예를 들어 12와 18의 공약수는 1, 2, 3, 6이고, 이 중 가장 큰 수는 6이므로 최대공약수는 6입니다.
최대공약수 구하는 공식 (유클리드 호제법)
두 자연수 a, b에 대해 a > b일 때, 다음의 과정을 반복합니다:
\[ GCD(a, b) = GCD(b, a \mod b) \]
나머지가 0이 될 때까지 이 과정을 반복하며, 마지막에 0이 아닌 수가 바로 최대공약수입니다.
예시: 48과 18의 최대공약수
48 % 18 = 12
18 % 12 = 6
12 % 6 = 0 → 따라서 GCD는 6입니다.
최소공배수(LCM)란?
최소공배수(Least Common Multiple)는 두 수 또는 그 이상의 수에서 공통적으로 나누어 떨어지는 가장 작은 수를 말합니다. 예를 들어 4와 6의 공배수는 12, 24, 36… 이고, 이 중 가장 작은 공배수는 12입니다.
최소공배수 구하는 공식
두 수 a, b의 최소공배수는 최대공약수를 이용해 다음과 같이 구할 수 있습니다:
\[ LCM(a, b) = \frac{a \times b}{GCD(a, b)} \]
예시: 12와 18의 최소공배수
먼저 GCD(12, 18)를 구합니다: 6
그러면
\[ LCM(12, 18) = \frac{12 \times 18}{6} = 36 \]
따라서 최소공배수는 36입니다.
최대공약수와 최소공배수의 성질
– 두 수의 곱 = 최대공약수 × 최소공배수
– 서로소인 두 수의 최대공약수는 1, 최소공배수는 두 수의 곱
– 여러 수의 최대공약수/최소공배수도 확장된 유클리드 호제법으로 구할 수 있음
파이썬 코드로 구현하기
프로그래밍에서도 GCD와 LCM 계산은 자주 사용됩니다. 파이썬에서는 내장 모듈을 활용해 간단하게 구현할 수 있습니다.
import math
a = 12
b = 18
# 최대공약수
gcd = math.gcd(a, b)
print("최대공약수:", gcd)
# 최소공배수
lcm = a * b // gcd
print("최소공배수:", lcm)자주 쓰이는 문제 유형
1. 여러 개의 수의 최대공약수/최소공배수 구하기
2. 어떤 조건을 만족하는 최소공배수 찾기
3. 두 수의 공약수나 공배수를 모두 나열하기
4. 서로소 여부 판단하기
결론
최대공약수(GCD): 두 수에서 공통으로 나눌 수 있는 가장 큰 수이며, 유클리드 호제법으로 쉽게 구할 수 있습니다.
최소공배수(LCM): 두 수가 공통으로 가지는 가장 작은 배수로, GCD를 이용해 간단하게 계산할 수 있습니다.
공식 요약: GCD(a, b) = GCD(b, a mod b), LCM(a, b) = (a × b) / GCD(a, b)
활용: 수학 문제는 물론, 알고리즘과 프로그래밍에서도 활용도가 매우 높습니다.