정수론 : 확장 유클리드 호제법

확장 유클리드 호제법

유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면, 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것

 

 

해를 구하고자 하는 방정식

ax + by = c (a, b, c, x, y는 정수)

 

-> 이때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가짐

-> c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가짐

 

 

예) 5x + 9y = 2일 때 이 식을 만족하는 정수 x, y를 구해보자.

1.  c의 최솟값이 gcd(5, 9)라는 것을 적용해 식을 다시 세운다. -> gcd(5, 9) = 1 이므로 5x + 9y = 1로 식을 다시 세움

2. a, b로 유클리드 호제법을 반복 실행해 몫과 나머지를 저장한다.

3. gcd(5, 9) 수행

 

4. 3번에서 구한 나머지와 몫을 이용해 거꾸로 올라가며 x = y', y = x' - y' * q 계산 (x'는 이전 x, y'는 이전 y, q는 현재 바라보는 몫)

이때 첫 x와 y에는 이전 x와 y가 없으므로 각각 1, 0 으로 지정하고 진행

 

4-1. 밑에서부터 역순으로 진행

[나머지 : 5, 몫 : 0] x = 2, y = -1 - (2 * 0) = -1

[나머지 : 4, 몫 : 1] x = -1, y = 1 - (-1 * 1) = 2

[나머지 : 1, 몫 : 1] x = 1, y = 0 - 1 * 1 = -1

[나머지 : 0, 몫 : 4] x = 0, y = 1 - 0 * 4 = 1

 

5. 최종 x, y는 ax + by = gcd(a, b)를 만족하게 된다. c / gcd(a, b) = k를 가정하면 최초 방정식의 해는 kx와 ky가 된다.

2 * 2와 2 * -1에 의해 방정식의 해는 4, -2가 된다.

 

 

* 만약 오른쪽 변의 값이 gcd(a, b)의 배수가 아니라면?

이 경우를 만족하는 x와 y의 값은 정수 범위에서 존재하지 않는다. 따라서 확장 유클리드 호제법을 구현할 때 먼저 오른쪽 변의 값이 gcd(a, b)를 만족하는지 먼저 판단해야 한다. 만약 조건을 만족하지 않는다면 이후 프로그램을 수행하지 않고 불가능을 표현하는 값을 출력하면 된다.