유클리드 호제법의 목적 - 두 수의 최대 공약수 구하기
확장 유클리드 호제법의 목적 - 방정식의 해를 구하기
확장 유클리드 호제법에서 해를 구하고자 하는 방정식
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로 간단히 구할 수 있습니다.
