Thuật toán euclid tìm ước chung lớn nhất

     
Kỳ trước chúng ta đã học về xẻ đề Bezout. Hôm nay chúng ta vẫn học về thuật toán Euclid. Thuật toán này dùng làm xác định các hệ số vào đẳng thức Bezout.

Bạn đang xem: Thuật toán euclid tìm ước chung lớn nhất


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

Xem thêm: Tôi Đã Hack Violympic (@Hackviolympic) / Twitter, Hack Violympic (@Hackviolympic) / Twitter

Dùng phép chia $b = aq + r$ nhằm làm nhỏ 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,$$ do đó $d=(1000,2013) = 1$
Bước 2.
Bắt đầu từ dưới lên, viết những phương trình về dạng $r = b - aq$(phương trình cuối cùng không đề xuất 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ó không ít ứng dụng trong câu hỏi giải những phương trình nghiệm nguyên. Bọn họ sẽ chăm chú kỹ về chủ đề này trong số kỳ sau. Trợ thời thời, bọn họ xem xét bài toán sau đây.Bài toán.
Tìm toàn bộ 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: Hot Girl Ribi Sachi Bao Nhiêu Tuổi, Ribi Sachi Cao Bao Nhiêu

Ở câu hỏi này bọn họ cần giải phương trình dưới đây $$2013 n = 999 = -1 pmod1000.$$Nếu họ tạm thời bỏ lỡ modulo cơ mà 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à bởi vì chúng ta đã nhân hai vế của phương trình 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,$$ chúng ta có thể giải được nó bằng cách 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$ thế nào cho $$ac = 1 pmodp.$$Bằng phương pháp nhân cả nhì vế phương trình với $c$ bọn họ có $$ac x = bc pmodp.$$ bởi vì $ac = 1 pmodp$ cho nên vì vậy $$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 yêu cầu tìm nghịch hòn đảo của $2013$ trong modulo $1000$. Chúng ta dùng đẳng thức Bezout ngơi nghỉ 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$ vào modulo $1000$ đó là $77$.Lời giải. Số $2013 n$ có cha chữ số tận thuộc là $999$ khi và chỉ còn khi $$2013 n = 999 = -1 pmod1000.$$Từ đẳng thức Bezout $$f 2013 imes 77 - f 1000 imes 155 = 1,$$ họ có $$2013 imes 77 = 1 pmod1000.$$Nhân cả hai vế phương trình sau với $77$ $$2013 n = -1 pmod1000,$$ bọn họ có $$2013 imes 77 n = -77 pmod1000.$$Vì $2013 imes 77 = 1 pmod1000$, chúng ta có $$n = -77 = 923 pmod1000.$$Tóm lại số $n$ đề xuất tìm là $n = 923 + 1000 k$.Kiểm chứng, cùng với $k=0$, chúng ta có $n=923$, và $$2013 imes 923 = 1857999.$$Chúng ta tạm dừng chủ đề về ngã đề Bezout cùng thuật toán Euclid ở đây. Về sau khi gồm dịp bọn họ sẽ để mắt tới 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. Cần sử dụng thuật toán Euclid để tùy chỉnh đẳng thức Bezout mang đến hai số $2012$ cùng $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 tiếp 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 liên kết facebook

Phép nhân thời thiết bị đá

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 cùng một việc xếp hình

James vẽ hình

Câu hỏi của James

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

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

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

Chào năm mới 2014

Chào năm mới 2015

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

Không gian 4d là gì?

Dựng hình đa 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ởi 1 không? (2015)

Hình tam giác

Bàn cờ vua cùng kim từ 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 đến góc bội

Công thức lượng giác Gauss mang đế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 mang lại 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 cùng định lý Wolstenholme

Câu iq về đo lường

Dựng đa giác phần đông 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 liên kết 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ới tam giác Pascal


Định lý Pitago

Định lý mặt đườ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ới Định lý MenelausLục giác kỳ diệuĐịnh lý PascalĐịnh lý PappusCánh bướm PascalBài toán bé bướmĐịnh lý ngôi sao Do TháiHãy để mắt tới trường hợp sệt biệtBài toán về tìm khoảng cách ngắn nhất cùng 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ới compa

Bài toán phân tách hình tứ giácDựng hình ngũ giác đềuDựng hình nhiều giác đềuDựng nhiều giác phần nhiều 15 cạnhĐịnh lý mặt đườ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 đông đảo Dựng hình chỉ bằng compa sử dụng compa chia đều đoạn thẳng