나눗셈과 최대공약수

임의의 두 정수 $a, b$에 대해, $(a, b)$를 $a$와 $b$의 최대공약수라고 하자. $a = bq + r$일 때, $(a, b) = (b, r)$이다. 증명은 어렵지 않다. 임의의 정수 $c$에 대해 $c \mid (a, b)$라면 $c \mid a - bq = r$이므로 $c \mid (b, r)$이고, 반대 방향도 같은 방법으로 보일 수 있다.

유클리드 알고리즘

유클리드 알고리즘은 나눗셈과 최대공약수의 이러한 성질을 이용하여 임의의 두 정수 $a, b$의 최대공약수를 빠르게 구하는 알고리즘이다. 다음과 같은 나눗셈 열을 생각하자.

마지막 나눗셈에서는 $r_{n - 1}$이 $r_n$으로 나누어 떨어진다. 이는 유클리드 알고리즘의 기저 사례라고 할 수 있다. 임의의 0이 아닌 정수 $m$에 대해 $(m, 0) = m$이기 때문이다. 유클리드 알고리즘을 통해 $(a, b) = r_n$임을 알 수 있다. 나눗셈 열에서 $r_m = 0$이 등장하여 알고리즘이 유한한 수행을 통해 정지한다는 사실은, 수열 $b > r_1 > r_2 > \cdots$가 감소하는 음이 아닌 정수 수열을 이룸을 관찰함으로써 알 수 있다.

구현

유클리드 알고리즘을 다음과 같이 구현할 수 있다.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

이는 꼬리 재귀 함수이다. 마음이 편안해진다.

일단 재귀 함수로 구현을 하였지만, 재귀 함수의 호출은 종종 많아져서는 메모리를 터뜨리게 된다. 알고리즘에 등장하는 나눗셈 열이 얼마나 길게 이어지는지 알아보기 위해 알고리즘을 분석하여 보자.

분석

입력이 $a \ge b$으로 주어졌다고 가정하자. 피보나치 수열을 사용하여 $k$의 증가에 따라 $r_k$가 지수적으로 감소한다는 사실을 증명할 것이다. 피보나치 수열은 점화식을 통해 주어지는 수열으로,

를 만족한다. $b < f_k$가 되는 정수 $k$를 선택하고, 표기의 편의를 위해 $r_0 = b$로 설정하자. $r_1 < f_{k - 1}$임을 보이고 싶지만, 이는 간단한 반례를 통해 반증될 수 있는 명제이다. $(23, 12)$를 유클리드 알고리즘을 통해 계산하는 상황을 생각하면, 처음 설정하는 피보나치 수는 $f_7 = 13$이다. $r_1 = 11 \ge 8 = f_6$이므로 $r_1 < f_{k - 1}$는 거짓이다.

그러나 이가 거짓일 때 관찰할 수 있는 사실이 하나 있다. 위의 예시에서 나눗셈을 한 번 더 진행하여 보자. $r_2 = 1 < 5 = f_5$임을 알 수 있다. 사실은 $r_1 < f_{k - 1}$이 거짓인 경우, $r_2 < f_{k - 2}$는 항상 참이다. 임의의 $m$에 대해, $r_m < f_k$이고 $r_{m + 1} \ge f_{k - 1}$을 가정하자. 다음을 관찰하자: $r_{m + 2} \le r_m - r_{m + 1} < f_k - f_{k - 1} = f_{k - 2}.$ 따라서 $r_0 < f_k$인 정수 $k$에 대해, 유클리드 알고리즘은 많아야 $k + 1$번의 나눗셈을 수행할 것이다. $f_k \in \mathcal{O} ( \varphi^k ), \varphi = \frac{1 + \sqrt{5}}{2}$이므로, 유클리드 알고리즘은 $\mathcal{O}(\log r_0)$의 시간복잡도를 갖는다.

확장된 유클리드 알고리즘

개요: 디오판토스 방정식 $ax + by = (a, b)$

임의의 두 정수 $a, b$에 대해 $ax + by = (a, b)$를 만족하는 정수 $x, y$가 존재한다. 정수 집합의 정렬성을 이용하여 증명할 수 있으나, 유클리드 알고리즘을 이용하여 증명하는 것이 좀 더 와닿는다고 생각한다. 우선 정수의 부분집합 $S = \{ax + by: x, y \in \mathbb{Z}\}$를 생각하자. 분명하게 $a = r_{-1}, b = r_0 \in S$이다. $S$에 대해 다음 성질들을 관찰하자.

