THUẬT TOÁN Ơ CƠ LÍT

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

Xem thêm: Dàn Ý Thuyết Minh Về Bút Máy (Lớp 8) Hay Nhất, Thuyết Minh Về Cây Bút Máy, Bút Bi

Dùng phép phân 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ừ bên 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 đề nghị 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ới thuật toán Euclid có nhiều ứng dụng trong vấn đề giải những phương trình nghiệm nguyên. Họ sẽ cẩn thận kỹ về đề bài này trong số kỳ sau. Nhất thời thời, họ 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$ thế nào cho số $2013 n$ có bố chữ số tận thuộc là $999$.Phân tích.

Xem thêm: Ngôn Ngữ Lập Trình Bậc Cao Là Gì, Ngôn Ngữ Lập Trình Bậc Cao Là

Ở vấn đề này chúng ta cần giải phương trình dưới đây $$2013 n = 999 = -1 pmod1000.$$Nếu họ tạm thời làm lơ modulo mà lại chỉ để ý đến 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à cũng chính vì chúng ta vẫn nhân hai vế của phương trình cùng với số nghịch hòn đảo của $a$.Cũng giống như như vậy, nếu chúng ta có phương trình modulo $$ax = b pmodp,$$ bạn có thể giải được nó bằng phương pháp nhân cả hai 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 bí quyết nhân cả nhị vế phương trình với $c$ bọn họ có $$ac x = bc pmodp.$$ vì chưng $ac = 1 pmodp$ cho nên $$x = bc pmodp.$$Bây giờ trở lại 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$ vào modulo $1000$. Chúng ta dùng đẳng thức Bezout sinh hoạt trên, đó là $$f 2013 imes 77 - f 1000 imes 155 = 1.$$Lấy modulo $1000$, bọn 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ó bố chữ số tận cùng là $999$ khi và chỉ khi $$2013 n = 999 = -1 pmod1000.$$Từ đẳng thức Bezout $$f 2013 imes 77 - f 1000 imes 155 = 1,$$ chúng ta có $$2013 imes 77 = 1 pmod1000.$$Nhân cả nhì vế phương trình sau với $77$ $$2013 n = -1 pmod1000,$$ chúng ta 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$, bọn họ có $n=923$, và $$2013 imes 923 = 1857999.$$Chúng ta tạm dừng chủ đề về bửa đề Bezout với thuật toán Euclid sống đây. Trong tương lai khi tất cả dịp bọn họ sẽ chú ý kỹ thêm về vận dụng của xẻ đề Bezout với thuật toán Euclid.Hẹn gặp mặt lại các bạn vào kỳ sau.Bài tập về nhà.1. Sử dụng thuật toán Euclid để tùy chỉnh đẳng thức Bezout mang đến hai số $2012$ với $999$.2. Giải phương trình nghiệm nguyên dưới đâ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 bắt đầu hơnBài đăng Cũ hơnTrang chủ

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


*

Lưu trữ Blog


►  2017(1) ►  2016(7) ►  2015(12) ►  2014(12) ►  2013(26) ▼  2012(36) ▼  mon mười một(7) ►  2011(7)
*

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

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

Mắt Biếc hồ nước Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci với một câu hỏi xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số bao gồm phương vi diệu của Vianney!

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

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

Chào năm mới 2014

Chào năm mới tết đến 2015

Chào năm mới 2016

Không gian 4d là gì?

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

Dựng đa giác phần lớn 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 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 nạp IIQuy hấp thụ 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

phương pháp 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 đến 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 vấn đề về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo mang lại 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 đố mẹo về đo lường

Dựng đa giác đầy đủ 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ố vi diệu của Euler


Bài toán liên kết facebook

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


Định lý Pitago

Định lý đường cao tam giác vuôngĐịnh lý MorleyPhương tíchTrục đẳng phương và trọng 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 con bướmĐịnh lý ngôi sao sáng Do TháiHãy cẩn thận trường hợp đặc biệtBài toán về tìm khoảng cách ngắn nhất và một đặc thù 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à compa

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