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
Trong đó  là các hệ số nguyên,  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à  là ước của . Khẳng định này dựa trên một mệnh đề sau:
Nếu  thì tồn tại các số nguyên  sao cho

Giải thuật

{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;
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ã:
 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, ycode
 End Sub

Số nghịch đảo trong vành 
  
    
      
        
          
            Z
          
          
            m
          
        
      
    
    {\displaystyle \mathbb {Z} _{m}}

Trong lý thuyết số, vành  được định nghĩa là vành thương của  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  chỉ với các đại diện của nó. Khi đó
Phép cộng và nhân trong  là phép toán thông thường được rút gọn theo modulo m:
Phần tử a của  được gọi là khả nghịch trong   hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong   sao cho a*a'=1 trong  hay . 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
Đẳ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 > 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 = 1function 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>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"

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