PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법

 

[목차]

 

1. 유클리드 호제법

 

2. 확장 유클리드 호제법

 

3. 모듈러(modular) 연산에서의 곱셈의 역원

 

4. 예시 문제

 

 

  1. 유클리드 호제법

 

유클리드 호제법은 정수론을 조금이라도 공부했다면, 혹은 공부하지 않았더라도 충분히 들어봤을 것이다. 

유클리드 호제법은 자연수 $a$, $b$ 가 주어졌을 때, $gcd(a, b)$ 즉, $a$와 $b$의 최대 공약수를 구하는 방법이다. 

 

$a$를 $b$로 나눈 몫을 $q$라고 하고, 나머지를 $r$이라고 하면 $a = bq + r$ 로 나타난다. 

이때, $gcd(a, b) = gcd(b, r)$을 만족한다. 

이유는 $gcd(a, b) = g$라고 하면, $g|a$, $g|b$ 를 만족하게 되고, $r = a - bq$이므로 $g|(a - bq) = r$ 을 만족한다.

반대로, $gcd(b, r) = g$라고 해도, $g|b$, $g|r$ 를 만족하게 되고, $a = bq + r$이므로 $g|(bq+r) = a$ 를 만족한다.

따라서, 위 식을 이용해서 기존의 $(a, b)$를 $(b, r)$로 축소 해나가게 되면 결국 최종적으로 $(g, 0)$의 형태가 나오게 된다. 

 

$gcd(a, b)$를 구하는데 걸리는 시간은 얼마나 될까?

먼저 $a \geq b$라고 가정하자. 사실 $a < b$인 경우에도 $a = bq + r$에서 $q$가 $0$이고 $r$이 $a$가 되므로 유클리드 호제법을 한 번만 수행하면 $gcd(a, b) = gcd(b, a)$로, 즉 앞에 있는 값이 뒤의 값보다 크도록 바뀌게 된다. 

 

따라서 $a \geq b$라고 하게 되면, $q \geq 1$, $(q + 1) \geq 2$ 을 만족하고 $2r \leq (q+1)r = rq + r \leq bq + r = a $이므로 $2r \leq a$를 만족한다. 

그러므로 $br \leq (1/2)ab$이기 때문에 순서쌍의 곱이 절반 이상씩 줄어들게 된다. 

즉, $gcd(a, b)$를 구하는데 걸리는 시간은 $O(max(loga, logb))$이다. 

 

예시) $gcd(120, 54)$

 

$120 = 54\times 2 + 12$ 이므로 $gcd(120, 54) = gcd(54, 12)$

$54 = 12\times 4 + 6$ 이므로 $gcd(54, 12) = gcd(12, 6)$

$12 = 6\times 2 + 0$ 이므로 $gcd(12, 6) = gcd(6, 0)$

따라서 $gcd(120, 54) = gcd(6, 0) = 6$

 

코드로 나타내면 한 줄로 구할 수 있다.

int gcd(int a, int b) {
	return b ? gcd(b, a%b) : a;
}

$b$가 $0$이 아니면 $b$와 '$a$를 $b$로 나눈 나머지'에 대해서 다시 수행하고, $b$가 $0$이면 $a$를 반환해준다. 

 

 

 

  2. 확장 유클리드 호제법

 

이름 그대로 유클리드 호제법의 확장형이다. 

확장 유클리드 호제법은 $gcd(a, b)$를 구하는 것뿐만 아니라, 정수해를 갖는 부정 방정식 $ax + by = c$이 주어질 때

이 방정식을 만족하는 $(x, y)$ 값을 구할 수 있다. 

이때, $c$가 $gcd(a, b)$의 배수가 아니라면 해가 존재하지 않는다. 좌변인 $ax + by$가 $gcd(a, b)$의 배수이기 때문이다. 

자세한 내용과 증명은 '베주 항등식(Bezout's Identity)'의 명제를 통해서 알 수 있다.

궁금하다면 이 링크를 통해 이해해보자. baeharam.github.io/posts/algorithm/extended-euclidean/

(본 글에서의 $(x, y)$ 해를 찾는 과정도 위 블로그를 참고하였다)

 

$c = gcd(a, b)$라고 가정하자. 추가적으로, $a, b, c$의 부호에는 제한이 없다.

$(x, y)$ 값을 구하기 위해서는 유클리드 호제법의 과정을 역으로 따라가면 찾을 수 있다. 

