Wikipedia

Khác biệt giữa bản sửa đổi của “Ước số chung lớn nhất”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Dòng 3:
Trong [[tiếng Anh]], ước chung lớn nhất gọi là '''greatest common divisor''' ('''gcd'''), '''greatest common factor''' ('''gcf'''),<ref>{{citation| last = Kelley| first = W. Michael| isbn = 9781592571611| page = 142| publisher = Penguin| title = The Complete Idiot's Guide to Algebra| url = https://books.google.com/books?id=K1hCltk-2RwC&pg=PA142| year = 2004}}.</ref> '''highest common factor''' ('''hcf'''),<ref>{{citation| last = Jones| first = Allyn| isbn = 9781864413786| page = 16| publisher = Pascal Press| title = Whole Numbers, Decimals, Percentages and Fractions Year 7| url = https://books.google.com/books?id=l-ItSuk-zngC&pg=PA16| year = 1999}}.</ref> '''greatest common measure''' ('''gcm'''),<ref>{{citation| last1 = Barlow| first1 = Peter| author1-link = Peter Barlow (mathematician)| last2 = Peacock| first2 = George| author2-link = George Peacock| last3 = Lardner| first3 = Dionysius| author3-link = Dionysius Lardner| last4 = Airy| first4 = Sir George Biddell| author4-link = George Biddell Airy| last5 = Hamilton| first5 = H. P.| author5-link = Henry Hamilton (priest)| last6 = Levy| first6 = A.| last7 = De Morgan| first7 = Augustus| author7-link = Augustus De Morgan| last8 = Mosley| first8 = Henry| page = 589| publisher = R. Griffin and Co.| title = Encyclopaedia of Pure Mathematics| url = https://books.google.com/books?id=3fIUAQAAMAAJ&pg=PA589| year = 1847}}.</ref> hay '''highest common divisor'''.<ref name="Hardy&Wright 1979 20">{{harvtxt|Hardy|Wright|1979|p=20}}</ref>
 
Trong trường hợp tất cả hai số nguyên ''a'' và ''b'' đều bằng 0 thì chúng không có ƯCLN vì khi đó mọi số tự nhiên khác không đều là ước chung của ''a''các vàsố ''b''đó. Nếu chỉ một trong haicác số ''a''đó hoặccó ''b''ít nhất 1 số bằng 0, sốvà kiaít nhất 1 số khác 0 thì ƯCLN của chúng bằng giáƯCLN trịcủa tuyệt đối củacác số khác 0.
 
==Tổng quan==
 
=== Ký hiệu ===
Ước chung lớn nhất của ''a''<sub>0</sub>, vàa<sub>1</sub>, ''ba<sub>2</sub>, ... a<sub>n</sub>'' được ký hiệu là ƯCLN(''a''<sub>0</sub>,&nbsp;''b'') a<sub>1</sub>, haya<sub>2</sub>, đơn... giản hơn là (''a<sub>n</sub>'',&nbsp;''b'' ), tiếng Anh ký hiệu là gcd(a,b).
 
=== Ví dụ ===
Dòng 18:
* Các ước của 45 là <math>1,3,9,15,45</math>.
 
Những số nằm trong cả hai danh sách được gọi là những ước chung của 27 và 45:<blockquote><math>1,3,9</math></blockquote>Trong đó số lớn nhất là 9. Vậy 9 là ước chung lớn nhất của 27 và 45. ViếViết UCLN(27,45)=9<br />{{Chính|Số nguyên tố cùng nhau}}
HaiCác số được gọi là [[số nguyên tố cùng nhau]] nếu ước chung lớn nhất của chúng bằng 1. Chẳng hạn, 9 và 28 là hai số nguyên tố cùng nhau.▼
<br />{{Chính|Số nguyên tố cùng nhau}}
▲Hai số được gọi là [[số nguyên tố cùng nhau]] nếu ước chung lớn nhất của chúng bằng 1. Chẳng hạn, 9 và 28 là hai số nguyên tố cùng nhau.
 
Ước chung lớn nhất được sử dụng để đưa một phân số về dạng [[phân số tối giản]]. Chẳng hạn, ƯCLN(42, 56)=14, do đó,
Hàng 28 ⟶ 27:
== Các tính chất ==
 
* Mọi ước chung của ''a''các và ''b''số là ước của ƯCLN(''a'',&nbsp;''b'') của các só đó.
 
* ƯCLN(Với các số nguyên ''a''<sub>0</sub>,&nbsp;''b'') a<sub>1</sub>, khia<sub>2</sub>, ... ''a<sub>n</sub>,'' và ''bƯCLN(''a<sub>0</sub>, khônga<sub>1</sub>, bằnga<sub>2</sub>, không... cả hai,a<sub>n</sub>'') có thể được định nghĩa tương đương như số nguyên dương ''d'' nhỏ nhất có dạng ''d''&nbsp;=&nbsp;''a''·''p''&nbsp;+&nbsp;''b''·''q''<math>\sum_{k=0}^n a_k x_k</math> trong đó ''p'' và ''qx<sub>k</sub>'' là các số nguyên. Định lý này được gọi là [[đẳng thức Bézout]]. Các số ''p'' và ''qx<sub>k</sub>'' có thể tính nhờ [[Giải thuật Euclid mở rộng]].▼
Bước
*ƯCLN(''a'',&nbsp;0) =|''a''|, với mọi ''a'' &ne; 0, vì mọi số khác không0 bất kỳ là ước của 0, và ước lớn nhất của ''a'' là|''a''|. Đây là trường hợp cơ sở trong thuật toán Euclid.▼
0 29 8 5 3 1 0 1 0 1 -3
1 8 5 3 1 0 1 -1 1 -3 4
2 5 3 2 1 1 -1 2 -3 4 -7
3 3 2 1 1 -1 2 -3 4 -7 11
4 2 1 0 2
▲* ƯCLN(''a'',&nbsp;''b''), khi ''a'' và ''b'' không bằng không cả hai, có thể được định nghĩa tương đương như số nguyên dương ''d'' nhỏ nhất có dạng ''d''&nbsp;=&nbsp;''a''·''p''&nbsp;+&nbsp;''b''·''q'' trong đó ''p'' và ''q'' là các số nguyên. Định lý này được gọi là [[đẳng thức Bézout]]. Các số ''p'' và ''q'' có thể tính nhờ [[Giải thuật Euclid mở rộng]].
▲*ƯCLN(''a'',&nbsp;0) =|''a''|, với mọi ''a'' &ne; 0, vì mọi số khác không bất kỳ là ước của 0, và ước lớn nhất của ''a'' là|''a''|. Đây là trường hợp cơ sở trong thuật toán Euclid.
*Nếu ''a'' là ước của tích ''b''·''c'', và ƯCLN(''a'',&nbsp;''b'')&nbsp;=&nbsp;''d'', thì ''a''/''d'' là ước của ''c''.
*Nếu ''m'' là số nguyên dương, thì ƯCLN(''m''·''a'',&nbsp;''m''·''b'')&nbsp;=&nbsp;''m''·ƯCLN(''a'',&nbsp;''b'').
*Nếu ''m'' là số nguyên bất kỳ, thì ƯCLN(''a''&nbsp;+&nbsp;''m''·''b'',&nbsp;''b'')&nbsp;=&nbsp;ƯCLN(''a'',&nbsp;''b''). Nếu ''m'' ước chung (khác 0) của ''a'' và ''b'', thì UCLN(''a''/''m'',&nbsp;''b''/''m'')&nbsp;=&nbsp;ƯCLN(''a'',&nbsp;''b'')/''m''.
*ƯCLN là một [[hàm có tính nhân]] theo nghĩa sau: nếu các số ''a''<sub>1</sub> và, ''a''<sub>2</sub>,...,a<sub>n</sub> là các số nguyên tố cùng nhau, thì ƯCLN(''a''<sub>1</sub>·''a''<sub>2</sub>·...a<sub>n</sub>,&nbsp;''b'') = ƯCLN(''a''<sub>1</sub>,&nbsp;''b'')·ƯCLN (''a''<sub>2</sub>,&nbsp;''b'')·...ƯCLN (''a<sub>n</sub>'',&nbsp;''b'').
*ƯCLN là hàm [[giao hoán]]: ƯCLN(''a'', ''b'') = ƯCLN(''b'', ''a'').
*ƯCLN là hàm [[kết hợp]]: ƯCLN(a,b,c)= ƯCLN(''a'', ƯCLN(''b'', ''c'')) = ƯCLN(ƯCLN(''a'', ''b''), ''c'').
*ƯCLN của ba số được tính nhờ công thức ƯCLN(''a'',&nbsp;''b'',&nbsp;''c'') = ƯCLN(ƯCLN(''a'',&nbsp;''b''),&nbsp;''c''), (hoặc vế kia của tính chất kết hợp. Điều này có thể mở rộng cho số bất kỳ các số nguyên.
*ƯCLN (''a'',&nbsp;''b'') quan hệ chặt chẽ với BCNN(''a'',&nbsp;''b''): ta có
::ƯCLN(''a'',&nbsp;''b'')·BCNN(''a'',&nbsp;''b'')&nbsp;=&nbsp;''a''·''b''.
:Công thức này thường được dùng để tính BCNN của 2 số. Dạng khác của mối quan hệ này là tính chất phân phối:
(''a'',&nbsp;''b''),&nbsp;ƯCLN(''a'',&nbsp;''c''))
 
::BCNN(''a'',&nbsp;ƯCLN(''b''a<sub>0</sub>,&nbsp;''c a<sub>1</sub>, a<sub>2</sub>, ... a<sub>n</sub>''))&nbsp;=&nbsp;ƯCLN(BCNN(''a'',&nbsp;''b''a<sub>0</sub>),&nbsp;BCNN(''a'',&nbsp;''c''a<sub>1</sub>), BCNN(a,a<sub>2</sub>),...,BCNN(a,a<sub>n</sub>)).
*Nếu sử dụng định nghĩa ƯCLN(0,&nbsp;0)&nbsp;=&nbsp;0 và BCNN(0,&nbsp;0)&nbsp;=&nbsp;0 thì khi đó tập các số tự nhiên trở thành một [[dàn đầy đủ]] [[dàn phân phối|phân phối]] với ƯCLN.
*Trong [[Hệ tọa độ Descartes]], ƯCLN(''a'',&nbsp;''b'') biểu diễn số các điểm với tọa độ nguyên trên đoạn thẳng nối các điểm (0,&nbsp;0) và (''a'',&nbsp;''b''), trừ chính điểm (0,&nbsp;0).
Hàng 64 ⟶ 57:
Trên thực tế phương pháp này chỉ dùng cho các số nhỏ. Việc phân tích các số lớn ra thừa số nguyên tố mất rất nhiều thời gian.
 
MộtĐể tìm ưcln của 2 số tự nhiên thì phương pháp hiệu quả là [[giải thuật Euclid]] dựa trên dãy liên tiếp các phép chia có dư.
 
Nếu ''a'' và ''b'' là các số khác không, thì ước chung lớn nhất của ''a'' và ''b'' có thể tính qua [[Bội số chung nhỏ nhất|bội chung nhỏ nhất]] (BCNN) của ''a'' và ''b'':
Lấy từ “https://vi.wikipedia.org/wiki/Ước_số_chung_lớn_nhất”