Máy tính GCD / LCM (ƯCLN / BCNN)

Định nghĩa:

• UCLN(a, b): ước chung lớn nhất chia hết cả a và b.
• BCNN(a, b): số nhỏ nhất chia hết cho cả a và b.

Thuật toán Euclidean (tìm UCLN):

gcd(a, b) = gcd(b, a mod b) với gcd(a, 0) = a

Mối liên hệ:

UCLN(a, b) × BCNN(a, b) = a × b

→ BCNN(a, b) = a × b / UCLN(a, b).

Ví dụ: Tìm UCLN(48, 36).

48 = 1×36 + 12
36 = 3×12 + 0
→ UCLN = 12

BCNN(48, 36) = 48 × 36 / 12 = 144.

Ứng dụng:

• Rút gọn phân số: 36/48 → chia cả 2 cho UCLN(36,48) = 12 → 3/4
• Cộng phân số khác mẫu: dùng BCNN của 2 mẫu làm mẫu chung
• Lập lịch (vd 2 đèn nháy chu kỳ a, b — sau BCNN(a,b) giây cả 2 cùng sáng)

1. Chọn loại: UCLN hay BCNN.
2. Nhập 2-10 số nguyên dương, cách nhau dấu phẩy.
3. Nhấn “Tính”. Kết quả + các bước trung gian.

Tại sao thuật toán Euclidean hoạt động — nguyên lý đằng sau một công thức 2.300 năm tuổi

Thuật toán Euclidean trong khối đầu bài (gcd(a, b) = gcd(b, a mod b)) trông kỳ diệu nhưng dựa trên một quan sát đơn giản: mọi ước chung của a và b cũng là ước chung của b và (a mod b). Tại sao?

Vì a = q×b + r (với r = a mod b), nên a − q×b = r. Nếu d là ước chung của a và b → d chia hết a và d chia hết q×b → d chia hết (a − q×b) = r. Suy ra d cũng là ước của r. Tập hợp ước chung của (a, b) hoàn toàn trùng với tập hợp ước chung của (b, r) — vậy UCLN của hai cặp bằng nhau.

Mỗi bước, số nhỏ hơn trong cặp giảm dần và luôn dương → sau hữu hạn bước tất yếu đến 0. Khi b = 0, UCLN(a, 0) = a vì mọi số đều chia hết cho a và 0 chia hết cho mọi số. Đây là trường hợp dừng.

Minh họa bằng ví dụ trong khối đầu bài theo chiều ngược lại để thấy rõ tại sao kết quả đúng:

Thuật toán có độ phức tạp O(log(min(a,b))) — cực kỳ nhanh ngay cả với số hàng tỷ. Đây là lý do std::gcd() trong C++17 và math.gcd() trong Python đều cài đặt thuật toán Euclidean ở nhân.

Cách dùng công cụ UCLN/BCNN trên VJOL — đơn lẻ và nhiều số cùng lúc

1. Nhập hai số cần tính: Nhập a và b vào hai ô tương ứng. Cả hai phải là số nguyên dương. Thứ tự nhập không ảnh hưởng kết quả: UCLN(48, 36) = UCLN(36, 48) = 12.
2. Chọn phép tính: “Tính UCLN”, “Tính BCNN”, hoặc “Tính cả hai”.
3. Đọc kết quả và bảng các bước: Công cụ hiển thị UCLN, BCNN và bảng từng bước thuật toán Euclidean — hữu ích khi học và cần kiểm tra kết quả tay.

Mở rộng cho nhiều hơn 2 số: UCLN và BCNN của nhiều số tính lần lượt từng cặp. Công thức tổng quát:

• UCLN(a, b, c) = UCLN(UCLN(a, b), c)
• BCNN(a, b, c) = BCNN(BCNN(a, b), c)

Ví dụ: UCLN(12, 18, 24) = UCLN(UCLN(12, 18), 24) = UCLN(6, 24) = 6. Công cụ xử lý chuỗi nhiều số nếu có ô nhập liệu mở rộng; nếu không, tính từng cặp lần lượt.

Sáu ứng dụng thực tế của UCLN và BCNN

Hai khái niệm tưởng như thuần học thuật này xuất hiện thường xuyên trong đời sống và lập trình:

• Rút gọn phân số (UCLN): Để rút gọn 36/48, tìm UCLN(36, 48) = 12 rồi chia cả tử và mẫu: 36÷12 / 48÷12 = 3/4. Máy tính khoa học và ngôn ngữ lập trình dùng đúng thao tác này khi biểu diễn phân số dạng tối giản.
• Cộng trừ phân số khác mẫu (BCNN): Cộng 1/4 + 1/6: tìm BCNN(4, 6) = 12 làm mẫu chung → 3/12 + 2/12 = 5/12. Đây là bước bắt buộc trong mọi phép cộng phân số — BCNN cho mẫu số chung nhỏ nhất để tránh tính với số lớn không cần thiết.
• Chia đều không dư (UCLN): Đóng gói 72 lon nước và 48 gói snack vào các túi quà giống hệt nhau (mỗi túi có cùng tỷ lệ). Số túi tối đa có thể tạo = UCLN(72, 48) = 24 túi (mỗi túi 3 lon + 2 gói).
• Lập lịch đồng bộ (BCNN): Tàu A rời bến mỗi 15 phút, tàu B mỗi 20 phút — cả hai cùng xuất phát lần đầu lúc 6:00. Lần tiếp theo cả hai cùng khởi hành: BCNN(15, 20) = 60 phút sau → lúc 7:00. Bài toán này áp dụng cho bất kỳ chu kỳ đồng bộ nào: đèn giao thông, máy in, cập nhật server.
• Thiết kế lưới và gạch lát (BCNN): Lát nền bằng hai loại gạch hình vuông — loại 24cm và loại 36cm — sao cho khớp viền không cần cắt. Kích thước ô lưới nhỏ nhất: BCNN(24, 36) = 72cm. Áp dụng cho thiết kế trang web (grid system), lưới pixel trong đồ họa.
• Lập trình và thuật toán (UCLN/BCNN): Trong Python math.gcd(a, b) và math.lcm(a, b) (từ Python 3.9) được dùng để chuẩn hóa tần số lấy mẫu audio, đồng bộ frame rate video, và tối ưu vòng lặp trong xử lý tín hiệu số.

