Thuật toán Euclide về USCLN & BSCNN

Thuật toán
Euclide
Giới thiệu
Điều quan trọng chủ yếu là nó không yêu cầu việc phân tích thành các thừa số nguyên tố.
Hơn thế, nó còn mang ý nghĩa lớn vì đây là một trong những thuật toán cổ nhất được biết đến từ thời Hy Lạp cổ đại
Chương trình toán THCS có phần tính ƯSCLN & BSCNN nhưng HS ít biết đến thuật toán này.
Trong lý thuyết số học , thuật toán Euclid là một thuật toán cổ để xác định ước số chung lớn nhất (ƯSCLNN-tắt tiếng Việt; hoặc tiếng Anh GCD – Greatest Common Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên).
Lịch sử của thuật toán
Thuật toán Euclid là một thuật toán cổ xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn.
Tuy thuật toán này được biết đến sóm hơn bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên), nhưng Euclide vẫn là người có công lớn nhất nên thuật toán được mang tên ông.
Aristotle
Euclid
Tính ước số chung lớn nhất
Ví dụ Tính ước số chung lớn nhất của 91 và 287.
Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)
Ta thấy bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287.
Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:
91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)
ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
Cuối cùng ƯSCLN(287,91) = 7
Tính BSCNN nhanh nhất
Để việc giải toán về BCNN & UCLN được nhanh, Nếu biết áp dụng “Thuật toán Euclid” :
hai số nguyên a, b có BCNN là [ a,b] và ƯCLN là (a,b) thì





(Công thức trên giúp tính nhanh , không phải làm theo cách phân tích ra thừa số nguyên tố)
Bổ đề Euclide
Giả sử
a = bq + r, với a, b, q, r là các số nguyên,
ta có



Từ bổ đề trên, người ta đã chứng minh thuật toán

Chứng minh
Giả thiết a và b là các số tự nhiên mà UCLN phải xác định.
Nếu b > 0, và phần dư của phép chia a cho b là r.
Thì a = qb + r với q là thương của phép chia.
Bất kì phép chia thông thường nào của a và b cũng cho một số dư r. Để thấy sự đúng đắn đó, ta coi r có thể được viết là r = a – qb. Bây giờ nếu có một ước chung d của a và b,
như vậy a = sd và b = td, khi đó r = (s-qt)d,
ta có thể thấy rằng r chia hết cho d.
Những phân tích trên là đúng cho bất kì số chia d nào, vì thế, UCLN của a và b cũng là UCLN của b và r. Do đó nếu ta tiếp tục tìm UCLN với các số b và r. Khi giá trị tuyệt đối của r nhỏ hơn b, ta sẽ tiến tới rn+1 = 0 sau nhiều bước.
Minh họa về thuật toán lặp:
Giả sử tính toán UCLN của 1071 và 1029 là 21;
Các bước lặp như biểu bên
Lưu ý :
a, b trong mỗi lần gọi. Nếu b > a, thì ta chỉ cần hoán đổi 2 giá trị cho nhau, sau đó các bước hoàn toàn tương tự.
Phạm vi của thuật toán Euclid

Ví dụ, Tính UCLN của
a = x4 + 8x3 + 12x2 + 17x + 6 = (x2 + 7x + 3)(x2 + x + 2)
b =x4 − 4x3 + 4x2 − 3x + 14 = (x2 − 5x + 7)(x2 + x + 2) và
Thuật toán Euclid có thể áp dụng cho các nhóm số khác, không chỉ cho số tự nhiên. Trường hợp cá biệt là các số nguyên Gaussian và các nhóm đa thức.
Xét nhóm đa thức với hệ số hữu tỷ. Nhóm này, phép chia với phần dư được sử dụng phép chia đa thức.
Thay lời kết
Thuật toán Euclitd không phải mới ( có từ 300 năm TCN ), nhưng sẽ có ích cho HS nếu phải giải những bài toán liên quan ƯSC & BSC.
Với HS muốn tìm hiểu sâu hơn (Đưa vào ngôn ngữ lập trình, sử dung đệ quy…) xin xem thêm phần “Giải thuật Euclitd mở rộng ”
GT & biên soạn Phạm Huy Hoạt 1-3-2012