THUẬT TOÁN ƠCLIT TÌM ƯCLN, BCNN

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

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

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 Aristotle

Euclid

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

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ó

Chứng minh

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.

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.

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

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

ích cho HS nếu phải giải những bài toán liên quan ƯSC & BSC.

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