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 $d=UCLN(a,b)$ thì tồn tại các số nguyên $x,y$ sao cho $ax+by=d$

Cơ sở lý thuyết của giải thuật[sửa | sửa mã nguồn]

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>b>0. Đặt $r_{o}=a,r_{1}=b$ , chia $r_{0}$ cho $r_{1}$ được số dư $r_{2}$ và thương số nguyên $q_{1}$ . Nếu $r_{2}=0$ thì dừng, nếu $r_{2}$ khác không, chia $r_{1}$ cho $r_{2}$ được số dư $r_{3}$ ,...Vì dãy các $r_{i}$ là giảm thực sự nên sau hữu hạn bước ta được số dư $r_{m+2}=0$ .

r_{o}=q_{1}*r_{1}+r_{2},0<r_{2}<r_{1}

;

r_{1}=q_{2}*r_{2}+r_{3},0<r_{3}<r_{2}

;

....;

r_{m-1}=q_{m}*r_{m}+r_{m+1},0<r_{m+1}<r_{m}

r_{m}=q_{m+1}*r_{m+1}

trong đó số dư cuối cùng khác 0 là $r_{m+1}=d$ . Bài toán đặt ra là tìm x, y sao cho

a*x+b*y=r_{m+1}(=d)

Để 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

x_{i}

và

y_{i}

sao cho:

a*x_{i}+b*y_{i}=r_{i}

với

i=0,1,...

.

Ta có

a*1+b*0=a=r_{o}

và

a*0+b*1=b=r_{1}

, nghĩa là

x_{o}=1,x_{1}=0

và

y_{o}=0,y_{1}=1

. (1)

Tổng quát, giả sử có

a*x_{i}+b*y_{i}=r_{i}

với

i=0,1,...

.

a*x_{i+1}+b*y_{i+1}=r_{i+1}

với

i=0,1,...

.

Khi đó từ

r_{i}=q_{i+1}*r_{i+1}+r_{i+2}

suy ra

r_{i}-q_{i+1}*r_{i+1}=r_{i+2}

(a*x_{i}+b*y_{i})-q_{i+1}*(a*x_{i+1}+b*y_{i+1})=r_{i+2}

a*(x_{i}-q_{i+1}*x_{i+1})+b*(y_{i}-q_{i+1}*y_{i+1})=r_{i+2}

từ đó, có thể chọn

x_{i+2}=x_{i}-q_{i+1}*x_{i+1}

(2)

y_{i+2}=y_{i}-q_{i+1}*y_{i+1}

(3)

Khi $i=m-1$ ta có được $x_{m+1}$ và $y_{m+1}$ . 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[sửa | sửa mã nguồn]

{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, y
code
 End Sub

Ví dụ[sửa | sửa mã nguồn]

Với a=29, b=8, giải thuật trải qua các bước như sau:

Bước $i$	$r_{i}$	$r_{i+1}$	$r_{i+2}$	$q_{i+1}$	$x_{i}$	$x_{i+1}$	$x_{i+2}$	$y_{i}$	$y_{i+1}$	$y_{i+2}$
0	29	8	5	3	1	0	1	0	1	-3
1	8	5	3	1	0	1	-1	1	-3	4
2	5	3	2	1	1	-1	2	-3	4	-7
3	3	2	1	1	-1	2	-3	4	-7	11
4	2	1	0	2

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

Áp dụng giải thuật Euclid mở rộng tìm số nghịch đảo trong vành $\mathbb {Z} _{m}$ [sửa | sửa mã nguồn]

Số nghịch đảo trong vành $\mathbb {Z} _{m}$ [sửa | sửa mã nguồn]

Trong lý thuyết số, vành $\mathbb {Z} _{m}$ được định nghĩa là vành thương của $\mathbb {Z}$ 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 $\mathbb {Z} _{m}$ chỉ với các đại diện của nó. Khi đó

$\mathbb {Z} _{m}=\left\{0,1,...,m-1\right\}$

Phép cộng và nhân trong $\mathbb {Z} m$ là phép toán thông thường được rút gọn theo modulo m:

$a+b=(a+b)\quad mod\quad m$
$a*b=(a*b)\quad mod\quad m$

Phần tử a của $\mathbb {Z} _{m}$ được gọi là khả nghịch trong $\mathbb {Z} _{m}$ hay khả nghịch theo modulo m nếu tồn tại phần tử a' trong $\mathbb {Z} _{m}$ sao cho a*a'=1 trong $\mathbb {Z} _{m}$ hay $a*a'\equiv 1{\pmod {m}}$ . 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

m*x+a*y=1

Đẳ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[sửa | sửa mã nguồn]

//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;

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"