Thuật toán Euclid

Thuật toán Euclid tính

$gcd(a,b)$:

$$gcd(a,b)=\{\begin{array}{ll}a& \text{nếu }b=0\\ gcd(b,amodb)& \text{nếu }b\ne 0\end{array}$$

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⟺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,amodb)=g$.
Giả sử ta đã tìm được

$x_1$ và

$y_1$ là cặp

$x,y$ đối với

$gcd(b,amodb)$.
Nói cách khác, đã tìm được

$x_1,y_1$ sao cho

$b\cdot x_1+(amodb)\cdot y_1=g$

Đầu tiên, ta viết lại

$amodb$ thành

$a-\lfloor \frac{a}{b}\rfloor \cdot b$:

$$b\cdot x_1+(a-\lfloor \frac{a}{b}\rfloor \cdot b)\cdot y_1=g$$
Tách ra:

$$b\cdot x_1+a\cdot y_1-\lfloor \frac{a}{b}\rfloor \cdot b\cdot y_1=g$$
Lấy

$b$ làm nhân tử chung:

$$a\cdot y_1+b\cdot (x_1-\lfloor \frac{a}{b}\rfloor \cdot y_1)=g$$
Vậy ta đã tìm được cặp hệ số

$x,y$ đối với

$a,b$:

$$\{\begin{array}{l}x=y_1\\ y=x_1-\lfloor \frac{a}{b}\rfloor \cdot y_1\end{array}$$

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;
}