Lớp 6
Ước chung lớn nhất (thuật toán Euclid)
Ước chung lớn nhất (ƯCLN) của hai số tự nhiên là số lớn nhất chia hết cả hai. Thuật toán Euclid tìm ƯCLN bằng cách thay liên tiếp (a, b) bằng (b, a mod b) cho đến khi b = 0 — khi đó a chính là ƯCLN.
Nhập hai số (1 – 999) rồi nhấn "Bước" để xem từng bước rút gọn
a = q · b + r
| # | a | q · b | + r |
|---|---|---|---|
| Nhấn "Bước" để bắt đầu | |||
Thuật toán Euclid
Với mọi a, b ≥ 0 (không cùng bằng 0): ƯCLN(a, b) = ƯCLN(b, a mod b). Khi b = 0, ƯCLN = a.
Ví dụ
Tìm ƯCLN(48, 18). Bước 1: 48 = 2·18 + 12. Bước 2: 18 = 1·12 + 6. Bước 3: 12 = 2·6 + 0. Vậy ƯCLN(48, 18) = 6, và BCNN(48, 18) = 48·18 / 6 = 144.