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

정의

확장 유클리드 호제법 (Extended Euclidean Algorithm) 은 두 정수 a, b 에 대해 gcd(a, b) = g 를 구하면서, 동시에 ax + by = g 를 만족하는 정수 x, y 를 찾는 알고리즘. Euclid 의 호제법을 역으로 되돌아가며 계산.

기본 호제법은 5세기경 Euclid 의 원론 에 등장, 확장 버전은 17세기 Bachet / Bézout 에 의해 정형화. Bézout 의 항등식 (Bézout’s identity) 으로도 불림.

문제 상황과 동기

일차 부정 방정식 ax + by = c 의 정수해를 구할 때:

• c 가 gcd(a, b) 의 배수가 아니면 해 없음.
• c = gcd(a, b) 일 때 한 조의 해 (x₀, y₀) 를 확장 유클리드로 구하면, 일반해는 x = x₀ + k(b/g), y = y₀ - k(a/g) (k 임의 정수).

나머지 연산의 역원 (modular inverse) 을 구할 때도 핵심:

• ax ≡ 1 (mod m) 의 해 ⇔ ax + my = 1 의 정수해.
• gcd(a, m) = 1 일 때만 역원 존재.

RSA 암호, 중국인의 나머지 정리 (CRT), 선형 디오판토스 방정식 등 다양한 응용.

시각화

핵심 아이디어

유클리드 호제법을 재귀로 내려가면서, 역으로 올라올 때 (x, y) 를 갱신.

gcd(a, b) = gcd(b, a mod b)

base case: gcd(g, 0) = g 일 때, g·1 + 0·0 = g 이므로 (x, y) = (1, 0).

induction: b·x' + (a mod b)·y' = g 가 이미 풀렸다고 가정. a mod b = a - ⌊a/b⌋·b 이므로,

b·x' + (a - ⌊a/b⌋·b)·y' = g
⇒ a·y' + b·(x' - ⌊a/b⌋·y') = g

따라서 x = y', y = x' - ⌊a/b⌋·y'.

invariant: 재귀가 내려가는 동안 언제나 ax + by = gcd(a, b) 성립.

알고리즘

exgcd(a, b):
    if b == 0:
        return (a, 1, 0)   # g = a, ax + by = a·1 + 0·0
    else:
        (g, x', y') = exgcd(b, a mod b)
        return (g, y', x' - ⌊a/b⌋·y')

반복문 (iterative) 버전도 가능 (공간 O(1)).

구현

// 확장 유클리드: ax + by = gcd(a, b)
#include <bits/stdc++.h>
using namespace std;
​
// return (g, x, y) where g = gcd(a, b), ax + by = g
tuple<long long, long long, long long> exgcd(long long a, long long b) {
  if (b == 0) return {a, 1, 0};
  auto [g, x1, y1] = exgcd(b, a % b);
  return {g, y1, x1 - (a / b) * y1};
}
​
int main() {
  long long a, b;
  cin >> a >> b;
  auto [g, x, y] = exgcd(a, b);
  cout << g << " " << x << " " << y << "\n";
  // verify
  cout << "verify: " << a*x + b*y << " == " << g << "\n";
  return 0;
}

# 확장 유클리드 재귀
def exgcd(a, b):
  if b == 0:
      return (a, 1, 0)
  g, x1, y1 = exgcd(b, a % b)
  return (g, y1, x1 - (a // b) * y1)
​
a, b = map(int, input().split())
g, x, y = exgcd(a, b)
print(g, x, y)
print(f"verify: {a*x + b*y} == {g}")

// 반복문 버전 (공간 O(1))
import java.util.*;
public class Main {
  static long[] exgcd(long a, long b) {
      long x0 = 1, y0 = 0, x1 = 0, y1 = 1;
      while (b != 0) {
          long q = a / b;
          long tmp = a; a = b; b = tmp - q * b;
          tmp = x0; x0 = x1; x1 = tmp - q * x1;
          tmp = y0; y0 = y1; y1 = tmp - q * y1;
      }
      return new long[]{a, x0, y0};
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      long a = sc.nextLong(), b = sc.nextLong();
      long[] r = exgcd(a, b);
      System.out.println(r[0] + " " + r[1] + " " + r[2]);
      System.out.println("verify: " + (a*r[1] + b*r[2]) + " == " + r[0]);
  }
}

240 46

2 -9 47
verify: 2 == 2

17 13

1 -3 4
verify: 1 == 1

복잡도

유클리드 호제법과 동일. Fibonacci 수가 worst case 입력 (연속 나눗셈 최대).

응용

1. 선형 디오판토스 방정식

ax + by = c 의 정수해:

1. g = gcd(a, b) 구하고, (x₀, y₀) = exgcd(a, b) → ax₀ + by₀ = g
2. c 가 g 의 배수가 아니면 해 없음
3. 그렇지 않으면 (x₀ · c/g, y₀ · c/g) 가 하나의 해
4. 일반해: x = x₀·(c/g) + k·(b/g), y = y₀·(c/g) - k·(a/g) (k ∈ ℤ)

2. 모듈러 역원

a·x ≡ 1 (mod m) 의 해 ⇔ ax + my = 1:

1. gcd(a, m) ≠ 1 이면 역원 없음
2. exgcd(a, m) → (g, x, y), g=1 이면 x 가 역원 (mod m 로 양수화)

모듈러 역원 문서 참고.

3. 중국인의 나머지 정리 (CRT)

두 합동식 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) (gcd(m₁, m₂)=1) 을 합칠 때, 확장 유클리드로 m₁ 의 mod m₂ 역원 (또는 반대) 을 구함.

함정

1. 음수 입력

a, b 가 음수일 수 있을 때:

• gcd(|a|, |b|) 로 절대값 취하거나,
• 재귀 내부에서 음수 mod 처리.

C++ / Java 의 % 는 음수에서 음수 나머지를 돌려주므로 주의.

2. 오버플로우

a, b 가 10^18 근처면 중간 a * x 가 long long 넘을 수 있음. (__int128 또는 Python).

3. x, y 의 크기

exgcd 로 나온 (x, y) 는 절댓값이 꽤 클 수 있음 (O(b), O(a)). 최소 절댓값 해를 원하면 일반해 식에서 k 조정.

4. gcd ≠ 1 일 때

ax + by = c 에서 c 가 gcd(a, b) 배수가 아니면 해 없음. 체크 누락하면 WA.

BOJ 연습 문제

참고

• 유클리드 호제법
• 모듈러 역원
• 중국인의 나머지 정리