Thuật Toán Ơ Cơ Lít

     
Kỳ trước chúng ta đã học tập về bổ đề Bezout. Lúc này chúng ta sẽ học về thuật toán Euclid. Thuật toán này dùng làm xác định những hệ số vào đẳng thức Bezout.

Bạn đang xem: Thuật toán ơ cơ lít


Bổ đề Bezout.Nếu $d$ là mong số chung lớn số 1 của nhì số nguyên $a$ cùng $b$ thì sẽ tồn tại nhị số nguyên $x$ với $y$ làm thế nào để cho $$d = a ~x + b ~y.$$Thuật toán Euclid mục đích đi tìm kiếm ước số chung lớn nhất $d$ của nhị số $a$ cùng $b$, và khẳng định hai quý giá 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à dễ dàng và trường đoản cú nhiên.Đầu tiên chúng ta nói về việc đi tìm ước số chung lớn số 1 của cặp số $a$, $b$.Giả sử như $a = 45$, $b = 155$. Làm cho sao bọn họ tìm được mong số chung lớn số 1 của cặp số này?Có một phương pháp làm khôn cùng tự nhiên, chính là làm bé dại các con số lại. Chúng ta biết rằng mong số chung lớn số 1 của cặp số $(a,b)$ cũng đó là ước số chung lớn nhất của cặp số $(a, b-a)$.Trong lấy một ví dụ này, họ có cặp số $a = 45$, $b = 155$. Bạn cũng có thể làm nhỏ con số $b$ lại bằng số lượng $$b-a = 110.$$ do vậy ước số chung lớn số 1 của cặp số $(45, 155)$ chính là ước số chung lớn số 1 của cặp số $(45, 110)$.Con số $b-a=110$ vẫn có thể làm nhỏ tuổi lại bằng cách lấy $$(b - a) - a = 110-45 = 65,$$ cùng $$b - 3a = 65-45 = 20.$$Cuối cùng, họ có cặp số $(45, 20)$. Bắt lại, nếu chúng ta lấy $b$ phân chia cho $a$ có số dư là $r$ như sau $$b = aq + r,$$ thì cầu số chung lớn nhất của cặp số $(a,b)$ đó là bằng ước số chung lớn nhất của cặp số nhỏ dại hơn $(a,r)$.Đây chính là mấu chốt của thuật toán Euclid.Chúng ta bước đầu lại từ đầu nhé. Bọn họ có $$155 = 45 imes 3 + 20,$$ do đó $(45, 155) = (45, 20)$. Giữ vững $$45 = trăng tròn imes 2 + 5,$$ cho nên $(45, 20) = (20,5)$. Tiếp tục, $$20 = 5 imes 4 + 0,$$ cho nên vì vậy $(20,5) = 5$. Như vậy chúng ta đã tra cứu ra mong số chung phệ nhất, đó chính là $5$.Bây giờ họ xem biện pháp tìm số $x$, $y$ vào đẳng thức Bezout $$d = a ~x + b ~y.$$Bước 1. chúng ta làm như trên để tìm ra cầu số chung lớn nhất là $d$.$$155 = 45 imes 3 + 20,$$ $$45 = 20 imes 2 + 5,$$ $$20 = 5 imes 4 + 0,$$ vì vậy $d=(45,155) = 5$
Bước 2.
Bắt đầu từ bên dưới lên, bọn họ 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 sau cuối có số dư bằng $0$ nên không cần phải viết)$$d = 5 = 45 - 20 imes 2,$$ $$20 = 155 - 45 imes 3,$$
$$d = 5 = 45 - 20 imes 2$$ $$= 45 - (155 - 45 imes 3) imes 2$$ $$= 45 imes 7 - 155 imes 2,$$Tóm lại họ đã viết được $d$ về dạng $ax + by$.Chúng ta cùng làm một ví dụ không giống nhé. Ví dụ như $a = 1000$, $b = 2013$.Bước 1.

Xem thêm: Cảm Nhận Về Bài Văn Tế Nghĩa Sĩ Cần Giuộc, Cảm Nhận Văn Tế Nghĩa Sĩ Cần Giuộc

Dùng phép chia $b = aq + r$ để làm bé dại bộ số $(b,a) o (a,r)$$$f 2013 = f 1000 imes 2 + f 13,$$ $$f 1000 = f 13 imes 76 + f 12,$$ $$f 13 = f 12 imes 1 + f 1,$$ $$f 12 = f 1 imes 12 + 0,$$ vì vậy $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 ở đầu cuối không bắt buộc viết)$$d = f 1 = f 13 - f 12 imes 1,$$ $$f 12 = f 1000 - f 13 imes 76,$$ $$f 13 = f 2013 - f 1000 imes 2,$$
*

Bổ đề Bezout và thuật toán Euclid có rất nhiều ứng dụng trong việc giải các phương trình nghiệm nguyên. Họ sẽ chu đáo kỹ về đề bài này trong số kỳ sau. Tạm thời, chúng ta xem xét việc sau đây.Bài toán.
Tìm tất cả các số tự nhiên và thoải mái $n$ làm thế nào cho số $2013 n$ có bố chữ số tận cùng là $999$.Phân tích.

Xem thêm: Bài Văn Nghị Luận Về Sách - Nghị Luận Về Vai Trò Của Sách (20 Mẫu)

