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

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

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


Bổ đề Bezout.Nếu $d$ là ước số bình thường lớn nhất của nhì số ngulặng $a$ cùng $b$ thì vẫn vĩnh cửu hai số ngulặng $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 ước số tầm thường lớn nhất $d$ của nhị số $a$ với $b$, cùng xác định nhị 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 cực kỳ dễ dàng và đơn giản với thoải mái và tự nhiên.trước hết bọn họ nói về câu hỏi đi kiếm ước số phổ biến lớn nhất của cặp số $a$, $b$.Giả sử nlỗi $a = 45$, $b = 155$. Làm sao chúng ta tìm kiếm được ước số phổ biến lớn số 1 của cặp số này?Có một cách làm khôn xiết thoải mái và tự nhiên, sẽ là có tác dụng nhỏ dại các con số lại. Chúng ta hiểu được ước số chung lớn nhất của cặp số $(a,b)$ cũng chính là ước số bình thường lớn số 1 của cặp số $(a, b-a)$.Trong ví dụ này, họ tất cả cặp số $a = 45$, $b = 155$. Chúng ta có thể làm cho nhỏ số lượng $b$ lại bởi con số $$b-a = 110.$$ vì thế ước số phổ biến lớn số 1 của cặp số $(45, 155)$ đó là ước số thông thường lớn số 1 của cặp số $(45, 110)$.Con số $b-a=110$ vẫn hoàn toàn có thể làm nhỏ tuổi lại bằng cách mang $$(b - a) - a = 110-45 = 65,$$ với $$b - 3a = 65-45 = đôi mươi.$$Cuối cùng, họ tất cả cặp số $(45, 20)$. Tóm lại, nếu họ đem $b$ phân tách mang lại $a$ bao gồm số dư là $r$ nlỗi sau $$b = aq + r,$$ thì ước số tầm thường lớn nhất của cặp số $(a,b)$ chính là bằng ước số thông thường lớn số 1 của cặp số nhỏ dại rộng $(a,r)$.Đây chính là cơ bản của thuật toán Euclid.Chúng ta bước đầu lại từ trên đầu nhé. Chúng ta bao gồm $$155 = 45 imes 3 + 20,$$ vì vậy $(45, 155) = (45, 20)$. Làm tiếp $$45 = đôi mươi imes 2 + 5,$$ cho nên vì thế $(45, 20) = (đôi mươi,5)$. Tiếp tục, $$trăng tròn = 5 imes 4 + 0,$$ cho nên vì vậy $(đôi mươi,5) = 5$. vì thế bọn họ sẽ đưa ra ước số tầm thường lớn nhất, kia đó là $5$.Bây giờ đồng hồ bọn họ xem bí quyết kiếm tìm số $x$, $y$ trong đẳng thức Bezout $$d = a ~x + b ~y.$$Cách 1. Chúng ta làm như bên trên nhằm đưa ra ước số thông thường lớn số 1 là $d$.$$155 = 45 imes 3 + 20,$$ $$45 = trăng tròn imes 2 + 5,$$ $$trăng tròn = 5 imes 4 + 0,$$ cho nên $d=(45,155) = 5$
Cách 2.
Bắt đầu tự dưới lên, bọn họ theo thứ tự viết các phương trình $b = aq + r$ về dạng $r = b - aq$(phương thơm trình ở đầu cuối bao gồm số dư bằng $0$ đề xuất không cần phải viết)$$d = 5 = 45 - đôi mươi imes 2,$$ $$trăng tròn = 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 thuộc có tác dụng một ví dụ khác nhé. Ví dụ $a = 1000$, $b = 2013$.Cách 1.

See more: Trường Cao Đẳng Hòa Bình Xuân Lộc Thông Báo Tuyển Sinh Năm 2021

