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 54:
 
== Tính toán ==
ƯCLN của hai2 hay nhiều số có thể tìm được bằng việccách phân tích haicác số đó ra thừa số nguyên tố, chẳng hạn để tìm ƯCLN(18,84), ta phân tích 18&nbsp;=&nbsp;2·3<sup>2</sup> và 84&nbsp;=&nbsp;2<sup>2</sup>·3·7 và nhận xét rằngchọn các thừa số chungnguyên vớitố sốchung mũcủa dươngtất nhỏcả nhất của haicác số nàyđó. là 2·3; doKhi đó ƯCLN(18,84)&nbsp;=&nbsp;6. Trêncần thựctìm tếlà phươngtích phápcủa nàycác chỉthừa dùngsố chosau cáckhi sốnâng nhỏ;lũy việcthừa phânbậc tíchnhỏ cácnhất sốcủa lớn ramỗi thừa số nguyên tố mất rất nhiều thời gian.
 
VD: Để tìm ƯCLN(18,84), ta phân tích 18&nbsp;=&nbsp;2·3<sup>2</sup> và 84&nbsp;=&nbsp;2<sup>2</sup>·3·7 và nhận xét rằng các thừa số chung với số mũ dương nhỏ nhất của hai số này là 2·3; do đó ƯCLN(18,84)&nbsp;=&nbsp;6.
 
Nếu không có thừa số nguyên tố chung nào thì xem như ƯCLN của các số đó là 1 và các số đó được gọi là các số nguyên tố cùng nhau.
 
VD: 10 = 2·5 và 9=3<sup>2</sup> không có thừa số nguyên tố nào chung nên 9 và 10 là 2 số nguyên tố cùng nhau và ƯCLN(9,10) = 1
 
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 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ư.
Lấy từ “https://vi.wikipedia.org/wiki/Ước_số_chung_lớn_nhất”