어떤 자연수 $n$을 나누어 떨어지게 하는 자연수 $i$를 $n$의 약수라고 하고, $i \mid n$라고 쓴다.
두 자연수 $a, b$의 공통인 약수를 $a, b$의 공약수라고 하고, 가장 큰 공약수를 최대공약수라고 한다. $a,b$의 최대공약수는 $\gcd(a, b)$로 표기할 수 있다. 반대로 $n$으로 나누었을 때 나누어 떨어지는 자연수 $i$를 $n$의 배수라고 한다. 두 자연수 $a, b$의 공통인 배수를 $a,b$의 공배수라고 하고, 가장 작은 공배수를 최소공배수라고 한다. $\text{lcm}(a, b)$로 표기한다.
유클리드 호제법
유클리드 호제법(Euclidean Algorithm)은 유클리드가 기원전 300년경에 만든 인류 최초의 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘이다. 전체적인 정의는 다음과 같다.
두 양의 정수 $a, b \; (a > b)$에 대해 $a = bq+r\, (0 \leq r < b)$라고 놓으면 $\gcd(a,b) = \gcd(b,r)$이다. 이때 $r = 0$이면 $\gcd(a,b) = b$다.
증명은 다음과 같이 할 수 있다.
$\gcd(a,b)$를 $G$로 놓으면 서로소인 두 정수 $n, m$에 대해 $a = Gn,b=Gm$이라고 할 수 있다. $a = bq+r$에 이를 $a,b$ 대신 대입하면 $Gn = Gmq + r$이 되고, $r$에 대해 식을 정리하면 $r = G(n-mq)$이다. 따라서 $r$은 $G$의 배수이므로 $G$는 $r,b$의 공약수다. 이때 $m$과 $n-mq$가 서로소이면 $\gcd(b,r) = G$가 된다. $m$과 $n-mq$가 서로소라는 것은 자명하므로 $\gcd(a,b) = \gcd(b,r)$이다.
이제 이걸 이용해서 어떻게 최대공약수를 구할 수 있을까? $r = 0$이면 $b$가 최대공약수가 되기 때문에 $r$을 $0$으로 만들면 된다. $r$은 $a-bq$이므로 $a \bmod b$이다. 따라서 다음 식이 성립한다.
$$\gcd(a,b) = \begin{cases} a & \text{if }b = 0 \\ \gcd(b, a \bmod b) & \text{otherwise} \end{cases}$$
이제 $b = 0$일때까지 위 과정을 반복하면 된다. 코드로 구현하면 다음과 같다.
int gcd(int a, int b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
최소공배수는 $\text{lcm}(a,b) = ab \div \gcd(a,b)$라는 식을 이용하여 계산할 수 있다. 이때 $ab$를 먼저 계산하면 오버플로우가 발생할 수 있으므로 연산 순서를 적절히 바꾸는 것이 좋다.
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
유클리드 호제법의 시간 복잡도는 $O(\log \text{max}(a,b))$라고 한다.