Toán học

Bài toán ngược của Thuật toán Euclide

Chúng ta đều đã quen thuộc với thuật toán Euclide, tìm ước số chung lớn nhất giữa hai số a, b.

Ví dụ: UCLN(30,12) = 6.

Tuy nhiên, bài viết này sẽ cung cấp cho các bạn một vấn đề khác liên quan đến thuật toán Euclide đó là:

Liệu rằng “có biểu thức nào liên hệ giữa UCLN(a,b) với hai số a và b” hay không ?

Và chúng tôi tạm gọi vấn đề này là “Bài toán ngược của thuật toán Euclide”


Trước tiên, chúng ta khẳng định rằng :

“Nếu a, b là các số nguyên và (a,b) = d. Khi đó tồn tại hai số nguyên x và y sao cho d = ax + by”

(chi tiết về cách chứng minh định lý trên các bạn có thể tham khảo tại http://www.cut-the-knot.org/blue/Euclid.shtml )


Ví dụ: (22, 38) = 2 và khi đó: 2 = 22 · 7 + 38 · (-4).
Vì vậy, ước chung lớn nhất của hai số trên được biểu diễn là tổ hợp tuyến tính của hai số 22 và 38. Các hệ số7 và -4 là một đáp số. Tuy nhiên, làm cách nào chúng ta có thể tìm được 2 hệ số đó? Thuật toán sau đây giúp chúng ta trả lời câu hỏi trên.
Chúng ta sẽ bắt đầu từ thuật toán Euclide để tìm ước chung lớn nhất của 38 và 22.
(1) 38 = 22 · 1 + 16
(2) 22 = 16 · 1 + 6
(3) 16 = 6 · 2 + 4
(4) 6 = 4 · 1 + 2
(5) 4 = 2 · 2 + 0

Vì vậy, (22, 38) = 2.

Để biểu diễn 2 như một biểu thức tổ hợp tuyến tính giữa 22 và 38 ta sẽ sử dụng các bước truy ngược lại của thuật toán Euclide.

Bắt đầu từ biểu thức (4) 6 = 4 · 1 + 2 ta giải tìm số dư 2:
(1′) 2 = 6 – 4 · 1
Bây giờ, từ bểu thức (3) 16 = 6 · 2 + 4 ta giải tìm số dư 4:
(2′) 4 = 16 – 6 · 2
Thay thế 4 ở biểu thức (2′) vào biểu thức (1′) ta có:
2 = 6 – (16 – 6 · 2) · 1
2 = 6 – (16 · 1 – 6 · 2)
(3′) 2 = 6 · 3 – 16 · 1

Kế tiếp, từ biểu thức (2) 22 = 16 · 1 + 6 ta giải tìm số dư 6:
(4′) 6 = 22 – 16 · 1
Thế 6 ở biểu thức (4′) vào biểu thức (3′) ta có:
2 = (22 – 16 · 1) · 3 – 16 · 1
2 = (22 · 3 – 16 · 3) – 16 · 1
(5′) 2 = 22 · 3 -16 · 4

Chúng ta cứ tiếp tục quá trình ngược trên cho đến biểu thức ban đầu.
….
Từ biểu thức (1) 38 = 22 · 1 + 16, ta giải tìm số dư 16:
(6′) 16 = 38 – 22 · 1.
Khi đó, thế (6′) vào (5′) ta sẽ có:
2 = 22 · 3 – (38 – 22 · 1) · 4
2 = 22 · 3 – (38 · 4 – 22 · 4)
2 = 22 · 7 – 38 · 4
2 = 22 · 7 + 38 · (-4)

Bằng cách trên, ta luôn tìm được các số nguyên x và y sao cho UCLN(a,b) = ax + by. Và bằng cách này, bạn có thể đố mọi người biểu diễn một số thông qua 2 số cho trước.
Ví dụ: biểu diễn 3 thông qua tổ hợp tuyến tính của hai số 60 và 39.

Advertisements

About 2Bo02B

Nguyễn Vũ Thụ Nhân (Mr) Lecturer Physics Department. HCMC University of Pedagogy

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Translators & RSS

English French RussiaMaths 4 Physics (M4Ps)


Bạn hãy nhập địa chỉ email của mình để đăng ký theo dõi tin tức từ blog này và nhận những bài viết mới nhất qua địa chỉ email.

Join 2 742 other followers

Đôi lời

Bạn có thể theo dõi các lời bình liên quan đến lời bình của mình qua email bằng cách chọn dòng thông báo Báo cho bạn khi có người bình luận tiếp theo đề tài này bằng điện thư mỗi khi viết 1 lời bình.


Rất mong các bạn viết lời nhắn bằng tiếng việt có dấu nhé.

Để viết tiếng việt có dấu bạn dùng font chữ Unicode và bảng mã là Unicode UTF-8.


Để biết cách gõ công thức Toán học trong các lời nhắn ở trang web này, mời bạn đọc bài hướng dẫn tại đây hoặc bạn có thể xem bài hướng dẫn dùng MathType tại đây và bài tạo công thức trực tuyến tại đây


Get Well

%d bloggers like this: