Thuật toán Euclide mở rộng
Định lý Bézout
Cho \(a,b \in \mathbb N: \gcd(a,b) = 1\) tồn tại \(x,y \in \mathbb Z\) sao cho \(ax+by=1\)
Chứng minh
Xét tập hợp \(S=\{ax+by | x,y\in \mathbb Z, ax+by>0 \}\). Dễ dàng thấy rằng $S$ không phải là tập rỗng.
Gọi $d $ là phần tử nhỏ nhất của $S$, vậy \(d=ax_0+by_0 \quad (x_0,y_0 \in \mathbb Z)\)
Mục tiêu là ta sẽ chứng minh \(d=1\).
Đầu tiên, ta chứng minh $d$ là ước số của $a$. Ta có: \(a = qd + r \quad (0 \le r \lt d)\)
Vậy \( r= a - qd\) thay \(d=ax_0+by_0\) vào:
\(r=a - q(ax_0+by_0) = a(1-qx_0) + b(-qy_0)\)
Như vậy, $r$ cũng có dạng \(Aa+By\) do đó \(r \in S\). Mà $r < d$, vậy nhất định \(r=0\), nghĩa là $d$ là ước của $a.$ Tương tự như vậy, $d$ cũng là ước của $b$. Mà ta có \(gcd(a,b)=1\) theo giả thuyết vậy \(d=1\), suy ra đpcm.
Nghịch đảo modulo
Nghịch đảo modulo của $a$ theo modulo $m$ là số nguyên $x$ sao cho \(a.x \equiv 1 \mod m\). Ta chuyển đổi để đưa bài toán về định lý Bezout: \(ax \equiv 1 \mod m \iff ax - 1 = my\), hay \(ax - my = 1\).
Điều kiện để tồn tại nghiệm là \(\gcd(a,m)=1\)
Thuật toán Euclide ngược
Ví dụ: Tìm \(x,y \in \mathbb Z\) sao cho \(67x + 12y =1\) hay tìm modulo nghịch đảo của $67$ trong modulo $12$
Chiều xuôi, liên tục chia lấy dư số lớn cho số bé để tìm các số dư:
67 chia 12 dư 7
12 chia 7 dư 5
7 chia 5 dư 2
5 chia 2 dư 1 ngừng
Ta thu được các số dư là 2,5,7. Giờ ta đi tính ngược lên để tìm nhân tử Bezout.
Bắt đầu với 2, ta có 1 = 5-2.2, mà 2=7-5.1, thay vào ta có 1=5-2(7-5.1)=3.5-7.2
Tiếp tục với 5 = 12 - 1.7, thay vào: 1=3(12-1.7)-2.7 = 3.12-5.7
Tiếp tục với 7 = 67 - 5.12, thay vào 1=3.12 - 5(67-5.12)=28.12-5.67
Như vậy \(x=-5, y=28\)