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

ax + by =c

Trong đó a, b, c là các hệ số nguyên, x, y 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à UCLN(a, b) là ước của c. Khẳng định này dựa trên một mệnh đề sau:

*Nếu <math>d = UCLN(a, b)</math> thì tồn tại các số nguyên <math>x, y</math> sao cho <math>ax + by = d</math>

==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 [[Ước số chung lớn nhất|ƯCLN]]*(a, b)* trong [[Giải thuật Euclid|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>b>0.
Đặt <math>r_o=a, r_1=b</math>, chia <math>r_0</math> cho <math>r_1</math> được [[số dư]] <math>r_2</math> và thương số nguyên <math>q_1</math>. Nếu <math>r_2=0</math> thì dừng,
nếu <math>r_2</math> khác không, chia <math>r_1</math> cho <math>r_2</math> được [[số dư]] <math>r_3</math>,...Vì dãy các <math>r_i</math> là giảm thực sự nên sau hữu hạn bước ta được [[số dư]] <math>r_{m+2}=0</math>.<br/>
::<math>r_o=q_1*r_1+r_2, 0<r_2<r_1</math>;
::<math>r_1=q_2*r_2+r_3, 0<r_3<r_2</math>;
::....;
::<math>r_{m-1}=q_m*r_m+r_{m+1},0<r_{m+1}<r_m</math>
::<math>r_m=q_{m+1}*r_{m+1}</math>
trong đó [[số dư]] cuối cùng khác 0 là <math>r_{m+1}=d</math>.
Bài toán đặt ra là tìm x, y sao cho 
::<math>a*x+b*y = r_{m+1}(=d)</math>
Để 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
::<math>x_i</math> và <math>y_i</math> sao cho:
::<math>a*x_i+b*y_i = r_i</math> với <math>i =0,1,...</math>.
Ta có 
::<math>a*1+b*0= a = r_o</math> và <math>a*0+b*1 =b =r_1</math>, nghĩa là 
::<math>x_o=1,x_1=0</math> và <math>y_o=0,y_1=1</math>. (1)
Tổng quát, giả sử có 
::<math>a*x_i+b*y_i = r_i</math> với <math>i =0,1,...</math>.
::<math>a*x_{i+1}+b*y_{i+1} = r_{i+1}</math> với <math>i =0,1,...</math>.
Khi đó từ
::<math> r_i=q_{i+1}*r_{i+1}+r_{i+2}</math>  
suy ra
::<math> r_i-q_{i+1}*r_{i+1}=r_{i+2}</math>
::<math> (a*x_i+b*y_i) -q_{i+1}*(a*x_{i+1}+b*y_{i+1})=r_{i+2}</math>
::<math>a*(x_i-q_{i+1}*x_{i+1})+b*(y_i-q_{i+1}*y_{i+1})=r_{i+2}</math>
từ đó, có thể chọn<br/>  
::<math>x_{i+2}=x_i-q_{i+1}*x_{i+1}</math>  (2) 
::<math> y_{i+2}=y_i-q_{i+1}*y_{i+1}</math>  (3)
Khi <math>i=m-1</math> ta có được <math>x_{m+1}</math> và <math>y_{m+1}</math>.
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===
<syntaxhighlight lang="pascal">
{Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)}
function gcd(a, b);
begin
  while b ≠ 0 do
    begin
      r:= a mod b; a:= b; b:= r;
    end;
  Result:= a;
end;
{Thuật toán Euclide mở rộng: a, b không đồng thời bằng 0, trả về cặp (x, y) sao cho a * x + b * y = gcd(a, b)
Về tư tưởng là ghép quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclide.}
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;
</syntaxhighlight>
Giải thuật sau chỉ thực hiện với các số nguyên a>b>0, biểu diễn bằng giải mã:
<syntaxhighlight lang="vb">
 Sub Euclid_Extended(a,b)
 Dim x0, x, y,y1 As Single
    x0=1: x1=0: y0=0: y1=1
 
 While b>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
</syntaxhighlight>

===Ví dụ===
Với a=29, b=8, giải thuật trải qua các bước như sau:
<Center>

</Center>
Kết quả thuật toán cho đồng thời <math>d=UCLN(29,8)=1</math> và <math>x=-3</math>, <math>y=11</math>.
<br/>Dễ dàng kiểm tra hệ thức <math>29*(-3)+8*11=1</math>

==Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành <math>\mathbb{Z}_m</math>==
===Số nghịch đảo trong vành <math>\mathbb{Z}_m</math>===

Trong lý thuyết số, vành <math>\mathbb{Z}_m</math> được định nghĩa là vành thương của <math>\mathbb{Z}</math> 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 <math>\mathbb{Z}_m</math> chỉ với các đại diện của nó. Khi đó
<Center>
<math>\mathbb{Z}_m = \left \{ 0,1,...,m-1 \right \}</math>
</Center>
Phép cộng và nhân trong <math>\mathbb{Z}m</math> là phép toán thông thường được rút gọn theo modulo m:
<Center>
<math>a+b=(a+b) \quad mod \quad m</math>
<br/>
<math>a*b=(a*b) \quad mod \quad m</math>
</Center>
Phần tử a của <math>\mathbb{Z}_m</math> được gọi là khả nghịch trong <math>\mathbb{Z}_m</math>  hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong <math>\mathbb{Z}_m</math>  sao cho a*a'=1 trong <math>\mathbb{Z}_m</math> hay <math>a*a' \equiv 1\pmod m</math>. 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.<br/>
Khi đó tồn tại các số nguyên x, y sao cho<br/>
<Center> <math>m*x+a*y=1</math> </Center>
Đẳ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===
<syntaxhighlight lang="pascal">
//a, m > 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;
</syntaxhighlight>

Giải thuật sau chỉ thực hiện với các số nguyên m>a>0, biểu diễn bằng giã mã:
 
  *'Procedure Euclid_Extended (a,m)
 *int*,  y0:=0,y1:=1;
 
 **While** a>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>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 -37. Lấy số đối của 37 theo mođun 101 được 64. Vậy 30^{-1}\,mod\,101=64.

### Ứ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ã.

## Xem thêm
* Giải thuật Euclid

## Tham khảo

## Liên kết ngoài
* A php implementation of the Extended Euclidean Algorithm showing line-by-line working and outputs 
* A javascript implementation of the Extended Euclidean Algorithm shown above 
* How to use the algorithm by hand 
* Extended Euclidean Algorithm Applet 
* Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)
* Source of a C++ program which calculates the multiplicative inverse.