# The Extended Euclidean Algorithm

$ax+by=\gcd(a,b)$를 만족하는 베주 항등식(Bézout's identity)의 계수(Coefficient)를 x, y를 구하는 알고리즘이다.

## 베주 항등식
### 정의
둘 중 하나는 0이 아닌 정수 a,b에 대해 gcd(a,b)=d라고 하면 다음 3가지 명제를 만족한다.

1) ax+by=d를 만족하는 정수 x,y가 존재한다.
2) d는 정수 x,y에 대하여 ax+by로 표현할 수 있는 가장 작은 정수이다.
3) ax+by로 표현될 수 있는 모든 정수는 d의 배수이다.

### 증명
둘 중 하나는 0이 아닌 정수 a, b에 대해서 집합 S를 다음과 같이 정의한다.

$$
S = \left \{ax+by \gt 0 \mid x,y \in \Bbb{Z} \right \}
$$

이 집합이 공집합이 아니라면 정렬성의 원리에 의해 최소 원소를 가진다.

> 공집합이 아니고, 음이 아닌 정수들을 원소로 갖는 모든 집합 S는 최소 원소를 가진다.
> 다시 말해, S는 S에 속하는 모든 원소 b에 대해 $a\leq b$ 를 만족하는 a를 포함한다.

( 정수에 대한 정의까지 들어가고 싶다면 [이 글](https://chocobear.tistory.com/36?category=851735)을 추천한다. )

그렇다면 공집합이 아닌지를 증명해보자

$$
if \; a\gt 0, \lvert a \rvert = a \cdot 1 + b \cdot 0 \in S \\
if \; a\lt 0, \lvert a \rvert = a \cdot -1 + b \cdot 0 \in S \\
if \; a = 0, \; then \; b \neq 0, \; \lvert a \rvert = 0 \cdot x + b \cdot 0 \in S
$$

모든 a에 대하여 $\lvert a \rvert$가 집합 S에 속하므로 공집합이 아니다.
반대로 b를 가지고 해도 동일 결과가 난다, 즉 $\lvert a \rvert$, $\lvert b \rvert$ 중에 적어도 하나는 집합 S에 속한다.
그렇게 ax+by로 나타낼 수 있는 최소 원소를 가짐을 보였고 이 값을 d라고 하겠다.

$$
d = ak + bl \; (k,l \in \Bbb{Z}) \\
x = au + bv \; (u,v \in \Bbb{Z}) \\
x = dq + r \; ( 0 \leq r \lt d) \\
if \; d \nmid x, \; then \; r \neq 0 \; , \; r \in \Bbb{N} \\
au + bv = (ak + bl) \cdot q + r \\
a(u-kq) + b(v-kl) = r \in S \\
r \lt d, but \; \forall x \in S \gt d \\
thus \; d \mid x
$$

위에서 증명했듯이 집합 S의 모든 원소는 d를 약수로 가진다.
$$
a\cdot(1) + b\cdot(0) = a \\
a\cdot(0) + b\cdot(1) = b
$$
a,b도 집합 S의 원소이므로 d는 a,b의 공약수이다.

e가 a,b의 공약수라 하면 a = a'e, b = b'e라 할 수 있다.
d = ak + bl = e(a'k + b'l) 이므로 e|d이다.
모든 공약수가 d의 약수이므로 d = gcd(a,b)

이로써 최소원소 d 가 gcd(a,b) 임을 보였고 일련의 과정을 통해 3가지 명제를 만족함을 보였다.

## 확장된 유클리드 알고리즘

### 유클리드 알고리즘
$$
a = bq+r \; (0 \leq r \lt b)\\
\gcd(a,b) = \gcd(b,r)
$$
두번째 식을 증명해보자면
$$
d = gcd(a,b) \\
a = dA,\; b = dB \\
dA = dBq + r \\
r = d(A-Bq) \\
gcd(b,r) = gcd(dB, d(A-Bq))
$$
$B$와 $A-Bq$가 서로소가 아니라고 가정하자
$$
A-Bq = kB \\
A = B(K+q)
$$
하지만 A, B는 서로소여야 하므로 모순이다.
즉 $B$와 $A-Bq$가 서로소이며 $gcd(b,r) = gcd(dB, d(A-Bq)) = d$ 를 만족한다.

해당 알고리즘을 활용하기 위하여 $a_n$의 점화식을 세워보자
$a_0 = a, a_1 = b$ 라 정의하면
$a_{n-1} = a_nq_n + a_{n+1}$ 으로 전개가 가능하며 $a_{n+1} = 0$ 일 때 $a_n = gcd(a,b)$ 이다.

### 전개
우리는 a,b를 알고 있고 x, y를 알려고 한다.

$$
y_n = 0, \; y_{n-1}=1 \\
y_{k-1} = y_kq_k + y_{k+1} \quad (for \; k = n-2, \cdots ,2,1)
$$

위와 같은 $y_n$의 점화식을 정의해보자

이 때 $(1 \leq k \leq n)$ 에서 $(-1)^{n+k+1}a_{k-1}y_k + (-1)^{n+k}a_ky_{k-1} = a_n$이 성립한다.

$$
k = n, (-1)^{2n+1}a_{n-1}y_n + a_ny_{n-1} = a_n \\
k = k-1, (-1)^{n+k}a_{k-2}y_{k-1} + (-1)^{n+k-1}a_{k-1}y_{k-2} \\
since \; (-1)^2 = 1 \; (-1)^{n+k}a_{k-2}y_{k-1} + (-1)^{n+k+1}a_{k-1}y_{k-2}
$$

$a_{k-2} = a_{k-1}q_{k-1} + a_k$ 이므로

$$
=(-1)^{n+k}(a_{k-1}q_{k-1} + a_k)y_{k-1} + (-1)^{n+k+1}a_{k-1}y_{k-2} \\
=(-1)^{n+k}a_ky_{k-1} + (-1)^{n+k}(a_{k-1}q_{k-1}y_{k-1}) + (-1)^{n+k+1}a_{k-1}y_{k-2} \\
=(-1)^{n+k}a_ky_{k-1} + (-1)^{n+k+1}((-1)\cdot a_{k-1}q_{k-1}y_{k-1}) + (-1)^{n+k+1}a_{k-1}y_{k-2} \\
=(-1)^{n+k}a_ky_{k-1} + (-1)^{n+k+1}a_{k-1}(y_{k-2} - q_{k-1}y_{k-1})
$$

$y_{k-2} - y_{k-1}q_{k-1} = y_k$ 이므로
$$
=(-1)^{n+k}a_ky_{k-1} + (-1)^{n+k+1}a_{k-1}y_k = a_n
$$

일련의 과정을 통해 성립함을 보였고 이제 k=1을 대입하면 $(-1)^na_0y_1 + (-1)^{n+1}a_1y_0 = a_n$ 이다.
우리가 알고싶은 값들은 각각 $x = (-1)^ny_1, \; y = (-1)^{n+1}y_0$ 임을 알게 되었다.

### 구현

마지막으로 해당 코드를 구현해보자
y_n을 구하면서 q_n을 구하자니 방향이 서로 엇갈려서
q_n을 미리 다 구해두고 y_n을 구하도록 하겠다.

def egcd(a, b):
    _q = []
    while b != 0:
        _q.append(a//b)
        a,b = b, a%b
    n = len(_q)
    _q.pop()
    # [y_{n-2}, y_{n-1}, y_{n}]
    y = [0,1,0]
    for q in reversed(_q):
        y[0] = y[1] * q + y[2]
        y[2], y[1] = y[1], y[0]
    return (-1)**n * y[2], (-1)**(n+1) * y[1]

구글링을 좀 해보니 보통 아래와 같은 방식으로 구한다.
근데 해당 방식의 증명 방법이 맘에 들지 않아서 난 쓰진 않았다.
(코드가 아래가 훨 깔끔해보여서 맘에 드는 증명 방식을 찾으면 바로 아래로 전환할려고 한다... )

def egcd(a, b):
    u, u1 = 1, 0
    v, v1 = 0, 1
    g, g1 = a, b
    while g1:
        q = g // g1
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        g, g1 = g1, g - q * g1
    return u, v, g

내 코드에서 gcd 값도 반환해주고 싶다면 a, b를 백업해두고 결과로 나오는 s,t 에 곱해서 sa+bt를 계산하면 된다.