Hàm Euler Phi là gì?
Hàm Euler phi, ký hiệu \(\varphi(n)\), đếm xem có bao nhiêu số nguyên dương từ 1 đến n không có ước chung nào với n ngoài 1 — nói cách khác, đó là những số nguyên tố cùng nhau với n. Ví dụ, \(\varphi(9) = 6\) vì các số 1, 2, 4, 5, 7 và 8 đều nguyên tố cùng nhau với 9. Đây là một hàm nền tảng trong lý thuyết số và xuất hiện khắp nơi trong mật mã học, nổi tiếng nhất là trong thuật toán RSA, nơi \(\varphi(n)\) quyết định nghịch đảo modulo dùng để tạo khóa.
Cách sử dụng máy tính này
Bạn chỉ cần nhập một số nguyên dương n bất kỳ rồi nhấn tính. Công cụ sẽ phân tích n thành các ước nguyên tố phân biệt, áp dụng công thức tích và trả về giá trị \(\varphi(n)\) ngay lập tức, kèm theo danh sách các số nguyên tố phân biệt mà nó tìm được. Máy tính hoạt động tốt với cả số nhỏ lẫn số rất lớn lên đến một tỷ.
Giải thích công thức
Cách tính hàm phi hiệu quả nhất là dùng công thức tích:
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$
lấy trên mọi số nguyên tố phân biệt p là ước của n.
Bạn chỉ cần các số nguyên tố phân biệt, không quan tâm đến số mũ của chúng. Mỗi thừa số \(\left(1 - \frac{1}{p}\right)\) loại bỏ phần các số chia hết cho số nguyên tố đó.
Ví dụ minh họa
Lấy n = 36. Phân tích thừa số nguyên tố của nó là \(2^2 \times 3^2\), nên các số nguyên tố phân biệt là 2 và 3. Khi đó:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$
Vậy có đúng 12 số nguyên trong khoảng từ 1 đến 36 nguyên tố cùng nhau với 36.
Câu hỏi thường gặp
\(\varphi(1)\) bằng bao nhiêu? Theo quy ước, \(\varphi(1) = 1\), vì 1 nguyên tố cùng nhau với chính nó.
φ của một số nguyên tố p bằng bao nhiêu? Với mọi số nguyên tố p, ta có \(\varphi(p) = p - 1\), bởi vì mọi số nguyên từ 1 đến \(p-1\) đều nguyên tố cùng nhau với p.
Hàm φ có tính nhân không? Có. Nếu \(\gcd(a, b) = 1\) thì \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\), và đây chính là lý do tại sao tích trên các số nguyên tố phân biệt lại đúng.
