확장 유클리드 알고리즘

objective

$gcd(a,b)=ax+by$를 만족하는 x,y를 찾아보자!

motivation

기본적으로 유클리드 알고리즘은 다음과 같은 사실에 의존한다.

$a=bq+r$ 일때, $gcd(a,b)=gcd(b,r)$이 성립한다.

위와 같은 성질이 성립하기 때문에 나눗셈 정리를 반복 적용하여 최대공약수를 구할 수 있다.

구체적으로 다음과 같이 적어보자.

$$a = bq_1 + r_1\\ b = r_1q_2 + r_2\\ r_1 = r_2q_3 + r_3\\\ ...\\ r_{n-2} = r_{n-1}q_n + r_n\\ r_{n-1} = r_{n}q_{n+1}$$

이때

$$gcd(a,b)=gcd(b,r_1)=gcd(r_1,r_2)=...=gcd(r_{n-2},r_{n-1}) = gcd(r_{n-1},r_n)= gcd(r_n,0)$$

가 성립하기 때문에 최대공약수를 구할수 있다.

이제 이 식을 조금 정리하면,(마지막 제외)

$$r_1 = a - bq_1\\ r_2 = b - r_1q_2 \\ r_3 = r_1 - r_2q_3\\ ...\\ r_n = r_{n-2} - r_{n-1}q_n$$

을 얻고, 이를 이제 $r_{n}$ 에다가 $r_{n-1},r_{n-2},...,r_2$ 까지 차례대로 대입하면 a와 b의 일차결합꼴로 나타낼수있음을 확인할수있다.

하지만 이 작업은 손으로 하기에는 너무 귀찮고 힘들다.. 역시 이런 작업은 컴퓨터한테 시키는게 정신건강에 좋을것이다.

algorithm

저 위에서 얻은 식과 두 수의 최대공약수는 두 수의 일차결합으로 나타낼수있다는 사실을 가지고 알고리즘을 얻어보자.

위에서 얻은 식을 토대로 다음과 같은 식을 얻을수있다.

$$r_{i+1} = r_{i-1} - r_iq_i$$

그리고 각 $r_{i+1}$이 0이 되면 이는 유클리드 알고리즘이 끝났다는 뜻이니 이를 탈출 조건으로 정해주면 되겠다.

그리고 이 식이 a와 b의 일차결합으로 나타내어짐을 보장하기 위하여 $r_0=a, r_1=b$로 설정하자. 그러면 $r_0 = a * 1 + b * 0, r_1 = a * 0 + b* 1$ 이기때문에 일차 결합으로 나타내어지고 따라서 나머지 $r_i$들도 a와 b의 일차결합으로 나타내어질것이다.(귀납법으로 쉽게 증명가능.)

그리고 $0 \leq r_{i+1} < \abs{r_i}$ 이기 때문에 언젠간 $r_{i+1}$은 0에 도달한다.

그리고 각 $r_i$들은 ax+by꼴로 나타내어지니 $r_i$의 a의 계수를 $s_i$ b의 계수를 $t_i$라고 두면,

$r_i = s_ia + t_ib$로 둘수있고, 이를 점화식에 대입하면 $s_i,t_i$의 점화식을 얻을수있다.

$$s_0 = 1,t_0=0\\ s_1=0,t_1=1\\ s_{i+1}=s_{i-1}-q_is_i\\ t_{i+1}=t_{i-1}-q_it_i$$

이제 위 식을 이용해서 그대로 코드로 옮겨주면 된다.

fn egcd(a: i32, b: i32) -> (i32,i32,i32) {
    let (mut s, mut t, mut r) = (0,1,b);
    let (mut old_s, mut old_t, mut old_r) = (1,0,a);

    while r != 0 {
        let q = old_r / r;
        let new_r = old_r - q*r;
        let new_s = old_s - q*s;
        let new_t = old_t - q*t;

        old_r = r;
        r = new_r;
        old_s = s;
        s = new_s;
        old_t = t;
        t = new_t;
    }
    (old_r,old_s,old_t)
}