Công cụ kiểm tra số nguyên tố cùng nhau là gì?
Hai số nguyên được gọi là nguyên tố cùng nhau (tiếng Anh là coprime) khi số nguyên dương duy nhất chia hết cho cả hai số đó là 1. Nói cách khác, ước chung lớn nhất (gcd) của chúng đúng bằng 1. Công cụ này nhận vào hai số nguyên và cho bạn biết ngay lập tức chúng có nguyên tố cùng nhau hay không, đồng thời hiển thị ước chung lớn nhất của chúng.
Cách sử dụng
Nhập hai số nguyên vào ô a và b rồi nhấn tính. Công cụ sẽ tính \(\gcd(a,\ b)\) bằng thuật toán Euclid. Nếu gcd bằng 1, hai số nguyên tố cùng nhau; ngược lại, chúng có ước chung khác 1 và không nguyên tố cùng nhau. Dấu âm được bỏ qua vì tính nguyên tố cùng nhau chỉ phụ thuộc vào giá trị tuyệt đối.
Giải thích công thức
Thuật toán Euclid liên tục thay cặp \((a,\ b)\) bằng cặp \((b,\ a \bmod b)\) cho đến khi giá trị thứ hai bằng 0. Giá trị khác 0 cuối cùng chính là gcd. Hai số nguyên tố cùng nhau khi và chỉ khi gcd này bằng 1.
$$\text{Coprime} \iff \gcd\left(\text{a},\ \text{b}\right) = 1$$Ví dụ, 8 và 15 không có thừa số nguyên tố chung nào, nên \(\gcd = 1\) và chúng nguyên tố cùng nhau, dù bản thân không số nào là số nguyên tố.
Ví dụ minh họa
Xét \(a = 12\) và \(b = 35\). Các thừa số nguyên tố của 12 là 2 và 3; của 35 là 5 và 7. Chúng không có thừa số nguyên tố chung nào, nên
$$\gcd(12,\ 35) = 1$$Vì vậy 12 và 35 nguyên tố cùng nhau. Ngược lại, 12 và 18 có chung thừa số 6, nên \(\gcd = 6\) và chúng không nguyên tố cùng nhau.
Câu hỏi thường gặp
Hai số nguyên tố cùng nhau có bắt buộc phải là số nguyên tố không? Không. Nguyên tố cùng nhau nghĩa là chúng không có ước chung nào lớn hơn 1; bản thân các số đó không cần phải là số nguyên tố (ví dụ 8 và 9).
Số 1 có nguyên tố cùng nhau với mọi số không? Có. \(\gcd(1,\ n) = 1\) với mọi số nguyên \(n\), nên 1 nguyên tố cùng nhau với mọi số nguyên.
Hai số chẵn có bao giờ nguyên tố cùng nhau không? Không. Hai số chẵn bất kỳ luôn có chung thừa số 2, nên gcd của chúng tối thiểu bằng 2.
