Báo cáo học liệu
Mua học liệu
Mua học liệu:
-
Số dư ví của bạn: 0 coin - 0 Xu
-
Nếu mua học liệu này bạn sẽ bị trừ: 2 coin\Xu
Để nhận Coin\Xu, bạn có thể:
Em có biết (Thuật toán Euclid) SVIP
Tìm ước chung lớn nhất bằng nhận xét sau:
Nếu \(a,b\) là hai số tự nhiên với \(a\ge b\) và \(a=b.q+r\), \(r\) là số dư của phép chia \(a\) cho \(b\) thì ƯCLN\(\left(a,b\right)=\) ƯCLN\(\left(b,r\right)\).
THUẬT TOÁN EUCLID (Ơ-CLÍT)
Bước 1. Thực hiện phép chia \(a\) cho \(b\):
\(a=b.p+r\) với \(r< b\) là số dư của phép chia này.
Nếu \(r=0\) thì \(a⋮b\), do đó ƯCLN\(\left(a,b\right)=b\).
Nếu \(r\ne0\) thì ƯCLN\(\left(a,b\right)=\) ƯCLN\(\left(b,r\right)\).
Sau bước 1, chúng ta chuyển việc tìm ƯCLN của hai số \(a\) và \(b\) về việc tìm ƯCLN của hai số nhỏ hơn là \(b\) và \(r\).
Bước 2. Thực hiện các phép toán như Bước 1, tức là thực hiện phép chia \(b\) cho \(r\).
\(b=rs+t\) với \(t< r\).
Nếu \(t=0\) thì \(b⋮r\), do đó ƯCLN\(\left(b,r\right)=r\).
Nếu \(t\ne0\) thì ƯCLN\(\left(b,r\right)=\) ƯCLN\(\left(r,t\right)\).
Quá trình này tiếp tục đến khi phép chia không còn dư. Khi đó ƯCLN chính là số chia của phép chia không còn dư đó.
Ví dụ:
Để tìm ƯCLN(4 836, 234), người ta thực hiện các phép chia 4 836 cho 234 (dư 156); Thực hiện phép chia 234 cho 156 (dư 78). Vì 156 chia hết cho 78, suy ra ƯCLN(4 836, 234) \(=78\).
Bạn có thể đánh giá bài học này ở đây