Extended Euclidean Algorithm (증명 X)

확장 유클리드 알고리즘(Extended Eucildean Algorithm)이란 ax + by = c 같은 부정방정식이 주어졌을 때, (x, y)의 정수해를 알아내는 알고리즘입니다.

 

증명은 따로 하지 않으며 배운 곳까지만 작성하겠습니다. 증명 자료를 찾으려니 이해가 안 되는 부분들이 꽤나 많았습니다.

 

[사전 지식]

 

ax + by = c와 같이 미지수의 개수가 식의 개수보다 많아서 근이 일정하지 않은 방정식을 부정방정식(Underdetermined Equation)이라고 합니다.

 

그리고, ax + by = c에서 정수해를 구한다고 하였는데 부정방정식에서 정수해를 구하는 방정식을 디오판토스 방정식(Diophantine Equation)이라고 합니다.

=> 사실 이 용어는 그닥 중요하지 않습니다.

 

ax + by = c에서 정수해가 존재하려면 베주 항등식(Bezout's Identity)의 명제에 의거하여 c = gcd(a, b)의 정수배여야 합니다.

 

---

위에서 말했듯이 이번 포스팅에서 증명은 따로 하지 않습니다.

 

확장 유클리드 알고리즘은 두 정수 a, b의 나머지 정리와 유클리드 알고리즘을 반복하면서 정리할 수 있습니다.

반복하면서 정리하여 얻은 식들을 나열해보겠습니다.

 

r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1

r = r1 -  r2 * q

s = s1 - s2 * q

t = t1 - t2 * q

코드가 반복되는 과정에서

r2 -> r1, r -> r2

s2 -> s1, s -> s2

t2 -> t1, t -> t2

r2가 0이 되는 시점에서 알고리즘 종료

 

종료된 시점에서 r1 = gcd(a, b), s1 = x, t1 = y가 됩니다.

즉, ax + by = c는 a*s1 + b*t1 = r1이 됩니다.

 

#include <iostream>
using namespace std;

void exGCD(int a, int b){
    int r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
    int r, s, t;
    
    while(true){
        int q = r1 / r2;
        
        r = r1 - q * r2;
        r1 = r2;
        r2 = r;
        
        s = s1 - q * s2;
        s1 = s2;
        s2 = s;
        
        t = t1 - q * t2;
        t1 = t2;
        t2 = t;
        
        if(r2 == 0) break;
    }
    
    cout << "gcd(a, b): " << r1 << '\n';
    cout << "x: " << s1 << " y: " << t1;
}

int main(){
    int a, b; cin >> a >> b;
    exGCD(a, b);
}