Thuật Toán Euclid

Trang chủ » Thuật Toán ơ Cơ Lít » Thuật Toán Euclid

Có thể bạn quan tâm

Trang

  • Trang nhà
  • Kỹ năng mềm
  • Giới thiệu

Thuật toán Euclid

Kỳ trước chúng ta đã học về bổ đề Bezout. Hôm nay chúng ta sẽ học về thuật toán Euclid. Thuật toán này dùng để xác định các hệ số trong đẳng thức Bezout. Trước hết chúng ta phát biểu bổ đề Bezout.
Bổ đề Bezout. Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a ~x + b ~y.$$
Thuật toán Euclid mục đích đi tìm ước số chung lớn nhất $d$ của hai số $a$ và $b$, và xác định hai giá trị của $x$ và $y$ trong đẳng thức Bezout $$d = a ~x + b ~y.$$ Ý tưởng của thuật toán Euclid rất đơn giản và tự nhiên. Đầu tiên chúng ta nói về việc đi tìm ước số chung lớn nhất của cặp số $a$, $b$. Giả sử như $a = 45$, $b = 155$. Làm sao chúng ta tìm được ước số chung lớn nhất của cặp số này? Có một cách làm rất tự nhiên, đó là làm nhỏ các con số lại. Chúng ta biết rằng ước số chung lớn nhất của cặp số $(a,b)$ cũng chính là ước số chung lớn nhất của cặp số $(a, b-a)$. Trong ví dụ này, chúng ta có cặp số $a = 45$, $b = 155$. Chúng ta có thể làm nhỏ con số $b$ lại bằng con số $$b-a = 110.$$ Như vậy ước số chung lớn nhất của cặp số $(45, 155)$ chính là ước số chung lớn nhất của cặp số $(45, 110)$. Con số $b-a=110$ vẫn có thể làm nhỏ lại bằng cách lấy $$(b - a) - a = 110-45 = 65,$$ và $$b - 3a = 65-45 = 20.$$ Cuối cùng, chúng ta có cặp số $(45, 20)$. Tóm lại, nếu chúng ta lấy $b$ chia cho $a$ có số dư là $r$ như sau $$b = aq + r,$$ thì ước số chung lớn nhất của cặp số $(a,b)$ chính là bằng ước số chung lớn nhất của cặp số nhỏ hơn $(a,r)$. Đây chính là mấu chốt của thuật toán Euclid. Chúng ta bắt đầu lại từ đầu nhé. Chúng ta có $$155 = 45 \times 3 + 20,$$ do đó $(45, 155) = (45, 20)$. Làm tiếp $$45 = 20 \times 2 + 5,$$ do đó $(45, 20) = (20,5)$. Tiếp tục, $$20 = 5 \times 4 + 0,$$ do đó $(20,5) = 5$. Như vậy chúng ta đã tìm ra ước số chung lớn nhất, đó chính là $5$. Bây giờ chúng ta xem cách tìm số $x$, $y$ trong đẳng thức Bezout $$d = a ~x + b ~y.$$ Bước 1. Chúng ta làm như trên để tìm ra ước số chung lớn nhất là $d$. $$155 = 45 \times 3 + 20,$$ $$45 = 20 \times 2 + 5,$$ $$20 = 5 \times 4 + 0,$$ do đó $d=(45,155) = 5$ Bước 2. Bắt đầu từ dưới lên, chúng ta lần lượt viết các phương trình $b = aq + r$ về dạng $r = b - aq$ (phương trình cuối cùng có số dư bằng $0$ nên không cần phải viết) $$d = 5 = 45 - 20 \times 2,$$ $$20 = 155 - 45 \times 3,$$ Bước 3. Chúng ta biến đổi $d$ như sau $$d = 5 = 45 - 20 \times 2$$ $$= 45 - (155 - 45 \times 3) \times 2$$ $$= 45 \times 7 - 155 \times 2,$$ Tóm lại chúng ta đã viết được $d$ về dạng $ax + by$. Chúng ta cùng làm một ví dụ khác nhé. Ví dụ $a = 1000$, $b = 2013$. Bước 1. Dùng phép chia $b = aq + r$ để làm nhỏ bộ số $(b,a) \to (a,r)$ $${\bf 2013} = {\bf 1000} \times 2 + {\bf 13},$$ $${\bf 1000} = {\bf 13} \times 76 + {\bf 12},$$ $${\bf 13} = {\bf 12} \times 1 + {\bf 1},$$ $${\bf 12} = {\bf 1} \times 12 + 0,$$ do đó $d=(1000,2013) = 1$ Bước 2. Bắt đầu từ dưới lên, viết các phương trình về dạng $r = b - aq$ (phương trình cuối cùng không cần viết) $$d = {\bf 1} = {\bf 13} - {\bf 12} \times 1,$$ $${\bf 12} = {\bf 1000} - {\bf 13} \times 76,$$ $${\bf 13} = {\bf 2013} - {\bf 1000} \times 2,$$ Bước 3. Chúng ta biến đổi $d$ như sau và cuối cùng chúng ta có $$d = {\bf 1} = {\bf 2013} \times 77 - {\bf 1000} \times 155$$ Bổ đề Bezout và thuật toán Euclid có nhiều ứng dụng trong việc giải các phương trình nghiệm nguyên. Chúng ta sẽ xem xét kỹ về đề tài này trong các kỳ sau. Tạm thời, chúng ta xem xét bài toán sau đây. Bài toán. Tìm tất cả các số tự nhiên $n$ sao cho số $2013 n$ có ba chữ số tận cùng là $999$. Phân tích. Ở bài toán này chúng ta cần giải phương trình sau đây $$2013 n = 999 = -1 \pmod{1000}.$$ Nếu chúng ta tạm thời bỏ qua modulo mà chỉ quan tâm đến phương trình số thực dạng $$ax = b$$ thì phương trình này có nghiệm là $$x = \frac{b}{a},$$ đấy là bởi vì chúng ta đã nhân hai vế của phương trình với số nghịch đảo của $a$. Cũng tương tự như vậy, nếu chúng ta có phương trình modulo $$ax = b \pmod{p},$$ chúng ta có thể giải được nó bằng cách nhân cả hai vế với nghịch đảo của $a$. Nghịch đảo của $a$ trong modulo $p$ chính là số $c$ sao cho $$ac = 1 \pmod{p}.$$ Bằng cách nhân cả hai vế phương trình với $c$ chúng ta có $$ac x = bc \pmod{p}.$$ Vì $ac = 1 \pmod{p}$ cho nên $$x = bc \pmod{p}.$$ Bây giờ quay lại bài toán ban đầu, chúng ta phải giải phương trình $$2013 n = -1 \pmod{1000}.$$ Chúng ta cần tìm nghịch đảo của $2013$ trong modulo $1000$. Chúng ta dùng đẳng thức Bezout ở trên, đó là $${\bf 2013} \times 77 - {\bf 1000} \times 155 = 1.$$ Lấy modulo $1000$, chúng ta có $$2013 \times 77 = 1 \pmod{1000}.$$ Vậy nghịch đảo của $2013$ trong modulo $1000$ chính là $77$. Lời giải. Số $2013 n$ có ba chữ số tận cùng là $999$ khi và chỉ khi $$2013 n = 999 = -1 \pmod{1000}.$$ Từ đẳng thức Bezout $${\bf 2013} \times 77 - {\bf 1000} \times 155 = 1,$$ chúng ta có $$2013 \times 77 = 1 \pmod{1000}.$$ Nhân cả hai vế phương trình sau với $77$ $$2013 n = -1 \pmod{1000},$$ chúng ta có $$2013 \times 77 n = -77 \pmod{1000}.$$ Vì $2013 \times 77 = 1 \pmod{1000}$, chúng ta có $$n = -77 = 923 \pmod{1000}.$$ Tóm lại số $n$ cần tìm là $n = 923 + 1000 k$. Kiểm chứng, với $k=0$, chúng ta có $n=923$, và $$2013 \times 923 = 1857999.$$ Chúng ta tạm dừng chủ đề về bổ đề Bezout và thuật toán Euclid ở đây. Sau này khi có dịp chúng ta sẽ xem xét kỹ thêm về ứng dụng của bổ đề Bezout và thuật toán Euclid. Hẹn gặp lại các bạn vào kỳ sau. Bài tập về nhà. 1. Dùng thuật toán Euclid để thiết lập đẳng thức Bezout cho hai số $2012$ và $999$. 2. Giải phương trình nghiệm nguyên sau đây $$2012 a + 999 b = 5.$$ 3. Giải phương trình nghiệm nguyên sau đây $$2012 x = 999 y + 99 z + 9.$$ Labels: algebra, Bézout, đại số, Euclidean algorithm, gcd, modulo, number theory, phương trình nghiệm nguyên, số học, ước số Bài đăng Mới hơn Bài đăng Cũ hơn Trang chủ

