확장 유클리드 호제법 (Extended Euclidean Algorithm)

1. 정의

확장 유클리드 호제법은 두 정수 $a, b$에 대해 $GCD(a, b) = d$라고 했을 때, $ax + by = d$를 만족하는 $x, y$를 찾을 때 이용되는 알고리즘이다. 확장 유클리드 호제법에 대해 공부하기 전에 유클리드 호제법과 베주 항등식이 무엇인지 먼저 알아보자. 

1) 유클리드 호제법

두 정수 $a, b$에 대하여 최대공약수 $GCD(a, b)$를 빠르게 찾는 알고리즘이다. $a$를 $b$로 나눈 나머지를 $r$이라고 할 때, $GCD(a, b) = GCD(b, r)$이 성립하는데 유클리드 호제법은 이 성질을 이용한다.

 

아래와 같이 한 숫자에서 다른 숫자를 계속 나누어서 나머지가 0이 될 때까지 위 성질을 이용하면 몇 번의 연산만으로 $GCD(a, b)$를 구할 수 있다. $a$를 $b$로 나눈 나머지를 $r_{1}$, $b$를 $r_{1}$로 나눈 나머지를 $r_{2}$, $r_{1}$을 $r_{2}$로 나눈 나머지를 $r_{3}$......라고 할 때, $GCD(a, b) = GCD(b, r_{1}) = GCD(r_{1}, r_{2}) = GCD(r_{2}, r_{3})$...... 일 것이고 이 과정을 반복하다가 나머지가 0이 될 때의 나누는 수가 $GCD(a, b)$가 된다. 

 

(증명 생략)

 

예를 들어, 78696과 19332의 최대공약수를 구해보자. 

1. 78696을 19332로 나눈 나머지는 1368이다. 

2. 19332를 1368로 나눈 나머지는 180이다. 

3. 1368을 180으로 나눈 나머지는 108이다. 

4. 180을 108로 나눈 나머지는 72이다. 

5. 108을 72로 나눈 나머지는 36이다. 

6. 72를 36으로 나눈 나머지는 0이다. 따라서 최대공약수는 나누는 수인 36이다. 

 

함수를 구현을 해보면 다음과 같다. 

 

int gcd(int a, int b) {
	// 나머지가 0이 될 때까지
	while (b) {
		int c = a % b;
		a = b;
		b = c;
	}
	return a;
}

 

---

2) 베주 항등식

베주 항등식은 아래의 3개의 참인 명제로 이루어져 있는데, 확장 유클리드 호제법은 이 명제들을 가정으로 두고 해를 구한다. 

 

두 정수 $a, b$에 대하여 $GCD(a, b) = d$라고 할 때,

1. $ax + by = d$를 만족하는 정수 $x, y$가 존재한다. 

2. 정수 $x, y$에  대하여 $d$는 $ax + by$로 표현할 수 있는 가장 작은 정수이다. 

3. $ax + by$로 표현될 수 있는 모든 정수는 $d$의 배수이다. 

 

(증명 생략)

---

유클리드 호제법으로 최대공약수를 구하는 법도 알았고 베주 항정식이 무엇인지도 알아보았다. 이제 확장 유클리드 호제법에 따라 $ax + by = d$를 만족하는 $x, y$를 구해 보자. 

 

유클리드 호제법으로 두 정수 $a, b$의 최대공약수 $d$를 구하는 과정을 다시 써보면 다음과 같다. 

$a = b * q_{1} + r_{2}$

$b = r_{2} * q_{2} + r_{3}$

$r_{2} = r_{3} * q_{3} + r_{4}$

               .

               .

               .

$r_{i-1} = r_{i} * q_{i} + r_{i+1}$ --- (1)

여기서 $r_{i+1}$이 0이 되어 연산이 끝났다고 해보자. 이 상태에서 $a, b$의 최대공약수 $d$는 $r_{i}$인 것을 알 수 있다. 또한, (1)을 통해 $a = r_{0}, b = r_{1}$이라고 할 수 있고 점화식 $r_{i+1} = r_{i-1} - r_{i} * q_{i}$를 얻을 수 있다. --- (2)

 

$r_{i}$를 $ax + by$꼴로 표현하기 위해 임의의 정수 $s_{i}, t_{i}$에 대해 다음과 같이 식을 쓸 수 있다. 

$a * s_{i} + b * t_{i} = r_{i}$ --- (3)

 

여기서 $a = r_{0}, b = r_{1}$라고 했으므로 $a = a * 1 + b * 0 = r_{0}, b = a * 0 + b * 1 = r_{1}$이라고도 볼 수 있으므로 $s_{0} = 1, t_{0} = 0, s_{1} = 0, t_{1} = 1$인 것을 알 수 있다. --- (4)

 

그리고 (3)을 (2)에 대입하면 다음과 같은 식을 얻을 수 있다. 

