최대공약수(Greatest Common Divisor; GCD)
공약수는 두 개 이상의 자연수의 약수 중 공통된 수다. 최대공약수는 공약수 중 가장 큰 수를 말한다.
두 수의 최대공약수가 1이면 서로소(coprime; relatively prime)이라 한다.
최대공약수를 구하는 가장 쉬운 방법은 두 수의 공약수 중 가장 큰 것을 선택하는 것이다. 예를 들어, 8과 12의 최대공약수를 구한다면, 각 수의 약수는 다음과 같다.
- 8 : 1, 2, 4, 8
- 12 : 1, 2, 3, 4, 6, 12
두 수의 공약수는 1, 2, 4 이다. 이중 가장 큰 수는 4이므로 4가 최대공약수다.
혹은 소인수 분해(prime factorial)의 결과의 차수 중 작은 것을 선택한 뒤 곱한다. 예를 들어 8의 소인수 분해 결과인 2³과 12의 소인수 분해 결과인 2² 3¹에서 작은 차수를 선택하면 2² 3⁰ 이 된다. 따라서 최대공약수는 4가 된다.
유클리드 알고리즘(Euclidean algorithm; 유클리드 호제법)
위의 방법들은 간단하게 생각하여 구할 수 있지만, 코드로 구현하면 계산이 많아진다는 문제점이 있다. 따라서 유클리드 알고리즘이 많이 쓰인다. 유클리드 알고리즘은 두 가지 사실을 바탕으로 만들어졌다.
-
b|a(b가 a의 인수나 약수이고, a가 b의 배수) 이면gcd(a, b) = b이다. -
a = bt + r을 만족하는 정수t와r이 있으면gcd(a, b) = gcd(b, r)이다.
우선 첫째로, a가 b의 배수라는 것은 a가 b로 나누어떨어진다는 것이다. 이 경우 a = bk를 만족하는 정수 k 가 존재한다. bk와 b의 최대공약수는 b이다. 즉, gcd(bk, b) = b 이기 때문에 1번이 성립한다.
2번 명제는 gcd(a, b) = gcd(bt+r, b) = gcd(b, r)로 정리해볼 수 있다. bt는b로 나누어떨어질 것이기 때문에 b의 모든 약수로 나눌 수 있다. 따라서 a와 b의 공약수는 r에 의해서 결정된다. 즉, a가 b로 나누어떨어지고, 나머지가 r일 경우 gcd(b, r)이 되는 것이다.
유클리드 알고리즘은 재귀적이다. 둘 중 큰 정수를 작은 정수로 나눈 나머지와 작은 정수의 최대 공약수를 구하는 것을 반복하기 때문이다. 다시 8과 12의 최대공약수를 구해보면 다음과 같은 과정을 거친다.
gcd(8, 12) &=& gcd(8, 12 % 8) = gcd(8, 4)
gcd(8, 4) &=& gcd(8 % 4, 4) = gcd(4, 0)따라서 gcd(8, 12) = 4 다.
최소공배수(Least Common Multiple; LCM)
공배수는 두 개 이상의 자연수의 공통된 배수이며, 최소공배수는 공배수 중 가장 작은 것이다. 8과 12의 공배수를 찾아보기 위해 각각의 배수를 나열해보면 다음과 같다.
- 8 : 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104 ...
- 12 : 12, 24, 36, 48, 60, 72, 84, 96, 108 ...
진하게 표시된 숫자가 공배수다. 그 중 최소공배수는 48이다.
최소공배수는 서로 다른 주기로 일어나는 두 사건이 동시에 일어나는 주기를 찾는 것과 같은 경우에 사용된다. 예를 들어, 대통령 선거(5년 주기)와 국회의원 선거(4년 주기)를 함께 치르는 주기는 lcm(5, 4) = 20이기 때문에 20년마다 한 번씩 찾아온다.
최소공배수는 최대공약수에서 살펴봤던 지수를 이용한 방법과 유사하게 구할 수 있지만, 최대공약수를 이용할 수도 있다. 최소공배수는 아래와 같은 성질을 가지고 있다.
max(x, y) <= lcm(x, y) <= xy최소공배수가 xy가 되는 상황은 최대공약수가 1이 되는 경우다. 이를 역으로 생각해보면 lcm(x, y) * gcd(x, y) = xy가 성립하는데, 이는 lcm(x, y) = xy / gcd(x, y)와 같이 정리할 수 있다.
구현
위에서 살펴봤던 대로 재귀적으로 mod 연산을 하여 r을 구해주며 진행하면 된다.
int gcd(int x, int y) {
int a = max(x, y);
int b = min(x, y);
int r = a % b;
if(r == 0) return b;
return gcd(b, r)
}
int lcm(int x, int y) {
return x * y / gcd(x, y);
}자바의 경우 BigInteger 클래스에 gcd가 구현돼있다. 다음과 같이 이용할 수 있다.
import java.math.BigInteger;
public class GcdUtil {
private GcdUtil() {}
public static int gcd(int x, int y) {
return BigInteger.valueOf(x)
.gcd(BigInteger.valueOf(y))
.intValue();
}
}References
