Áp dụng Thuật toán Euclid về UCLN & BCNN.doc

Áp dụng Thuật toán Euclid
tính nhanh ước chung lớn nhất &
Bội số chung nhỏ nhất


“Thuật toán Euclid” 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, sau đó được Euclid (ơ –clit) hệ thống và phát triển nên thuật toán mang tên ông. Về số học, “Thuật toán Euclid” là một thuật toán để xác định ước số chung lớn nhất (GCD – Greatest Common Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên). Khi có UCLN ta cũng tính nhanh được BSCNN. Thuật toán này không yêu cầu việc phân tích thành thừa số 2 số nguyên.

1/ Thuật toán Oclit – dùng để tìm USCLN của 2 số nguyên bất kỳ.

Để tìm USCLN của hai số nguyên a và b bất kỳ ta dùng cách chia liên tiếp hay còn gọi là “vòng lặp” như sau:

Bước 1: Lấy a chia cho b:
Nếu a chia hết cho b thì USCLN(a,b) = b.
Nếu a không chia hết cho b (dư r) thì làm tiếp bước 2.

Bước 2: Lấy b chia cho số dư r:
Nếu b chia hết cho r thì USCLN(a,b) = r
Nếu b chia cho r dư r1 (r1 # 0) thì làm tiếp bước 3.

Bước 3: Lấy r chia cho số dư r1:
Nếu r chia cho r1 dư 0 thì UCLN(a,b) = r1.
Nếu r chia cho r1 dư r2 (r2 # 0) thì làm tiếp bước 4.

Bước 4: Lấy r1 chia cho số dư r2:
Nếu r1 chia hết cho r2 thì USCLN(a,b) = r2.
Nếu r1 cho cho r2 dư r3 (r3 # 0) thì làm tiếp như trên đến khi số dư bằng 0.

Số dư cuối cùng khác 0 trong dãy chia liên tiếp như trên là USCLN(a,b).

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ả
Thật ậy: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91
Cuối cùng ƯSCLN(287,91) = 7

2/ 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” :
Biết rằng: hai số nguyên a, b có BCNN là [ a,b] và ƯCLN là (a,b) thì




Nghĩa là: Tích 2 số nguyên (a x b ( = UCLN (a,b) x BSCNN (a,b)

Ví dụ: có a = 12; b = 18 ( USCLN (12,18) = 6 thì:
BSCNN (12,18) = (18) : 6 = 36
Nếu làm theo cách phân tich thừa số nguyên tố thì phải tính:
12 = ; 18 = 2 ( BSCNN (12,18) = 22 x 32 = 36
Nhận xét: Với cặp số nguyên có nhiều chữ số thì việc phân tích ra thừa số nguyên tố mất nhiều thời gian; trong khi lấy tích số có thể bấm máy tính cầm tay khá nhanh và dễ hơn.


PHH sưu tầm & giới thiệu - 11 / 2014