Giải Thuật Euclid Mở Rộng – Wiki Tiếng Việt 2022 - .vn

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 {\displaystyle r_{o}=a,r_{1}=b} , chia r 0 {\displaystyle r_{0}} cho r 1 {\displaystyle r_{1}} được số dư r 2 {\displaystyle r_{2}} và thương số nguyên q 1 {\displaystyle q_{1}} . Nếu r 2 = 0 {\displaystyle r_{2}=0} thì dừng,nếu r 2 {\displaystyle r_{2}} khác không, chia r 1 {\displaystyle r_{1}} cho r 2 {\displaystyle r_{2}} được số dư r 3 {\displaystyle r_{3}} ,...Vì dãy các r i {\displaystyle 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 {\displaystyle r_{m+2}=0} .

r o = q 1 ∗ r 1 + r 2 , 0 < r 2 < r 1 {\displaystyle 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 {\displaystyle 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 {\displaystyle r_{m-1}=q_{m}*r_{m}+r_{m+1},0<r_{m+1}<r_{m}} r m = q m + 1 ∗ r m + 1 {\displaystyle r_{m}=q_{m+1}*r_{m+1}}

trong đó số dư cuối cùng khác 0 là r m + 1 = d {\displaystyle 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 ) {\displaystyle 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 {\displaystyle x_{i}} và y i {\displaystyle y_{i}} sao cho: a ∗ x i + b ∗ y i = r i {\displaystyle a*x_{i}+b*y_{i}=r_{i}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} .

Ta có

a ∗ 1 + b ∗ 0 = a = r o {\displaystyle a*1+b*0=a=r_{o}} và a ∗ 0 + b ∗ 1 = b = r 1 {\displaystyle a*0+b*1=b=r_{1}} , nghĩa là x o = 1 , x 1 = 0 {\displaystyle x_{o}=1,x_{1}=0} và y o = 0 , y 1 = 1 {\displaystyle y_{o}=0,y_{1}=1} . (1)

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

a ∗ x i + b ∗ y i = r i {\displaystyle a*x_{i}+b*y_{i}=r_{i}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} . a ∗ x i + 1 + b ∗ y i + 1 = r i + 1 {\displaystyle a*x_{i+1}+b*y_{i+1}=r_{i+1}} với i = 0 , 1 , . . . {\displaystyle i=0,1,...} .

Khi đó từ

r i = q i + 1 ∗ r i + 1 + r i + 2 {\displaystyle r_{i}=q_{i+1}*r_{i+1}+r_{i+2}}

suy ra

r i − q i + 1 ∗ r i + 1 = r i + 2 {\displaystyle 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 {\displaystyle (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 {\displaystyle 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 {\displaystyle x_{i+2}=x_{i}-q_{i+1}*x_{i+1}} (2) y i + 2 = y i − q i + 1 ∗ y i + 1 {\displaystyle y_{i+2}=y_{i}-q_{i+1}*y_{i+1}} (3)

Khi i = m − 1 {\displaystyle i=m-1} ta có được x m + 1 {\displaystyle x_{m+1}} và y m + 1 {\displaystyle 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

{Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)}functiongcd(a,b);beginwhileb≠0dobeginr:=amodb;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.}functionExtended_gcd(a,b);begin(xa,ya):=(1,0);(xb,yb):=(0,1);whileb≠0dobeginq:=adivb;r:=amodb;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ã:

SubEuclid_Extended(a,b)Dimx0,x,y,y1AsSinglex0=1:x1=0:y0=0:y1=1Whileb>0r=amodbifr=0thenExitWhileq=a/bx=x0-x1*qy=y0-y1*qa=bb=rx0=x1x1=xy0=y1y1=yWendMe.Printd:=b,x,ycodeEndSub

Ví dụ

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

Bước i {\displaystyle i}	r i {\displaystyle r_{i}}	r i + 1 {\displaystyle r_{i+1}}	r i + 2 {\displaystyle r_{i+2}}	q i + 1 {\displaystyle q_{i+1}}	x i {\displaystyle x_{i}}	x i + 1 {\displaystyle x_{i+1}}	x i + 2 {\displaystyle x_{i+2}}	y i {\displaystyle y_{i}}	y i + 1 {\displaystyle y_{i+1}}	y i + 2 {\displaystyle 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 = U C L N ( 29 , 8 ) = 1 {\displaystyle d=UCLN(29,8)=1} và x = − 3 {\displaystyle x=-3} , y = 11 {\displaystyle y=11} .Dễ dàng kiểm tra hệ thức 29 ∗ ( − 3 ) + 8 ∗ 11 = 1 {\displaystyle 29*(-3)+8*11=1}