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

확장 유클리드 호제법

유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하려면 수학 증명 과정까지 공부해야 한다고 하지만 여기서는 확장 유클리드 호제법 관련 문제를 풀기 위한 알고리즘만 설명하려고 한다.

확장 유클리드 호제법의 핵심 이론 
확장 유클리드 호제법에서 해를 구하고자 하는 방정식

해를 구하고자 하는 방정식
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로 식을 다시 놓고 다음 단계를 진행한다.

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

3 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x=y', y= x'-y’*q를 계산한다. x'는 이전 x, y'는 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미. 이때 처음 시 작하는 x,y는 이전 x와 이전 y가 없으므로 각각 1, 0으로 지정하여 역계산을 진행.

4 이렇게 재귀 방식으로 알아낸 최종 x, y는 ax + by = gcd(a, b)를 만족한다. 
그리고 c/ gcd(a, b) = K를 가정하면 최초 방정식의 해는 Kx, Ky로 간단히 구할 수 있다. 과정 3 에서 찾은 x는 2, y는 -1이고 K값을 구하면 2(c값) / 1(최대 공약수) = 2가 되므로 2의 값 을 기존의 x(2), y(-1) 값에 각각 곱한다. 이에 따라 최초 방정식의 해는 4, -2가 된다.

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

위 예제에서 만약 오른쪽 변의 값이 gcd(A, B)의 배수의 형태가 아니라면 어떻게 X, Y의 값을 도출할 수 있을까? 

결론적으로 이 경우를 만족하는 X, Y 값은 정수 범위에서 존재 하지 않는다. 따라서 확장 유클리드 호제법을 구현할 때 먼저 오른쪽 변의 값이 gcd(A,B)의 배수라는 조건을 만족하는지 먼저 판단해야 한다. 만약 조건에 만족하지 않는다면 이후 프로그램을 수행하지 않고 불가능을 표현하는 값을 출력하면 된다. 또한 유클리드 호제법의 구조 자체가 특정한 값을 업데이트시키면서 같은 로직을 반복적으로 수행하므로 재귀 함수의 형태로 구현한다.

 

관련 문제

 

https://www.acmicpc.net/problem/21568

21568번: Ax+By=C

 

 

책 <Do It! 알고리즘 코딩테스트>_김종관 지음, 이지스퍼블리싱 출판사

학교 알고리즘 수업 강의자료 등 여러 자료 참고해서 공부함.