## Thuật toán Euclid
Thuật toán Euclid tính $\gcd(a, b)$: $$\gcd(a, b) = \begin{cases}a &\text{nếu }b = 0 \\ \gcd(b, a \bmod b) &\text{nếu }b \neq 0 \end{cases}$$

int gcd(int a, int b) {
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

## Thuật toán Euclid mở rộng
Thuật toán Euclid mở rộng ngoài tính gcd của 2 số ra còn tính được 2 hệ số $x$ và $y$ sao cho: $$a \cdot x + b \cdot y = \gcd(a, b)$$

### Thuật toán
Gọi $\gcd(a, b)$ là $g$.

Trong thuật toán Euclid, khi gặp trường hợp $b = 0$, vậy khi đó $a = g$ và $b = 0 \Rightarrow a \cdot x + b \cdot y = g \iff g \cdot x + 0 \cdot y = g \Rightarrow x = 1, y = 0$
Vậy $x = 1, y = 0$ trong base case.

Ta có $\gcd(a, b) = \gcd(b, a \bmod b) = g$.
Giả sử ta đã tìm được $x_1$ và $y_1$ là cặp $x, y$ đối với $\gcd(b, a \bmod b)$.
Nói cách khác, đã tìm được $x_1, y_1$ sao cho $b \cdot x_1 + (a \bmod b) \cdot y_1 = g$

Đầu tiên, ta viết lại $a \bmod b$ thành $a - \left\lfloor {a \over b} \right\rfloor \cdot b$: $$b \cdot x_1 + \left(a - \left\lfloor {a \over b} \right\rfloor \cdot b\right) \cdot y_1 = g$$
Tách ra: $$b \cdot x_1 + a \cdot y_1 - \left\lfloor {a \over b} \right\rfloor \cdot b \cdot y_1 = g$$
Lấy $b$ làm nhân tử chung: $$a \cdot y_1 + b \cdot \left(x_1 - \left\lfloor {a \over b} \right\rfloor \cdot y_1\right) = g$$
Vậy ta đã tìm được cặp hệ số $x, y$ đối với $a, b$: $$\begin{cases} x = y_1 \\ y = x_1 - \left\lfloor{a \over b}\right\rfloor \cdot y_1 \end{cases}$$

int extended_euclidean(int a, int b, int& x, int& y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = extended_euclidean(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}