LCM vs GCD
LCM vs GCD compared — least common multiple vs greatest common divisor, formulas and uses, with a free calculator.
The GCD (greatest common divisor) is the largest number that divides two values; the LCM (least common multiple) is the smallest number both divide into. They are linked: LCM(a,b) × GCD(a,b) = a × b.
LCM vs GCD at a glance
| LCM | GCD | |
|---|---|---|
| Meaning | Smallest common multiple | Largest common divisor |
| Always | ≥ both numbers | ≤ both numbers |
| Used for | Adding fractions, cycles | Simplifying fractions |
When to use LCM
Use the LCM to find a common denominator or when two cycles re-align.
When to use GCD
Use the GCD to simplify a fraction or split into equal groups.
Tools for LCM & GCD
Trình tính BCNN & ƯCLN
Tính ước chung lớn nhất và bội chung nhỏ nhất của bất kỳ danh sách số nguyên nào, kết quả chính xác. Chạy phía client.
Mở công cụMáy tính phân số
Cộng, trừ, nhân và chia phân số với tự động rút gọn, hiển thị kết quả dạng số thập phân và hỗn số. Chạy phía client.
Mở công cụTrình trực quan hóa phân tích thừa số nguyên tố
Phân tích thừa số nguyên tố dạng hoạt hình theo cây thừa số — tách một số thành các thừa số nguyên tố từng bước. Chạy ngay trên trình duyệt.
Mở công cụTrình trực quan hóa thuật toán Euclid (GCD)
Thuật toán Euclid dạng hoạt họa — tính GCD của hai số theo từng bước với phép rút gọn (a, b) → (b, a mod b). Chạy ngay trong trình duyệt.
Mở công cụLCM vs GCD
Thuật toán Euclid là gì?
Một phương pháp tính ước chung lớn nhất (GCD) của hai số nguyên bằng cách liên tục thay số lớn hơn bằng phần dư khi chia nó cho số nhỏ hơn, cho đến khi phần dư bằng 0.
Độ phức tạp thời gian của thuật toán Euclid là gì?
O(log min(a, b)) — số bước tỉ lệ với số chữ số, đó là lý do thuật toán cực kỳ nhanh ngay cả với các số rất lớn.
Vì sao gcd(a, b) = gcd(b, a mod b)?
Bất kỳ ước chung nào của a và b cũng chia hết a mod b (và ngược lại), nên tập hợp các ước chung — và do đó ước chung lớn nhất — không đổi qua phép thay thế này.
GCD được dùng để làm gì?
Rút gọn phân số, số học modulo, thuật toán Euclid mở rộng (nghịch đảo modulo, RSA), và tính bội chung nhỏ nhất qua công thức lcm(a,b) = a·b / gcd(a,b).