Máy tính GCD & LCM (kèm phân tích nhân tử nguyên tố)

GCD: nhân tử chung lớn nhất

GCD của hai số nguyên là số nguyên lớn nhất chia hết cả hai mà không có phần dư. GCD(12, 18) = 6 vì 6 chia hết cả hai và không có số nào lớn hơn làm được điều này. GCD(7, 13) = 1 vì chúng không có nhân tử chung nào (các cặp như vậy gọi là 'nguyên tố cùng nhau').

Chúng tôi sử dụng thuật toán Euclid: gcd(a, b) = gcd(b, a mod b), đệ quy. Đã được biết đến ~2300 năm và vẫn là phương pháp tiêu chuẩn nhanh nhất. Với ba số trở lên, gcd(a, b, c) = gcd(gcd(a, b), c).

LCM: bội chung nhỏ nhất

LCM là số nguyên dương nhỏ nhất là bội của cả hai. LCM(4, 6) = 12 vì 12 là số đầu tiên mà cả 4 và 6 đều chia hết.

Công thức: lcm(a, b) = (a × b) / gcd(a, b). Với 4 và 6: 24 / 2 = 12. Với ba số: lcm(a, b, c) = lcm(lcm(a, b), c).

Nếu bất kỳ số nào là 0, LCM là 0 (mọi số đều chia hết 0, nhưng 'nhỏ nhất dương' không xác định). Máy tính trả về 0 trong trường hợp đó.

Tại sao điều này quan trọng

Phân số: để cộng 1/4 + 1/6, tìm LCM(4, 6) = 12 là mẫu số chung. 1/4 = 3/12, 1/6 = 2/12, tổng = 5/12.

Lịch trình: nếu sự kiện A lặp lại mỗi 4 ngày và sự kiện B mỗi 6 ngày, chúng trùng nhau mỗi LCM(4, 6) = 12 ngày.

Mật mã học: các thuật toán dựa trên GCD (Euclid mở rộng) là nền tảng của tạo khóa RSA và tính toán nghịch đảo modulo.

Lý thuyết âm nhạc: các nhịp điệu với chu kỳ 3 và 4 đồng bộ sau 12 nhịp (LCM).