Cho vành Euclid $A$ và $f,g\in A$ khác $0$. Khi đó tồn tại $d\in A$ sao cho $(f)+(g)=(d)$, ta gọi $d$ là một ước chung lớn nhất của $f,g$, theo đó tồn tại $a,b\in A$ nguyên tố cùng nhau sao cho:
\[af+bg=d\] Ta đã biết rằng trên vành Euclid, ta có thể tìm ước chung lớn nhất dựa trên thuật chia Euclid, nhưng việc tìm hai số $a,b$ để $af+bg=d$ không hiển nhiên chút nào. Bài viết này đi tìm một thuật toán giải quyết bài toán trên cho trường hợp vành số nguyên $\mathbb{Z}$

Ta thống nhất phép chia dư trong bài viết như sau: Với hai số nguyên $a,b$ khác $0$ bất kì, tồn tại duy nhất cặp số nguyên $q,r$ thỏa mãn $0\le r\le |b|$ sao cho $a=bq+r$
Cho hai số nguyên $f,g$ khác $0$. Dùng thuật chia Euclid, ta tìm được ước chung lớn nhất $d$ của chúng là một số tự nhiên.

Giờ ta sẽ xem thuật chia Euclid hoạt động thế nào:
*Bước $1$: Lấy $r_{-1}=f$ chia cho $r_0=g$, được thương $h_1$ và dư $r_1$
*Bước $2$: Lấy $r_0$ chia cho $r_1$, được thương $h_2$ và dư $r_2$
…
*Bước $k$: Lấy $r_{k-2}$ chia cho $r_{k-1}$, được thương $h_{k}$ và dư $r_{k}$
Giả sử đến bước thứ $n$, ta được số dư $r_n=0,r_{n-1}=d$, thuật toán kết thúc và ta kết luận $d$ là một ước chung lớn nhất của $f$ và $g$.
Giờ ta xét một tương ứng giữa hai bộ $(f,g)$ và $(a,b)$ thỏa mãn $af+bg=d$ (kí hiệu $(f,g) \leftrightarrow (a,b)$).
Từ bước 1, ta có $f=gh_1+r_1$ dẫn tới $(b+ah_1)g+ar_1=d$, do đó ta có:
\[(g,r_1)\leftrightarrow (b+ah_1,a)\] Xét dãy $(u_k)_{-1\le k\le n}$ thỏa mãn $u_{-1}=b,u_0=a$ và $u_k=h_{k}u_{k-1}+u_{k-2}$.
Bằng quy nạp ta chứng minh được:
\[(r_{k-1},r_{k})\leftrightarrow (u_k,u_{k-1})\] với mọi $0\le k\le n$.
Ta biết rằng đến bước $n$, $r_n=0$ và $r_{n-1}=d$ nên $(r_{n-1},r_n)\leftrightarrow (1,0)$.
Do đó ta chỉ cần chọn $a,b$ sao cho $u_n=1,u_{n-1}=0$. Đến đây ta có thể tính ngược từ $u_n$ lên giá trị của $u_1$ và $u_0$, hình thức hơn đặt $v_k=u_{n-k}$ thì ta có:
\[\left\{ \begin{array}{l}
v_0=1, v_1=0\\
v_k=h_{n-k+2}v_{k-1}+v_{k-2}
\end{array} \right.\] Khi đó ta tính được $a=v_n$ và $b=v_{n+1}$.

*KẾT LUẬN:
Cho trước hai số nguyên $f,g$ khác $0$ có $d$ là ước chung lớn nhất. Để tìm các số nguyên $a$ và $b$ để $af+bg=d$ ta làm như sau:
Bước 1: Thực hiện thuật chia Euclid, từ đó xác định được số lần thực hiện thuật chia và các thương số mỗi lần chia.
Bước 2: Giả sử ta thực hiện thuật chia $n$ lần và thương số lần lượt là $h_1,h_2,…,h_n$, xét dãy:
\[\left\{ \begin{array}{l}
v_0=1, v_1=0\\
v_k=h_{n-k+2}v_{k-1}+v_{k-2}
\end{array} \right.\] Khi đó $a=v_n$ và $b=v_{n+1}$

Có thể thấy rằng thuật toán trên cũng áp dụng tốt cho vành đa thức. Một số ví dụ áp dụng sẽ để dành cho bài viết sau.