1. $S$는 덧셈에 대해 닫혀있다. $S$의 임의의 두 원소 $ax + by, au + bv$에 대해

$(ax + by) + (au + bv) = a(x + u) + b(y + v) \in S$ 이다.

2. $S$는 상수배 곱셈에 대해 닫혀있다. $S$의 임의의 원소 $ax + by$와 임의의 정수 $d$에 대해

$d(ax + by) = a(dx) + b(dy) \in S$ 이다.

이러한 성질에 의해, 임의의 $k$에 대해 $r_{k - 2}, r_{k - 1}$이 $S$에 포함된다면 $r_k = r_{k - 2} - q_k r_{k - 1}$또한 $S$에 포함됨을 알 수 있다. $r_{-1}, r_0 \in S$이므로 수학적 귀납법을 통해 $r_n = (a, b) \in S$임을 알 수 있다.

한편, 디오판토스 방정식 $ax + by = (a, b)$에는 항상 정수해 $x, y$가 존재한다는 정리를 베주 항등식^{Bézout's identity}으로 부르기도 한다.

유클리드 알고리즘과 디오판토스 방정식 $ax + by = (a, b)$

디오판토스 방정식 $ax + by = (a, b)$는 정수해를 가짐을 보였다. 유클리드 알고리즘은 단지 이 방정식에서 정수해가 존재하는지 알려줄 뿐 만 아니라, 정수해를 계산할 수 있는 방법을 제시한다.

우선 $a = r_{-1}, b = r_0$라고 하자. $i = -1, 0, 1, \cdots, n$에 대해 $r_i \in S$임을 보였으므로, $as_i + bt_i = r_i$를 만족하는 정수 $s_i, t_i$가 존재할 것이다. $r_k = r_{k - 2} - r_{k - 1} q_k$를 관찰하자. $s_{k - 2}, s_{k - 1}, t_{k - 2}, t_{k - 1}$으로 부터 $s_k, t_k$를 각각 다음과 같이 계산할 수 있다.

$r_{-1} = a \cdot 1 + b \cdot 0, r_0 = a \cdot 0 + b \cdot 1$은 쉽게 구할 수 있으므로, $s_n$과 $t_n$을 총 $n$번의 나눗셈을 통해 계산할 수 있다.

구현

기존에 구현하였던 유클리드 알고리즘에 $s_n$과 $t_n$을 계산하는 기능을 추가하여 보자. 자료를 쉽게 다루기 위해서 다음고 같은 구조체를 정의한다.

struct eucPair {
    int x;
    int s, t;
};

x에는 $r_k$의 값이, $s, t$에는 각각 $r_k$를 $a, b$의 선형결합으로 나타내었을 때의 계수가 저장된다. 위에서 구한 점화식과 유클리드 알고리즘을 이용하여 디오판토스 방정식을 해결하는 알고리즘은 다음과 같다.

eucPair Euclidean(eucPair a, eucPair b) {
    if (b.x == 0) return a;
    int q = a.x / b.x;
    eucPair r;
    r.x = a.x % b.x;
    r.s = a.s - b.s * q;
    r.t = a.t - b.t * q;
    return Euclidean(b, r);
}

다시 꼬리 재귀함수가 나왔다.

활용

PS 또는 정수론 문제들을 풀게 된다면 이러한 형태의 디오판토스 방정식의 해를 구해야 하는 일이 종종 생긴다. 주어진 정수 $a$에 대해, $ax \equiv 1 \pmod{n}$을 만족하는 정수 $x$를 법 $n$에 대한 $a$의 잉여역수라고 하고, $x = a^{-1}$으로 표기한다. $(\mathbb{Z}/n\mathbb{Z})^\times$에서 $x$는 $a$의 역원이기 때문에 이러한 표기법을 사용한다. 이러한 $x$를 찾는 문제는 이변수 선형 디오판토스 방정식으로 변형될 수 있다. $ax + ny = 1$을 만족하는 정수 $x, y$를 찾는 문제와 같기 때문이다. 확장된 유클리드 알고리즘을 사용하면 $a$의 잉여역수를 $\mathcal{O}(\log n)$의 시간복잡도로 찾을 수 있다. 물론, $(a, n) > 1$이라면 잉여역수를 찾을 수 없을 것이다.