Ở việc này chúng ta cần giải phương trình dưới đây $$2013 n = 999 = -1 pmod1000.$$Nếu bọn họ tạm thời bỏ qua mất modulo nhưng chỉ cân nhắc phương trình số thực dạng $$ax = b$$ thì phương trình này còn có nghiệm là $$x = fracba,$$ đấy là chính vì chúng ta đang nhân nhị vế của phương trình cùng với số nghịch hòn đảo của $a$.Cũng tương tự như như vậy, nếu bọn họ có phương trình modulo $$ax = b pmodp,$$ bạn cũng có thể giải được nó bằng phương pháp nhân cả nhị vế cùng với nghịch hòn đảo của $a$.Nghịch đảo của $a$ trong modulo $p$ chính là số $c$ làm sao để cho $$ac = 1 pmodp.$$Bằng biện pháp nhân cả hai vế phương trình cùng với $c$ chúng ta có $$ac x = bc pmodp.$$ vày $ac = 1 pmodp$ cho nên vì vậy $$x = bc pmodp.$$Bây giờ trở về bài toán ban đầu, bọn họ phải giải phương trình $$2013 n = -1 pmod1000.$$Chúng ta đề xuất tìm nghịch đảo của $2013$ trong modulo $1000$. Chúng ta dùng đẳng thức Bezout làm việc trên, đó là $$f 2013 imes 77 - f 1000 imes 155 = 1.$$Lấy modulo $1000$, họ có $$2013 imes 77 = 1 pmod1000.$$Vậy nghịch hòn đảo của $2013$ trong modulo $1000$ đó là $77$.Lời giải. Số $2013 n$ có ba chữ số tận cùng là $999$ khi còn chỉ khi $$2013 n = 999 = -1 pmod1000.$$Từ đẳng thức Bezout $$f 2013 imes 77 - f 1000 imes 155 = 1,$$ bọn họ có $$2013 imes 77 = 1 pmod1000.$$Nhân cả nhì vế phương trình sau cùng với $77$ $$2013 n = -1 pmod1000,$$ họ có $$2013 imes 77 n = -77 pmod1000.$$Vì $2013 imes 77 = 1 pmod1000$, bọn họ có $$n = -77 = 923 pmod1000.$$Tóm lại số $n$ cần tìm là $n = 923 + 1000 k$.Kiểm chứng, cùng với $k=0$, chúng ta có $n=923$, với $$2013 imes 923 = 1857999.$$Chúng ta tạm ngưng chủ đề về té đề Bezout với thuật toán Euclid sinh hoạt đây. Sau này khi có dịp chúng ta sẽ chăm chú kỹ thêm về áp dụng của vấp ngã đề Bezout cùng thuật toán Euclid.Hẹn chạm chán lại chúng ta 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 đến hai số $2012$ với $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 dưới đâ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ơnBài đăng Cũ hơnTrang chủ

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


*

Lưu trữ Blog


►  2017(1) ►  2016(7) ►  2015(12) ►  2014(12) ►  2013(26) ▼  2012(36) ▼  tháng 11(7) ►  2011(7)
*

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

Phép nhân thời đồ gia dụng đá

Mắt Biếc hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci cùng một vấn đề xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số thiết yếu phương vi diệu của Vianney!

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

Công thức lượng giác Gauss mang đến 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 nhiều giác phần nhiều 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... Có bởi 1 không? (2015)

Hình tam giác

Bàn cờ vua với kim trường đoản cú tháp


Dãy số - Phần 1

Dãy số - Phần 2Dãy số - Phần 3Dãy số - Phần 4Dãy số - Phần 5Dãy số - Phần 6Dãy số - Phần 7Dãy số - Phần 8Dãy số - Phần 9


Tam giác Pascal

Quy nạpQuy hấp thụ IIQuy nạp IIINhị thức Newton1 = 2012 = 2013Đa thức nội suy NewtonĐa thức nội suy LagrangeChứng minh Định lý Wilson bởi công thức nội suyTổng luỹ thừa


Số phức


Số phức

bí quyết Moivre


Lượng giác


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

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

Ngày số Pi (2016)

Radian là gì?


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 đến số hữu tỷ

Modulo mang đến 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ới định lý Wolstenholme

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

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

Bò đi nhỏ bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số kỳ lạ của Euler


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

Dãy số Fibonacci và một việc xếp hìnhHằng đẳng thức về hàng số FibonacciDãy số Fibonacci và tam giác Pascal


Định lý Pitago

Định lý con đường cao tam giác vuôngĐịnh lý MorleyPhương tíchTrục đẳng phương và trung tâm đẳng phươngĐịnh lý Ceva và Định lý MenelausLục giác kỳ diệuĐịnh lý PascalĐịnh lý PappusCánh bướm PascalBài toán nhỏ bướmĐịnh lý ngôi sao sáng Do TháiHãy chu đáo trường hợp sệt biệtBà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 bởi thước với compa

Bài toán phân chia hình tứ giácDựng hình ngũ giác đềuDựng hình nhiều giác đềuDựng đa giác gần như 15 cạnhĐịnh lý con đường cao tam giác vuôngThuật toán dựng hìnhCông thức lượng giác Gauss đến 17-giác đều Dựng hình chỉ bởi compa dùng compa chia phần đông đoạn thẳng