Ước chung lớn nhất là gì?
Ước chung lớn nhất (ƯCLN) của hai số nguyên dương a và b là số lớn nhất chia hết cả a và b. Ví dụ, các ước chung của 48 và 18 là 1, 2, 3, 6 — số lớn nhất là 6, nên ƯCLN(48, 18) = 6. Thuật toán Euclid là cách tìm ƯCLN nhanh và đẹp, có từ hơn 2000 năm trước.
Ý tưởng: lát hình bằng những hình vuông lớn nhất
Hãy hình dung một hình chữ nhật a×b. Ta lát nó bằng những hình vuông lớn nhất vừa khít — cạnh hình vuông bằng cạnh ngắn của hình chữ nhật. Lát được bao nhiêu hình vuông thì lát, phần còn lại là một hình chữ nhật nhỏ hơn; ta lại lát phần đó như cũ.
- Lấy cạnh hình vuông bằng cạnh ngắn của hình chữ nhật hiện tại.
- Lát càng nhiều hình vuông đó càng tốt dọc theo cạnh dài.
- Phần chưa lát là một hình chữ nhật nhỏ hơn (phần dư).
- Lặp lại trên phần dư cho đến khi lát kín hoàn toàn (dư bằng 0).
Thuật toán: phép chia có dư lặp lại
Đặt mỗi hàng hình vuông tương ứng với một phép chia có dư. Lát q hình vuông cạnh nhỏ rồi còn dư r chính là viết: cạnh lớn = q × cạnh nhỏ + r. Với ví dụ 48 và 18:
48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0
Mỗi bước thay cặp số (cạnh lớn, cạnh nhỏ) bằng (cạnh nhỏ, phần dư). Phần dư cứ nhỏ dần nên thuật toán luôn dừng. Khi phần dư cuối bằng 0, số chia của bước đó chính là ƯCLN.
Vì sao cạnh hình vuông cuối là ƯCLN?
Hình vuông cuối cùng lát kín mọi phần — tức cạnh của nó chia đều cả phần dư trước đó, rồi chia đều cạnh nhỏ, rồi chia đều cạnh lớn ban đầu. Vậy cạnh ấy là một ước chung của a và b.
Ngược lại, bất kỳ ước chung d nào của a và b cũng chia hết mọi phần dư (vì r = lớn − q×nhỏ), nên d không thể lớn hơn cạnh hình vuông cuối. Do đó cạnh hình vuông cuối đúng là ước chung lớn nhất — không có số nào lớn hơn lát kín được.
Câu hỏi thường gặp
Nếu a và b nguyên tố cùng nhau thì sao? Khi đó ƯCLN(a, b) = 1, và hình vuông cuối có cạnh 1 — tức ta phải lát đến tận những ô đơn vị mới khít hoàn toàn.
Có cần a lớn hơn b không? Không. Nếu a nhỏ hơn b, bước đầu chỉ đơn giản đổi chỗ hai cạnh; kết quả ƯCLN không đổi vì ƯCLN(a, b) = ƯCLN(b, a).
Ứng dụng: rút gọn phân số
ƯCLN xuất hiện ở khắp nơi trong toán học và đời sống:
- ➗ Rút gọn phân số: chia cả tử và mẫu cho ƯCLN, ví dụ 18/48 = 3/8 vì ƯCLN(18, 48) = 6.
- 📦 Chia đều: cắt tấm a×b thành các ô vuông lớn nhất bằng nhau không thừa.
- 🔐 Mật mã học: thuật toán Euclid mở rộng tìm nghịch đảo modulo trong RSA.
- 🎵 Nhịp điệu & bánh răng: tìm chu kỳ lặp chung của hai chuỗi tuần hoàn.