알고리즘 개념[기초] - 확장 유클리드 호제법

기존의 유클리드 호제법의 목적은 두 수의 최대 공약수를 구하는 것이었습니다. 이와 다르게 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것입니다.

확장 유클리드 호제법의 핵심 이론

해를 구하고자 하는 방정식
ax + by = c (a,b,c,x,y는 정수)

이 때 위 방정식은 c % gcd(a,b) = 0인 경우에만 정수해를 갖습니다. 다시 말하면 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 갖습니다.

이는 ax + by = c가 정수해를 갖게 하는 c의 최솟값은 gcd(a,b) 라는 것을 의미합니다.

확장 유클리드 호제법은 재귀함수를 사용하여 구현합니다.

확장 유클리드 호제법의 원리 이해하기

5x + 9y = 2 인 경우, 이 식을 만족하는 정수 x,y 구하는 알고리즘 구현

1. 5x + 9y가 정수해를 갖게 하는 c의 최솟값이 gcd(5,9) 라는 것을 적용하여 식을 다시 정하면 gcd(5,9) = 1 이므로 5x + 9y = 1 입니다.

	gcd(a,b) = c(최솟값)
    a = 5, b = 9, c = 1

2. a,b로 유클리드 호제법을 반복 실행하며, 몫과 나머지를 저장합니다. 반복은 나머지가 0이 되면 종료합니다.

5%9 = 나머지 : 5, 몫 : 0;

9%5 = 나머지 : 4, 몫 : 1;

5%4 = 나머지 : 1, 몫 : 1;

4%1 = 나머지 : 0, 몫 : 4;

3. 반복을 통해 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y = x' - y' * q라는 식으로 계산해줍니다. 이때 처음 시작하는 x,y는 x'와 y'가 없기 때문에 x' = 1, y' = 0으로 지정하여 계산해줍니다.
   (x' : 이전 x, y' : 이전 y, q : 현재 보고 있는 몫)

역계산을 통해 x,y값을 유추
x = y'
y = x' - y' * q

이전 x = 1, y = 0
1st x = 0, y = 1 - 0 * 4 = 1
2nd x = 1, y = 0 - 1 * 1 = -1
3rd x = -1, y = 1 - ( -1 * 1) = 2
4th x = 2, y = -1 - (2 * 0) = -1

x = 2, y = -1

4. 위 재귀 방식으로 알아낸 최종 x,y는 ax + by = gcd(a,b)를 만족합니다. 그리고 c/gcd(a,b) = K를 가정하면, 최초 방정식의 해는 Kx, Ky로 간단히 구할 수 있습니다.

2 / gcd(5,9) = 2/1 = 2 = K

Kx Ky - x : 4, y : -2