Ủng hộ Vườn Toán trên facebook

Facebook

Lưu trữ Blog

  • ▼  2012 (36)
    • ▼  tháng 11 (7)
      • Tổng luỹ thừa và định lý Wolstenholme
      • Tổng luỹ thừa
      • Thuật toán Euclid
      • Bổ đề Bezout
      • Chứng minh lại định lý Wilson
      • Modulo cho số hữu tỷ II
      • Modulo cho số hữu tỷ

English Version

English Version

Bài toán kết nối facebook

Phép nhân thời đồ đá

Mắt Biếc Hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci và một bài toán xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số chính phương kỳ diệu của Vianney!

Câu đố mẹo về đo lường

Công thức lượng giác Gauss cho 17-giác đều

Chào năm mới 2014

Chào năm mới 2015

Chào năm mới 2016

Không gian 4 chiều là gì?

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... có bằng 1 không? (2015)

Hình tam giác

Bàn cờ vua và kim tự tháp

Dãy số

Dãy số - Phần 1

Dãy số - Phần 2

Dãy số - Phần 3

Dãy số - Phần 4

Dãy số - Phần 5

Dãy số - Phần 6

Dãy số - Phần 7

Dãy số - Phần 8

Dãy số - Phần 9

Đại số

Tam giác Pascal

