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ác ví dụ minh họa thêm
Ví dụ 1: một số nguyên tố, φ(13)
13 là số nguyên tố, nên thừa số nguyên tố duy nhất của nó chính là 13:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. Kết quả này khớp với công thức rút gọn cho số nguyên tố \(\varphi(p) = p-1\).
Ví dụ 2: lũy thừa của một số nguyên tố, φ(32)
Phân tích thừa số: \(32 = 2^5\). Số nguyên tố khác nhau duy nhất là 2.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
Dạng tương đương cho lũy thừa của số nguyên tố: \(\varphi(p^k) = p^k - p^{k-1}\), do đó \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). Đây chính xác là các số lẻ từ 1 đến 31.
Ví dụ 3: ba số nguyên tố khác nhau trở lên, φ(210)
Phân tích thừa số: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- Bắt đầu với \(210\).
- Nhân với \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
- Nhân với \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
- Nhân với \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
- Nhân với \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).
Vậy \(\varphi(210) = \)48. Lưu ý rằng quy tắc tích chỉ dùng mỗi số nguyên tố khác nhau một lần. Ví dụ, \(60 = 2^2 \cdot 3 \cdot 5\) cho \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).
Diễn giải φ(n) và các ứng dụng
- Liên hệ với tính nguyên tố: với \(n \ge 2\), \(\varphi(n) = n-1\) khi và chỉ khi \(n\) là số nguyên tố. Mọi số nhỏ hơn một số nguyên tố đều nguyên tố cùng nhau với nó. Nếu \(n\) là hợp số, ít nhất một số nhỏ hơn nó có chung thừa số với \(n\), nên \(\varphi(n) < n-1\).
- Nhóm các phần tử khả nghịch: \(\varphi(n)\) là số phần tử của nhóm các phần tử khả nghịch modulo \(n\), tức là các thặng dư có nghịch đảo nhân theo modulo \(n\). Với \(n = 15\), đó là các số 1, 2, 4, 7, 8, 11, 13, 14, tức là 8 phần tử.
- Định lý Euler: nếu \(\gcd(a, n) = 1\), thì \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Ví dụ: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, và \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Định lý Fermat nhỏ là trường hợp đặc biệt khi \(n = p\) là số nguyên tố.
- RSA: khi \(n = pq\) với hai số nguyên tố khác nhau \(p\) và \(q\), \(\varphi(n) = (p-1)(q-1)\). Với \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). Số mũ công khai \(e\) phải nguyên tố cùng nhau với \(\varphi(n)\), và số mũ bí mật \(d\) thỏa mãn \(ed \equiv 1 \pmod{\varphi(n)}\). RSA thực tế dùng các số nguyên tố dài hàng trăm chữ số. Ai có thể phân tích \(n\) thành thừa số thì có thể tính \(\varphi(n)\), và đó là lý do bảo mật dựa trên việc phân tích thừa số là khó.
- Tỉ số chỉ phụ thuộc vào các số nguyên tố khác nhau: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Số mũ không ảnh hưởng. Ví dụ, 6 và 12 có cùng tập số nguyên tố {2, 3}, nên \(\varphi(6)/6 = 2/6 = 1/3\) và \(\varphi(12)/12 = 4/12 = 1/3\).
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.