Extended Euclidean Algorithm
gcd부터 canon_egcd까지
나는 야호다.
수학게이라서 수학글을 쓰려고 고민하던 중, 확장유클리드 알고리즘에 대해서 글을 써볼까한다.
우선 확장유클리드 알고리즘에 앞서 유클리드 호제법에 대해 알아보자. 유클리드 호제법은 두 숫자 a,b의 최대공약수 gcd(a,b)를 구하는 알고리즘으로 다음의 성질을 이야기 한다.
gcd(a,b) = gcd(b,a%b)
증명은 다음과 같다.
a를 b로 나누어 보면 a=b*q+r (q는몫, r는 나머지)로 나타낼수 있다. 여기서 gcd(b,r)|b, gcd(b,r)|r이므로 gcd(b,r)|a가 성립한다. gcd(b,r)|b, gcd(b,r)|a이므로 gcd(b,r)|gcd(a,b)가 성립한다.
또한, 이를 나머지 r에 대한 식으로 정리하면, r=a-b*q라는 식을 얻을 수 있다. 같은 방법으로 gcd(a,b)|gcd(b,r)를 얻을수 있고 gcd(a,b)=gcd(b,r)=gcd(b,a%b)가 성립한다.
이를 프로그램으로 구현해보자.
int gcd(int a, int b)
{
if(b==0) return a;
return gcd(b,a%b);
}이를 응용해서 확장 유클리드 알고리즘도 가능하다.
gcd(a,b)를 구하면서, ax+by=gcd(a,b)의 해를 구하는 것인데
이는 유클리드 호제법을 약간 응용할 수 있다.
gcd(a,b)=gcd(b,a%b)이므로 우리는 기존문제보다 더 작은 문제인
bx' + (a%b) y'=gcd(a,b)의 해를 이미 알고 있다고 가정하자. 그러면 ax+by=gcd(a,b)의 해는 다음의 과정으로 구할수 있다.
ax + by
= (a%b + a/b*b)x + by
= a%b*x + a/b*b*x + by
= a%b*x + b(y+a/b*x)
= gcd(a,b)
x' = y+a/b*x, y'=x -> x=y', y=x'-a/b*x
따라서 다음과 같이 재귀적으로 구할수 있다.
int extgcd(int a, int b, int&x, int&y)
{
if(b==0)
{
x=1; y=0;
return a;
}
int d=extgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}참 쉽죠?
또한 이렇게 구한 x,y는 굉장히 작은 범위에 국한되어있는데,
|x|<=b, |y|<=a가 만족하게 되는데, 이것은 extgcd 과정에 따라 수학적 귀납법으로 증명하면 가능하므로, 증명은 독자에게 맡긴다.(별로 안어렵다)
이상으로 확장유클리드 호제법이었다.
내용 추가 @Optatum, 2019-10-31, 19:52
egcd와 관련된 내용 중에 Canonical Extended GCD 라는 것도 있어서 코드 조각 첨부해본다. a, b, c >= 0인 정수에 대해서 ax - by = c를 만족하는 해 (x, y)가 없으면 false를 리턴하고, 해가 있다면 true를 리턴하며 x, y >= 0을 만족하는 가장 작은 해를 찾아 준다고 한다.
bool canon_egcd(int a, int b, int c, int& x, int& y) {
int d = egcd(a, b, x, y);
if (c%d) return false;
y = ((-y*c/d)%(a/d) + (a/d))%(a/d);
x = (c + b*y)/a;
return true;
}
야호에게 원리를 물어보니 야호 가라사대 "별건 아니고, 그냥 나온 답 가지고 적당히 덧셈 뺄셈 해서 최소해 찾는거임 ㅇㅇ"라고 한다.