Quy nạp

Quy nạp II

Quy nạp III

Nhị thức Newton

1 = 2012 = 2013

Đa thức nội suy Newton

Đa thức nội suy Lagrange

Chứng minh Định lý Wilson bằng công thức nội suy

Tổng luỹ thừa

Số phức

Số phức

Công thức Moivre

Lượng giác

Công thức lượng giác cho góc bội

Công thức lượng giác Gauss cho 17-giác đều

Ngày số Pi (2016)

Radian là gì?

Số học

modulo - Phần 1

modulo - Phần 2

modulo - Phần 3

modulo - Phần 4

modulo - Phần 5

modulo - Phần 6

Số nguyên tố

Định lý Euclid về số nguyên tố

Một vài bài toán về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo cho số hữu tỷ II

Chứng minh lại định lý Wilson

Bổ đề Bezout

Thuật toán Euclid

Tổng luỹ thừa

Tổng luỹ thừa và định lý Wolstenholme

Câu đố mẹo về đo lường

Dựng đa giác đều 15 cạnh

Bò đi con bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số kỳ diệu của Euler

Tổ hợp

Bài toán kết nối facebook

Dãy số Fibonacci và một bài toán xếp hình

Hằng đẳng thức về dãy số Fibonacci

Dãy số Fibonacci và tam giác Pascal

Hình học

Định lý Pitago

Định lý đường cao tam giác vuông

Định lý Morley

Phương tích

Trục đẳng phương và tâm đẳng phương

Định lý Ceva và Định lý Menelaus

Lục giác kỳ diệu

Định lý Pascal

Định lý Pappus

Cánh bướm Pascal

Bài toán con bướm

Định lý Ngôi Sao Do Thái

Hãy xem xét trường hợp đặc biệt

Bài toán về tìm khoảng cách ngắn nhất và một tính chất của hình elíp

Điểm Fermat của hình tam giác

Điểm Fermat của hình tam giác II

Dựng hình

Dựng hình bằng thước và compa

Bài toán chia hình tứ giác

Dựng hình ngũ giác đều

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Định lý đường cao tam giác vuông

Thuật toán dựng hình

Công thức lượng giác Gauss cho 17-giác đều

Dựng hình chỉ bằng compa

Dùng compa chia đều đoạn thẳng

Giải tích

Ngày số Pi 2015

Chuỗi Taylor

Tổng nghịch đảo bình phương

Giúp bé thông minh

Xì-tin năng động

BBC - Học tiếng Anh Du học Hoa kỳ Học Bổng Hoa Kỳ VOA - Học tiếng Anh

Tạp chí toán học

Kỹ năng mềm

Tạo lập tài khoản google

Cách tạo blog toán học

Học toán trên Wolfram

Dịch tài liệu toán học

Viết văn bản toán học PDF trực tuyến bằng LaTeX

Chia xẻ tài liệu toán học trên Google Drive

Từ khóa » Thuật Toán ơ Cơ Lít