$a * s_{i+1} + b * t_{i+1} = a * s_{i-1} + b * t_{i-1} - (a * s_{i} + b * t_{i}) * q_{i}$

                                         $= a * (s_{i-1} - s_{i} * q_{i} ) + b * (t_{i-1} - t_{i} * q_{i})$ --- (5)

 

(2), (4), (5)에 의해, $s, t, r, q$를 다음과 같이 정리할 수 있다. 

$r_{0} = a, r_{1} = b,  r_{i+1} = r_{i-1} - r_{i} * q_{i}$

$s_{0} = 1, s_{1} = 0,  s_{i+1} = s_{i-1} - s_{i} * q_{i}$

$t_{0} = 0, t_{1} = 1,  t_{i+1} = t_{i-1} - t_{i} * q_{i}$

 

다시 위로 돌아가서 결국 $ax + by = d$를 만족하는 두 정수 $x, y$는 $d$가 $r_{i}$일 때이므로, $x = s_{i}, y=t_{i}$라고 정리할 수 있다. 

 

 

문자로는 제대로 파악이 안 되니 예시를 한 번 보자. $9x + 5y = 1$을 만족하는 두 정수 $x, y$를 구해보자.

먼저 $s, t, r, q$의 초기 상태를 표로 나타내면 다음과 같다. 

 

 

그다음 $r_{i}$가 0이 될 때까지 계속해서 $r_{i}$과 $q_{i}$를 구하자. 

 

 

$i = 4$일 때, $r_{i}$가 0이 되었다. 그러면 $i = 3$일 때의 $s_{i}$와 $t_{i}$값이 우리가 구하고 싶은 해이다. 표를 채워보자. 

 

 

따라서, $9x + 5y = 1$을 만족하는 해는 $x = -1, y=2$이다. 

---

2. 구현

$s, t, r, q$의 초기값을 설정하고 $r$이 0이 될 때까지 위에서 구한 점화식을 통해 값이 갱신되도록 구현을 하면 된다. 생각보다 쉽다. 

 

$s, t, r, q$의 초기값을 다음과 같이 각각 1차원 배열에 저장하자.

 

vector<int>s = { 1,0 }; // s0=1, s1=0
vector<int>t = { 0,1 }; // t0=0, t1=1
vector<int>r = { a,b }; // r0=a, r1=b
vector<int>q; // q는 비어있는 상태

 

 

$r$이 0이 될 때까지 $r$과 $q$를 다음과 같이 구하자. 

 

int r0 = r[r.size() - 2];
int r1 = r[r.size() - 1];
// r1이 0일 때까지 구하기
r.push_back(r0 % r1);
q.push_back(r0 / r1);

 

 

$r$과 $q$를 구했다면 위에서 구한 점화식에 따라 $s$와 $t$도 다음과 같이 구해준다. 

 

int s0 = s[s.size() - 2];
int s1 = s[s.size() - 1];
int t0 = t[t.size() - 2];
int t1 = t[t.size() - 1];
int q1 = q[q.size() - 1];
s.push_back(s0 - s1 * q1); // si+1 = si-1 - si*qi
t.push_back(t0 - t1 * q1); // ti+1 = ti-1 - ti*qi

 

 

이 과정을 $r$이 0이 될 때까지 반복한다고 했으므로 while문 안에 넣고 탈출 조건을 추가하면 될 것이다. 아래와 같다.

 

while (1) {
	int r0 = r[r.size() - 2];
	int r1 = r[r.size() - 1];
       
    	// 탈출 조건
	if (r0 % r1 == 0) break;
    
	r.push_back(r0 % r1);
	q.push_back(r0 / r1);

	int s0 = s[s.size() - 2];
	int s1 = s[s.size() - 1];
	int t0 = t[t.size() - 2];
	int t1 = t[t.size() - 1];
	int q1 = q[q.size() - 1];
	s.push_back(s0 - s1 * q1);
	t.push_back(t0 - t1 * q1);
}

 

 

내가 구하고 싶은 해 $x, y$는 아마 $s, t$ 배열의 마지막 원소일 것이다. 

 

x = s[s.size() - 1], y = t[t.size() - 1];

 

---

3. 전체 코드

 

void extendedGCD(int a, int b) {
	vector<int>s = { 1,0 };
	vector<int>t = { 0,1 };
	vector<int>r = { a,b };
	vector<int>q;
	while (1) {
		int r0 = r[r.size() - 2];
		int r1 = r[r.size() - 1];
        
        	// 탈출 조건
		if (r0 % r1 == 0) break;

		r.push_back(r0 % r1);
		q.push_back(r0 / r1);

		int s0 = s[s.size() - 2];
		int s1 = s[s.size() - 1];
		int t0 = t[t.size() - 2];
		int t1 = t[t.size() - 1];
		int q1 = q[q.size() - 1];
		s.push_back(s0 - s1 * q1);
		t.push_back(t0 - t1 * q1);
	}

	x = s[s.size() - 1], y = t[t.size() - 1];
}

 

---

4. 관련 문제

 

[백준 3955번] 캔디 분배

 

[백준 14565번] 역원(Inverse) 구하기