Thuật toán Euclid mở rộng sẽ tìm USCLN d của a và b, đồng thời tìm được cả hai số nguyên x, y trong phần 2.3

Thuật toán Euclid mở rộng có thể diễn đạt bằng đệ quy như sau:

procedure ee(a, b, var x, var y);

var

     x2,y2;

begin

     if (a<b) then

          ee(b, a, x, y)

     else if (b=0) then

     begin

          x:=1;

          y:=0;

     end else

     begin

          ee(b, a mod b, x2, y2);

          x:=y2;

          y:=x2-(a div b)*y2;

     end;

end;

Giải thích:

Từ 2.1, ta đã biết (a, b) = (b, r) = d

ee(a, b, var x, var y) trả về giá trị x, y sao cho ax + by = d

Dòng lệnh màu đỏ chạy thủ tục đệ quy: tìm x₂, y₂ sao cho:

bx₂ + ry₂ = d

Mặt khác:

r = a – bq

Với

r=a mod b

q=a div b

Do đó

bx₂ + (a-bq)y₂ = d

ay₂ + b(x₂ – qy₂) = d

Vậy

x = y₂

y = x₂ – qy₂

Cấu trúc đệ quy của thuật toán Euclid mở rộng cũng tương tự như thuật toán Euclid.

2.5. Một số tính chất

Giả sử

a = p₁^a1p₂^a2...p_k^ak

b = p₁^b1p₂^b2...p_k^bk

Định nghĩa:

USCLN: (a, b) = p₁^{min(a1, b1)}p₂^{min(a2, b2)}...p_k^{min(ak, bk)}

BSCNN: [a, b] = p₁^{max(a1, b1)}p₂^{max(a2, b2)}...p_k^{max(ak, bk)}

Tính chất:

• (a, b) x [a, b] = ab
•  (a, b, c) = ((a, b), c) = (a, (b, c))
• [a, b, c] = [[a, b], c] = [a, [b, c]]

Chú ý:

• Không có đẳng thức (a, b, c) [a, b, c]  = abc

2.6. Bài tập

Cho dãy số nguyên dương n phần tử a₁, a₂, ..., a_n.

Yêu cầu:

Tìm dãy con liên tiếp dài nhất có USCLN > 1