두 정수 $a$, $b$에 대해서 유클리드 호제법을 반복하는 과정을 나열하면 다음과 같다.

 

$a = bq_0 + r_1$

$b = r_1q_1 + r_2$

$r_1 = r_2q_2 + r_3$

...

$r_{i-1} = r_iq_i + r_{i+1}$

 

유클리드 호제법은 $r_{i+1} = 0$일 때 종료되고, $r_{i+1} = r_{i-1} - r_iq_i$ 임을 알 수 있다. 이때 $c$는 $r_i$가 된다. 

따라서 $ax + by$ 꼴로 나타내기 위해서 $r_0 = a$, $r_1 = b$라고 하면, $r_0 = a\times 1 +b\times 0$ 이 되고, 

$r_1 = a \times 0 + b \times 1$이 된다. 

이후의 $r_i$들도 같은 꼴로 나타나는 것을 알 수 있고, 일반화를 하면 아래와 같이 나타난다.

$r_i = s_ia + t_ib$ 

 

이를 $r_{i+1} = r_{i-1} - r_iq_i$에 대입하면 다음의 점화식을 얻는다. 

 

$s_{i+1}a + t_{i+1}b = (s_{i-1}a + t_{i-1}b) - (s_ia + t_ib)q_i = s_{i-1}a - s_iaq_i + t_{i-1}b - t_ibq_i$

$ = (s_{i-1} - s_iq_i)a + (t_{i-1} - t_iq_i)b $

 

따라서 $s$와 $t$에 대한 점화식이 만들어진다.

$s_{i+1} = s_{i-1} - s_iq_i$

$t_{i+1} = t_{i-1} - t_iq_i$

 

코드로 나타내면 다음과 같다. 주어진 $a$와 $b$값을 넣어주고, $s$와 $t$의 주솟값을 넣어주어 함수 내에서 $s$와 $t$를 구한다. 

구한 $(s, t)$가 $ax + by = c$를 만족하는 정수해가 되는 것이다. 

그리고 return값으로 $gcd(a, b)$를 반환하므로 만약 $c$가 $gcd(a,b)$의 배수인 경우에는 $s$와 $t$에 정수배를 해주면 된다. 

 

ll exEuclid(ll a, ll b, ll &s, ll &t) {
	if (b == 0) {
		s = 1; t = 0;
		return a;
	}
	ll gcd = exEuclid(b, a%b, s, t);
	ll tmp = t;
	t = s - (a / b)*t;
	s = tmp;
	
	if (s <= 0) { //s를 양수로
		s += b;
		t -= a;
	}
	return gcd;
}

위의 코드 또한 유클리드 호제법과 마찬가지로 로그 시간 내에 계산이 가능하다.

 

$ax + by = c$의 해가 유일하지 않기 때문에 다른 해 들은 어떻게 구할지도 생각해볼 수 있다. 

일반 해는 다음과 같이 구한다.

$ax + by = c$를 만족하는 두 정수해를 $(x_1, y_1)$ , $(x_2, y_2)$라고 하면 $ax_1 + by_1 = ax_2 + by_2 = c$ 이므로

$a(x_2 - x_1) = b(y_1 - y_2)$를 만족한다. 

따라서 $b(y_1 - y_2)$는 $a$의 배수가 되어야 하고, $(y_1 - y_2)$가 $a/gcd(a, b)$의 배수 이어야 하기 때문에 어떤 정수 k에 대해서

 

$y_2 = y_1 - k\times a / gcd(a, b)$

$x_2 = x_1 + k\times b/gcd(a,b)$ 가 일반 해가 된다. 

 

 

  3. 모듈러(modular) 연산에서의 곱셈의 역원

 

확장 유클리드 호제법을 잘 이용할 수 있는 대표적인 경우이다. 

모듈러(modular) 연산에서의 곱셈의 역원을 구하는 경우는 $ax \equiv 1 (mod\;n)$ 인 $x$를 찾는 경우이다. 

이는 결국 $ax + ny = 1$의 방정식을 만족하는 정수 순서쌍 $(x, y)$를 구하는 것과 동일하다. 

 

그러므로 우선 $gcd(a, n)$이 $1$이 아니라면 위에서 설명한 내용을 바탕으로 역원이 존재하지 않음을 알 수 있다. 

$gcd(a, n) = 1$이라면, 확장 유클리드 알고리즘을 그대로 이용해주면 된다. 

 

이렇게 구한 곱셈의 역원이 과연 유일할까?

