나눗셈과 최대공약수

임의의 두 정수 에 대해, 를 와 의 최대공약수라고 하자. 일 때, 이다. 증명은 어렵지 않다. 임의의 정수 에 대해 라면 이므로 이고, 반대 방향도 같은 방법으로 보일 수 있다.

유클리드 알고리즘

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

마지막 나눗셈에서는 이 으로 나누어 떨어진다. 이는 유클리드 알고리즘의 기저 사례라고 할 수 있다. 임의의 0이 아닌 정수 에 대해 이기 때문이다. 유클리드 알고리즘을 통해 임을 알 수 있다. 나눗셈 열에서 이 등장하여 알고리즘이 유한한 수행을 통해 정지한다는 사실은, 수열 가 감소하는 음이 아닌 정수 수열을 이룸을 관찰함으로써 알 수 있다.

구현

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

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

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

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

분석

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

를 만족한다. 가 되는 정수 를 선택하고, 표기의 편의를 위해 로 설정하자. 임을 보이고 싶지만, 이는 간단한 반례를 통해 반증될 수 있는 명제이다. 를 유클리드 알고리즘을 통해 계산하는 상황을 생각하면, 처음 설정하는 피보나치 수는 이다. 이므로 는 거짓이다.

그러나 이가 거짓일 때 관찰할 수 있는 사실이 하나 있다. 위의 예시에서 나눗셈을 한 번 더 진행하여 보자. 임을 알 수 있다. 사실은 이 거짓인 경우, 는 항상 참이다. 임의의 에 대해, 이고 을 가정하자. 다음을 관찰하자: 따라서 인 정수 에 대해, 유클리드 알고리즘은 많아야 번의 나눗셈을 수행할 것이다. 이므로, 유클리드 알고리즘은 의 시간복잡도를 갖는다.

확장된 유클리드 알고리즘

개요: 디오판토스 방정식

임의의 두 정수 에 대해 를 만족하는 정수 가 존재한다. 정수 집합의 정렬성을 이용하여 증명할 수 있으나, 유클리드 알고리즘을 이용하여 증명하는 것이 좀 더 와닿는다고 생각한다. 우선 정수의 부분집합 를 생각하자. 분명하게 이다. 에 대해 다음 성질들을 관찰하자.

1. 는 덧셈에 대해 닫혀있다. 의 임의의 두 원소 에 대해 이다.

2. 는 상수배 곱셈에 대해 닫혀있다. 의 임의의 원소 와 임의의 정수 에 대해 이다.

이러한 성질에 의해, 임의의 에 대해 이 에 포함된다면 또한 에 포함됨을 알 수 있다. 이므로 수학적 귀납법을 통해 임을 알 수 있다.

한편, 디오판토스 방정식 에는 항상 정수해 가 존재한다는 정리를 베주 항등식^{Bézout’s identity}으로 부르기도 한다.

유클리드 알고리즘과 디오판토스 방정식

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

우선 라고 하자. 에 대해 임을 보였으므로, 를 만족하는 정수 가 존재할 것이다. 를 관찰하자. 으로 부터 를 각각 다음과 같이 계산할 수 있다.

은 쉽게 구할 수 있으므로, 과 을 총 번의 나눗셈을 통해 계산할 수 있다.

구현

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

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

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

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 또는 정수론 문제들을 풀게 된다면 이러한 형태의 디오판토스 방정식의 해를 구해야 하는 일이 종종 생긴다. 주어진 정수 에 대해, 을 만족하는 정수 를 법 에 대한 의 잉여역수라고 하고, 으로 표기한다. 에서 는 의 역원이기 때문에 이러한 표기법을 사용한다. 이러한 를 찾는 문제는 이변수 선형 디오판토스 방정식으로 변형될 수 있다. 을 만족하는 정수 를 찾는 문제와 같기 때문이다. 확장된 유클리드 알고리즘을 사용하면 의 잉여역수를 의 시간복잡도로 찾을 수 있다. 물론, 이라면 잉여역수를 찾을 수 없을 것이다.