Máy Tính GCD & LCM

Tính ước chung lớn nhất (GCD) và bội chung nhỏ nhất (LCM) với các bước thuật toán Euclid hoàn chỉnh. Hỗ trợ hai hoặc nhiều số.

Máy Tính GCD & LCM là gì?

Ước số chung lớn nhất (GCD) và Bội số chung nhỏ nhất (LCM) là hai trong số những khái niệm quan trọng nhất trong lý thuyết số sơ cấp, với ứng dụng từ rút gọn phân số ở trường trung học đến các thuật toán mật mã bảo mật internet.

Thuật toán Euclid, được mô tả bởi Euclid khoảng 300 TCN, là một trong những thuật toán lâu đời nhất và hiệu quả nhất trong toán học. Nó tính GCD trong O(log(min(a,b))) bước, kết thúc nhanh chóng ngay cả với số rất lớn. Thuật toán áp dụng đẳng thức: GCD(a, b) = GCD(b, a mod b) lặp lại cho đến khi số dư bằng không.

Máy tính này hiển thị thuật toán Euclid hoàn chỉnh từng bước cho hai số và cũng tính GCD và LCM cho danh sách nhiều số bằng cách tổng quát hóa: GCD(a, b, c) = GCD(GCD(a, b), c).

Công Thức

GCD(a, b) — Euclidean Algorithm:

GCD(a, b) = GCD(b, a mod b), repeat until b = 0

Example: GCD(48, 18)

48 ÷ 18 = 2 remainder 12

18 ÷ 12 = 1 remainder 6

12 ÷ 6 = 2 remainder 0

GCD = 6

LCM(a, b) = |a × b| / GCD(a, b)

For multiple numbers:

GCD(a, b, c) = GCD(GCD(a, b), c)

LCM(a, b, c) = LCM(LCM(a, b), c)

Cách Tính

Nhập hai số nguyên dương a và b.
Xem GCD và LCM với giải thích.
Thay a bằng b và b bằng r. Lặp lại cho đến khi r = 0.
Số dư khác không cuối cùng là ƯCLN.
Tính BCNN = |a × b| / ƯCLN sử dụng đồng nhất thức cơ bản.
Dùng chế độ Nhiều Số cho ba số trở lên.

Ví Dụ

Tìm ƯCLN(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. ƯCLN = 6. BCNN = |48×18|/6 = 864/6 = 144. Kiểm tra: 144/48 = 3 ✓, 144/18 = 8 ✓.

Các Thuật Ngữ Chính Được Giải Thích

GCD (Ước số chung lớn nhất): Số lớn nhất chia hết tất cả các số đầu vào
LCM (Bội số chung nhỏ nhất): Số nhỏ nhất chia hết cho tất cả các số đầu vào
Số nguyên tố: Số chỉ chia hết cho 1 và chính nó
Phân tích thừa số nguyên tố: Biểu diễn số thành tích các số nguyên tố
Phép Modulo: a mod b là số dư khi a chia cho b
Tính Chia Hết: a chia hết cho b nếu b/a không có số dư

Trường Hợp Sử Dụng Phổ Biến

Rút gọn phân số: giảm a/b bằng cách chia cả hai cho GCD(a, b)
Cộng phân số với mẫu số khác nhau: tìm LCM của các mẫu số
Lập lịch: tìm thời điểm hai sự kiện định kỳ sẽ trùng nhau tiếp theo
Tạo khóa RSA: kiểm tra số mũ e là nguyên tố cùng nhau với φ(n)
Bài toán tỷ số bánh răng trong kỹ thuật cơ khí
Thiết kế mẫu gạch: tìm đơn vị lặp nhỏ nhất

Câu Hỏi Thường Gặp

GCD là gì và nó được tính như thế nào?

GCD (Ước số chung lớn nhất) là số nguyên dương lớn nhất chia hết cả a và b mà không có dư. Thuật toán Euclid tính nó một cách hiệu quả: lặp lại thay thế (a, b) bằng (b, a mod b) cho đến khi b = 0. Giá trị khác không cuối cùng là GCD.

LCM là gì và nó được dùng để làm gì?

LCM (Bội số chung nhỏ nhất) là số nguyên dương nhỏ nhất chia hết cho cả a và b. Nó được sử dụng để cộng phân số với mẫu số khác nhau, các bài toán lập lịch và lý thuyết âm nhạc.

Mối quan hệ giữa GCD và LCM là gì?

GCD(a, b) × LCM(a, b) = |a × b|. Khi bạn biết GCD, LCM đơn giản là |a × b| / GCD(a, b). Điều này hiệu quả hơn là liệt kê các bội số.

Nguyên tố cùng nhau có nghĩa là gì?

Hai số là nguyên tố cùng nhau nếu GCD của chúng là 1 — chúng không có thừa số nguyên tố chung. Tính nguyên tố cùng nhau là cơ bản trong số học mô-đun, mật mã học và Định lý Phần dư Trung Hoa.