$x_1$과 $x_2$가 $mod\;n$에 대한 $a$의 역원이라고 하자. 역원이 존재하기 때문에 $gcd(a, n) = 1$을 당연히 만족하고, $n | (ax_1 - 1)$ , $n | (ax_2 - 1)$이므로 $n | a(x_1 - x_2)$를 얻을 수 있다. 

$gcd(a, n) = 1$이므로 $n | (x_1 - x_2)$임을 알 수 있고, 결국 $x_1 \equiv x_2 (mod\;n)$이 성립한다. 

따라서 모듈러 역원은 유일하다.

 

더 나아가 나머지가 $1$이 아닌 일반적인 경우 $ax \equiv b (mod\;n)$인 경우도 해결할 수 있음을 쉽게 알 수 있다. 

 

 

  4. 예시 문제 및 풀이

 

가장 간단한 예시 문제 코드를 통해서 어떤식으로 이용하는지 알아보자. 

 

[백준 14565번] 역원(Inverse) 구하기 www.acmicpc.net/problem/14565

14565번: 역원(Inverse) 구하기

 

확장 유클리드 알고리즘을 이용할 수 있는 제일 기본적인 문제이다. 

우선 덧셈역은 더해서 $n$의 배수가 되어야 하므로 $n-a$로 바로 구해주면 된다.

곱셈역은 $ac + nk = 1$ 을 만족하는 양수 c를 구해주면 된다. 

여기서 $gcd(a, n) = 1$이 아니라면 곱셈역이 존재하지 않으므로 -1을 출력해주어야 한다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll exEuclid(ll a, ll b, ll &s, ll &t) {
	if (b == 0) {
		s = 1; t = 0;
		return a;
	}
	ll gcd = exEuclid(b, a%b, s, t);
	ll temp = t;
	t = s - (a / b)*t;
	s = temp;

	if (s <= 0) {
		s += b;
		t -= a;
	}
	return gcd;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	ll n, a; cin >> n >> a;
	ll c, k;
	ll g = exEuclid(a, n, c, k);
	if (g != 1) cout << n - a << ' ' << -1;
	else cout << n - a << ' ' << c;
}

 

<추가 문제들>

 

 

[백준 2436] 공약수  Gold V

힌트)

lcm(a, b) = a * b / gcd(a, b) 임을 이용하자. 입력받은 두 수 a, b의 곱이 두 자연수의 곱이다.

한 자연수를 설정하면 다른 자연수가 자동으로 정해진다.  

 

[백준 3955번] 캔디 분배  Platinum V

힌트)

$KX + 1 = CN$을 만족하는 N을 찾아줘야 한다. 이 문제는 예외처리를 해줄 부분이 꽤 있다. 

먼저 X가 0이 되면 안되고, N이 $10^9$를 초과하면 안된다. 혹시나 맞왜틀을 시전중이라면 예외를 잘 처리했는지 확인해보자. 참고로 1 1 인풋이 들어오면 답은 2이다.

 

[백준 11635번] Wipe Your Whiteboards  Platinum IV

힌트)

마찬가지로 단순히 확장 유클리드 호제법을 이용해주면 된다. 

다만 추가적인 조건으로, 구해지는 $(A, B)$가 최소가 되어야 하고, A와 B가 모두 0보다 커야하기 때문에 

유클리드 알고리즘을 통해 나온 A와 B를 적절히 조절해주어야 한다.

기본적으로 $ax + by = c$를 만족하는 $(x, y)$가 있을 때, $(x+b, y -a)$도 해를 만족하는 점을 이용하자.

 

 

[백준 10327번] 피보나치 문제해결전략  Platinum III

힌트)

G1 = a, G2 = b라고 하고, 원래의 피보나치 수열을 fibo[i]라고 하면
Gabonacci 수열은 fibo[i]*a + fibo[i+1]*b의 형태로 나타난다. 
따라서 가능한 모든 fibo[i]*a + fibo[i+1]*b = n의 방정식의 해를 구해서 그 중, 가장 작은 해를 구한다.

overflow에 주의하자.

 

[Atcoder ABC186 E] Throne

힌트)

$Kx + S \equiv 0 (mod\;N)$ 을 만족하는 최소의 x를 찾는 문제이다.  

 

 

본 글은 rkm0959.tistory.com/ 블로그에서 도움을 받았습니다.

허락해주신 rkm0959님 감사드립니다.

 

[추가 참고 블로그]

casterian.net/archives/601

baeharam.github.io/posts/algorithm/extended-euclidean/