나는 야호다.

수학게이라서 수학글을 쓰려고 고민하던 중, 확장유클리드 알고리즘에 대해서 글을 써볼까한다.

우선 확장유클리드 알고리즘에 앞서 유클리드 호제법에 대해 알아보자. 유클리드 호제법은 두 숫자 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;
}

야호에게 원리를 물어보니 야호 가라사대 "별건 아니고, 그냥 나온 답 가지고 적당히 덧셈 뺄셈 해서 최소해 찾는거임 ㅇㅇ"라고 한다.

Reference