Giải thuật Euclid mở rộng

Giải thuật Euclid mở rộng được sử dụng để giải một phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) có dạng
formula_1
Trong đó formula_2 là các hệ số nguyên, formula_3 là các ẩn nhận giá trị nguyên. Điều kiện cần và đủ để phương trình này có nghiệm (nguyên) là formula_4 là ước của formula_5. Khẳng định này dựa trên một mệnh đề sau:
"Nếu formula_6 thì tồn tại các số nguyên formula_3 sao cho formula_8
Cơ sở lý thuyết của giải thuật.
Giải thuật Euclid mở rộng kết hợp quá trình tìm ƯCLN"(a, b)" trong thuật toán Euclid với việc tìm một cặp số x, y thoả mãn phương trình Đi-ô-phăng.
Giả sử cho hai số tự nhiên a, b, ngoài ra a&gt;b&gt;0.
Đặt formula_9, chia formula_10 cho formula_11 được số dư formula_12 và thương số nguyên formula_13. Nếu formula_14 thì dừng,
nếu formula_12 khác không, chia formula_11 cho formula_12 được số dư formula_18...Vì dãy các formula_19 là giảm thực sự nên sau hữu hạn bước ta được số dư formula_20.
trong đó số dư cuối cùng khác 0 là formula_25.
Bài toán đặt ra là tìm x, y sao cho 
Để làm điều này, ta tìm x, y theo công thức truy hồi, nghĩa là sẽ tìm
Ta có 
Tổng quát, giả sử có 
Khi đó từ
suy ra
từ đó, có thể chọn 
Khi formula_45 ta có được formula_46 và formula_47.
Các công thức (1), (2), (3) là công thức truy hồi để tính x, y.
Giải thuật.
function gcd(a, b);
begin
 while b ≠ 0 do
 begin
 r:= a mod b; a:= b; b:= r;
 end;
 Result:= a;
end;
function Extended_gcd(a, b); 
begin
 (xa, ya):= (1, 0);
 (xb, yb):= (0, 1);
 while b ≠ 0 do
 begin
 q:= a div b;
 r:= a mod b; a:= b; b:= r; //Đoạn này giống thuật toán Euclide.
 (xr, yr):= (xa, ya) - q * (xb, yb); //Hiểu là: (xr, yr):= (xa, ya) "mod" (xb, yb);
 (xa, ya):= (xb, yb);
 (xb, yb):= (xr, yr);
 end;
 Result:= (xa, ya);
end;
Giải thuật sau chỉ thực hiện với các số nguyên a&gt;b&gt;0, biểu diễn bằng giải mã:
 Sub Euclid_Extended(a,b)
 Dim x0, x, y,y1 As Single
 x0=1: x1=0: y0=0: y1=1
 While b&gt;0
 r= a mod b 
 if r=0 then Exit While
 q= a / b
 x= x0-x1*q
 y= y0-y1*q
 a=b
 b=r
 x0=x1 
 x1=x
 y0=y1 
 y1=y
 Wend
 Me.Print d:=b, x, y
code
 End Sub
Ví dụ.
Với a=29, b=8, giải thuật trải qua các bước như sau:
Kết quả thuật toán cho đồng thời formula_48 và formula_49, formula_50.
Dễ dàng kiểm tra hệ thức formula_51
Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành formula_52.
Số nghịch đảo trong vành formula_52.
Trong lý thuyết số, vành formula_52 được định nghĩa là vành thương của formula_55 với quan hệ đồng dư theo modulo m (là quan hệ tương đương) mà các phần tử của nó là các lớp đồng dư theo modulo m (m là số nguyên dương lớn hơn 1). Ta cũng có thể xét formula_52 chỉ với các đại diện của nó. Khi đó
formula_57
Phép cộng và nhân trong formula_58 là phép toán thông thường được rút gọn theo modulo m:
formula_59
formula_60
Phần tử a của formula_52 được gọi là khả nghịch trong formula_52 hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong formula_52 sao cho a*a'=1 trong formula_52 hay formula_65. Khi đó a' được gọi là nghịch đảo modulo m của a. Trong lý thuyết số đã chứng minh rằng, số a là khả nghịch theo modulo m khi và chỉ khi ƯCLN của a và m bằng 1.
Khi đó tồn tại các số nguyên x, y sao cho
 formula_66 
Đẳng thức này lại chỉ ra y là nghịch đảo của a theo modulo m. Do đó có thể tìm được phần tử nghịch đảo của a theo modulo m nhờ thuật toán Euclid mở rộng khi chia m cho a.
Giải thuật.
//a, m &gt; 0. Trả về a^-1 mod m, gcd(a, m) phải bằng 1, chú ý là ta không cần quan tâm y khi giải pt diophante a * x + m * y = 1
function ModuloInverse(a, m);
begin
 xa:= 1; xm:= 0;
 while m ≠ 0 do
 begin
 q:= a div m;
 xr:= xa - q * xm;
 xa:= xm;
 xm:= xr;
 r:= a mod m;
 a:= m;
 m:= r;
 end;
 Result:= xa;
end;
Giải thuật sau chỉ thực hiện với các số nguyên m&gt;a&gt;0, biểu diễn bằng giã mã:
 Procedure Euclid_Extended (a,m)
 "int", y0:=0,y1:=1;
 While a&gt;0 do {
 r:= m mod a 
 if r=0 then Break 
 q:= m div a
 y:= y0-y1*q
 y0:=y1 
 y1:=y
 m:=a
 a:=r
 If a&gt;1 Then Return "A không khả nghịch theo mođun m" 
 else Return " Nghịch đảo modulo m của a là y"
Ví dụ.
Tìm số nghịch đảo (nếu có) của 30 theo môđun 101
Kết quả tính toán trong bảng cho ta formula_67. Lấy số đối của formula_68 theo mođun formula_69 được formula_70. Vậy formula_71.
Ứng dụng.
Số nghịch đảo theo môđun được ứng dụng nhiều trong việc giải phương trình đồng dư, trong lý thuyết mật mã.