Dùng phxay chia $b = aq + r$ để triển khai bé dại bộ số $(b,a) o lớn (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ì thế $d=(1000,2013) = 1$
Bước 2.
Bắt đầu trường đoản cú dưới lên, viết các phương thơm trình về dạng $r = b - aq$(phương thơm trình cuối cùng ko yêu cầu 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 áp dụng trong Việc giải những phương trình nghiệm ngulặng. Chúng ta đã chăm chú kỹ về chủ đề này trong số kỳ sau. Tạm thời, họ để mắt tới bài bác toán sau đây.Bài toán.
Tìm tất cả những số thoải mái và tự nhiên $n$ làm thế nào cho số $2013 n$ bao gồm tía chữ số tận thuộc là $999$.Phân tích.

See more: Cá Mập Đẻ Ra Con Hay Trứng Hay Đẻ Con? Ít 1001 Thắc Mắc: Cá Mập Đẻ Con Hay Trứng Hay Đẻ Con

Tại bài bác toán này chúng ta cần giải pmùi hương trình sau đây $$2013 n = 999 = -1 pmod1000.$$Nếu bọn họ tạm thời làm lơ modulo mà lại chỉ quan tâm mang lại phương thơm trình số thực dạng $$ax = b$$ thì phương thơm trình này còn có nghiệm là $$x = fracba,$$ đấy là bởi vì bọn họ sẽ nhân nhì vế của pmùi hươ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 tất 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ế với nghịch đảo của $a$.Nghịch đảo của $a$ trong modulo $p$ đó là số $c$ thế nào cho $$ac = 1 pmodp.$$Bằng biện pháp nhân cả nhì vế phương thơm trình cùng với $c$ họ tất cả $$ac x = bc pmodp.$$ Vì $ac = 1 pmodp$ cho nên vì thế $$x = bc pmodp.$$Bây giờ quay trở về bài bác tân oán thuở đầu, họ đề xuất giải pmùi hương trình $$2013 n = -1 pmod1000.$$Chúng ta cần tìm kiếm nghịch đảo của $2013$ trong modulo $1000$. Chúng ta dùng đẳng thức Bezout làm việc bên trên, đó là $$f 2013 imes 77 - f 1000 imes 155 = 1.$$Lấy modulo $1000$, bọn họ gồm $$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$ gồm cha chữ số tận cùng 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ọ gồm $$2013 imes 77 = 1 pmod1000.$$Nhân cả nhị vế phương thơm trình sau cùng với $77$ $$2013 n = -1 pmod1000,$$ chúng ta gồm $$2013 imes 77 n = -77 pmod1000.$$Vì $2013 imes 77 = 1 pmod1000$, họ gồm $$n = -77 = 923 pmod1000.$$Tóm lại số $n$ phải kiếm tìm là $n = 923 + 1000 k$.Kiểm bệnh, với $k=0$, họ gồm $n=923$, cùng $$2013 imes 923 = 1857999.$$Chúng ta tạm ngưng chủ đề về ngã đề Bezout cùng thuật tân oán Euclid ở đây. Sau này lúc bao gồm thời điểm chúng ta đã cẩn thận kỹ thêm về ứng dụng của ngã đề Bezout với thuật toán thù Euclid.Hẹn gặp gỡ lại chúng ta vào kỳ sau.Bài tập về đơn vị.1. Dùng thuật toán Euclid để tùy chỉnh thiết lập đẳng thức Bezout mang lại nhì số $2012$ cùng $999$.2. Giải pmùi hương trình nghiệm nguyên ổn dưới đâ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 thơm 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 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 thù kết nối facebook

Phnghiền nhân thời đồ vật đá

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 bài xích toán xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số chủ yếu phương thơm kỳ lạ của Vianney!

Câu IQ 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 tết đến 2015

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

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

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

Dựng nhiều giác hầu hết 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... bao gồm bởi 1 không? (2015)

Hình tam giác

Bàn cờ vua với klặng từ bỏ 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 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 bí quyết nội suyTổ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 mang đến 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ố nguim tố

Một vài ba bài toán thù về số ngulặng tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo đến số hữu tỷ II

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

Bổ đề Bezout

Thuật toán Euclid

Tổng luỹ thừa

Tổng luỹ quá cùng định lý Wolstenholme

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

Dựng đa giác nhữ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 tân oán kết nối facebook

Dãy số Fibonacci với một bài xích toán 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ý mặt đường cao tam giác vuôngĐịnh lý MorleyPhương tíchTrục đẳng phương với 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 chu đáo trường thích hợp sệt biệtBài tân oán về kiếm tìm khoảng cách nđính thêm nhất và một đặc điểm 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ằng thước với compa

Bài toán thù phân tách hình tđọng giácDựng hình ngũ giác đềuDựng hình nhiều giác đềuDựng đa giác phần lớn 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 phần đa Dựng hình chỉ bởi compa Dùng compa chia đầy đủ đoạn thẳng


Chuyên mục: Blog