Sai lầm thường gặp khi tính UCLN và BCNN

Bốn lỗi phổ biến nhất trong bài tập và thực hành:

• Nhầm UCLN với BCNN trong bài toán rút gọn phân số: Để rút gọn phân số, dùng UCLN (chia để số nhỏ hơn). Để tìm mẫu số chung, dùng BCNN (nhân để số lớn hơn). Nhầm dùng BCNN để rút gọn cho kết quả sai hoàn toàn.
• Tính BCNN bằng cách nhân thẳng mà không chia UCLN: BCNN(12, 18) ≠ 12×18 = 216. Công thức đúng: BCNN = 12×18 / UCLN(12, 18) = 216 / 6 = 36. Bỏ bước chia UCLN làm kết quả lớn hơn thực tế nhiều lần.
• Sai khi một trong hai số bằng 0: UCLN(a, 0) = a theo định nghĩa. BCNN(a, 0) = 0 (theo quy ước — bội chung của a và 0 phải chia hết cho 0, mà chỉ có 0 chia hết cho 0). Nhiều học sinh bối rối khi gặp trường hợp này.
• Tính UCLN/BCNN của nhiều số theo cặp sai thứ tự và không kết hợp đúng: Để tính UCLN(12, 18, 24), phải kết hợp dần: UCLN(12, 18) = 6, rồi UCLN(6, 24) = 6. Không được tính riêng lẻ UCLN(12, 18) = 6, UCLN(18, 24) = 6 rồi lấy max = 6 — may mắn đúng trong trường hợp này nhưng sai về phương pháp và sẽ sai với bộ số khác.

Câu hỏi thường gặp

Hai số nguyên tố cùng nhau (nguyên tố cùng nhau) là gì?

Hai số a và b gọi là nguyên tố cùng nhau (coprime) khi UCLN(a, b) = 1 — tức là không có ước chung nào lớn hơn 1. Ví dụ: 8 và 15 không phải số nguyên tố nhưng UCLN(8,15) = 1 vì 8 = 2³ và 15 = 3×5 không có thừa số chung. Khái niệm này quan trọng trong mật mã (RSA dùng số nguyên tố cùng nhau) và lý thuyết số.

UCLN của hai số nguyên tố bất kỳ bằng bao nhiêu?

Luôn bằng 1 — vì số nguyên tố chỉ có ước là 1 và chính nó. Hai số nguyên tố phân biệt không thể có ước chung nào khác 1. Hệ quả: BCNN của hai số nguyên tố p và q bằng p×q (vì BCNN = p×q / UCLN = p×q / 1 = p×q).

Làm thế nào để kiểm tra nhanh BCNN bằng tay cho hai số nhỏ?

Liệt kê bội của số lớn hơn cho đến khi tìm thấy bội chia hết cho số còn lại. Ví dụ: BCNN(8, 12) → bội của 12: 12 (12÷8 dư 4), 24 (24÷8 = 3 đúng) → BCNN = 24. Cách này nhanh cho số nhỏ; với số lớn hơn thì dùng công thức BCNN = a×b / UCLN(a,b) hoặc công cụ.

UCLN có thể lớn hơn cả hai số không?

Không bao giờ. UCLN(a, b) luôn ≤ min(a, b) vì UCLN là ước của a → UCLN ≤ a, và là ước của b → UCLN ≤ b. UCLN đạt giá trị lớn nhất khi một số là ước của số kia: UCLN(12, 36) = 12 = min(12, 36).

Máy tính UCLN và BCNN trên VJOL xử lý thuật toán Euclidean trong một bước — nhập hai số, nhận ngay kết quả kèm bảng từng bước giải. Từ rút gọn phân số trong bài tập lớp 6 đến đồng bộ chu kỳ trong lập trình hệ thống, hai phép tính này xuất hiện nhiều hơn bạn tưởng và đáng được làm chủ hoàn toàn.

Xem thêm các công cụ liên quan

• giải tam giác online — tính cạnh, góc, diện tích tam giác từ các thông số đã biết theo định lý hàm số sin và cosin.
• tính nguyên hàm online — tính nguyên hàm hàm số một biến kèm các bước giải theo quy tắc tích phân.
• bảng tuần hoàn Mendeleev — tra cứu đầy đủ 118 nguyên tố hóa học với số hiệu, khối lượng nguyên tử và cấu hình electron.
• chuyển đổi ngoại tệ online — tra tỷ giá và đổi tiền giữa VND và hơn 10 đồng tiền phổ biến trên thế giới.