Phi Hàm Euler và Ứng Dụng Trong Đồng Dư Số Học
Trong lý thuyết số học và mật mã học hiện đại, Phi hàm Euler (kí hiệu là \(\phi(n)\) hay Euler's Totient Function) giữ một vị trí trung tâm vô cùng quan trọng. Hàm số này được nhà toán học vĩ đại Leonhard Euler giới thiệu vào thế kỷ 18, định nghĩa số lượng các số nguyên dương nằm trong đoạn từ \(1\) đến \(n\) nguyên tố cùng nhau với \(n\) (nghĩa là có ước chung lớn nhất \(\gcd(x, n) = 1\)).
Đối với các lập trình viên thi đấu, phi hàm Euler không chỉ là một bài toán đếm đơn thuần mà còn là chìa khóa để giải quyết bài toán tính lũy thừa siêu lớn \(A^B \pmod M\) khi số mũ \(B\) vượt quá giới hạn \(10^{18}\) hoặc khi modulo \(M\) là một hợp số bất kỳ. Định lý Euler đóng vai trò như chiếc chìa khóa vàng giúp thu gọn số mũ về một phạm vi tính toán an toàn.
Bài viết này sẽ trình bày trọn vẹn lý thuyết toán học đằng sau phi hàm Euler, chứng minh công thức tích Euler, so sánh thuật toán tính đơn lẻ trong \(O(\sqrt{N})\) với thuật toán sàng phi hàm trong \(O(N \log \log N)\), đồng thời minh họa cách ứng dụng định lý Euler để giải quyết các bài toán lũy thừa tầng hóc búa.
1. Định nghĩa và Công thức tích Euler
Theo định nghĩa toán học: \[\phi(n) = \sum_{i=1}^n [\gcd(i, n) == 1]\]
Bảng giá trị của \(\phi(n)\) cho các số nguyên đầu tiên:
- \(\phi(1) = 1\) (số 1 nguyên tố cùng nhau với chính nó).
- \(\phi(2) = 1\) (chỉ có số 1).
- \(\phi(3) = 2\) (gồm \(\{1, 2\}\)).
- \(\phi(4) = 2\) (gồm \(\{1, 3\}\)).
- \(\phi(5) = 4\) (với mọi số nguyên tố \(p\), \(\phi(p) = p - 1\)).
- \(\phi(6) = 2\) (gồm \(\{1, 5\}\)).
Tính chất nhân tính (Multiplicative Function)
Phi hàm Euler là một hàm số nhân tính: nếu hai số \(a\) và \(b\) nguyên tố cùng nhau (\(\gcd(a, b) = 1\)) thì: \[\phi(a \cdot b) = \phi(a) \cdot \phi(b)\]
Công thức với lũy thừa số nguyên tố
Nếu \(p\) là một số nguyên tố và \(k \ge 1\): Trong đoạn \([1, p^k]\), các số không nguyên tố cùng nhau với \(p^k\) bắt buộc phải là bội số của \(p\). Các bội số đó là: \(1p, 2p, 3p, \dots, p^{k-1}p\). Có đúng \(p^{k-1}\) bội số như vậy. Do đó: \[\phi(p^k) = p^k - p^{k-1} = p^k \left( 1 - \frac{1}{p} \right)\]
Công thức tích tổng quát của Euler (Euler's Product Formula)
Xét số nguyên dương \(n\) có phân tích thừa số nguyên tố duy nhất: \[n = p_1^{a_1} \cdot p_2^{a_2} \dots p_k^{a_k}\] Áp dụng tính chất nhân tính: \[\phi(n) = \prod_{i=1}^k \phi(p_i^{a_i}) = \prod_{i=1}^k p_i^{a_i} \left( 1 - \frac{1}{p_i} \right)\] Vì \(\prod_{i=1}^k p_i^{a_i} = n\) nên: \[\phi(n) = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right)\]
Ví dụ: Tính \(\phi(36)\): \(36 = 2^2 \times 3^2\). Các thừa số nguyên tố phân biệt là 2 và 3. \[\phi(36) = 36 \times \left( 1 - \frac{1}{2} \right) \times \left( 1 - \frac{1}{3} \right)\] tức là \(\phi(36) = 36 \times \frac{1}{2} \times \frac{2}{3} = 12\). Tập 12 số nguyên tố cùng nhau với 36 nhỏ hơn 36 là: \(\{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\}\).
2. Các thuật toán tính Phi hàm Euler trong lập trình
Tùy vào bối cảnh bài toán, chúng ta lựa chọn thuật toán phù hợp:
Thuật toán 1: Tính phi(N) cho một số đơn lẻ trong O(sqrt(N))
Dựa trực tiếp vào công thức tích Euler: ta duyệt tìm các ước số nguyên tố \(p\) từ \(2\) đến \(\sqrt{N}\). Mỗi khi tìm thấy một ước \(p\), ta trừ bớt \(res / p\) và chia triệt tiêu \(p\) khỏi \(N\):
long long phi(long long n) {
long long res = n;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
Thuật toán 2: Sàng Phi hàm Euler từ 1 đến M trong O(M log log M)
Khi cần trả lời nhiều truy vấn hoặc cần tính tổng phi hàm trên một đoạn lớn \(M = 10^6\), ta sử dụng kỹ thuật sàng tương tự sàng nguyên tố Eratosthenes:
- Khởi tạo mảng
phi[i] = ivới mọi \(i\). - Với mỗi số nguyên tố \(p\), duyệt qua mọi bội số \(j\) của \(p\) (\(j = p, 2p, 3p, \dots\)) và cập nhật: \[phi[j] -= phi[j] / p\]
vector<int> sieve_phi(int n) {
vector<int> phi_arr(n + 1);
for (int i = 0; i <= n; ++i) phi_arr[i] = i;
for (int p = 2; p <= n; ++p) {
if (phi_arr[p] == p) { // p la so nguyen to
for (int i = p; i <= n; i += p) {
phi_arr[i] -= phi_arr[i] / p;
}
}
}
return phi_arr;
}
3. Cài đặt C++17 và Python 3 chuẩn thi đấu
Dưới đây là mã nguồn hoàn chỉnh kết hợp cả hai phương pháp:
Cài đặt C++17
#include <iostream>
#include <vector>
using namespace std;
// Tinh phi(n) trong O(sqrt(n)) bang phan tich thua so nguyen to
long long phi(long long n) {
long long res = n;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
// Sang phi ham Euler tu 1 den n trong O(n log log n)
vector<int> sieve_phi(int n) {
vector<int> phi_arr(n + 1);
for (int i = 0; i <= n; ++i) phi_arr[i] = i;
for (int p = 2; p <= n; ++p) {
if (phi_arr[p] == p) { // p la so nguyen to
for (int i = p; i <= n; i += p) {
phi_arr[i] -= phi_arr[i] / p;
}
}
}
return phi_arr;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Tinh phi(36) = 12
cout << phi(36) << '\n';
// Tinh phi(10^9+7) = 10^9+6 (so nguyen to)
cout << phi(1000000007LL) << '\n';
// Sang phi tu 1 den 12
auto arr = sieve_phi(12);
for (int i = 1; i <= 12; ++i) {
cout << arr[i] << (i == 12 ? '\n' : ' ');
}
return 0;
}
Cài đặt Python 3
import sys
def phi(n: int) -> int:
res = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
res -= res // p
p += 1
if n > 1:
res -= res // n
return res
def sieve_phi(n: int) -> list[int]:
phi_arr = list(range(n + 1))
for p in range(2, n + 1):
if phi_arr[p] == p:
for i in range(p, n + 1, p):
phi_arr[i] -= phi_arr[i] // p
return phi_arr
def main():
print(phi(36))
print(phi(1000000007))
arr = sieve_phi(12)
print(*(arr[1:13]))
if __name__ == '__main__':
main()
4. Ứng dụng đột phá: Định lý Euler và Rút gọn số mũ
Định lý Euler (Euler's Totient Theorem)
Nếu hai số nguyên \(a\) và \(m\) nguyên tố cùng nhau (\(\gcd(a, m) = 1\)), thì: \[a^{\phi(m)} \equiv 1 \pmod m\]
Hệ quả trực tiếp là khi tính \(a^b \pmod m\), ta có thể rút gọn số mũ \(b\) khổng lồ bằng phép chia lấy dư cho \(\phi(m)\): \[a^b \equiv a^{b \pmod{\phi(m)}} \pmod m\]
Định lý Euler mở rộng (Power Reduction khi không nguyên tố cùng nhau)
Nếu \(\gcd(a, m) > 1\), định lý Euler vẫn có dạng mở rộng cực kỳ hữu ích: \[a^b \equiv a^{(b \pmod{\phi(m)}) + \phi(m)} \pmod m\] với mọi \(b \ge \phi(m)\).
Công thức này là chìa khóa để giải quyết các bài toán Lũy thừa tầng (Power Towers): \[A^{B^{C^D}} \pmod M\] Ta đệ quy tính số mũ tầng trên theo modulo \(\phi(M)\), rồi lại đệ quy tiếp theo \(\phi(\phi(M))\), cho đến khi modulo giảm về 1 thì dừng lại!
Bảng chạy tay chi tiết thuật toán Sàng Phi hàm Euler
Để hiểu rõ cơ chế hoạt động của thuật toán sàng Phi hàm Euler trong đoạn \([1, 12]\), ta theo dõi cách các giá trị \(\phi(i)\) được biến đổi liên tục:
Ban đầu, khởi tạo mảng phi[i] = i với mọi \(i \in [1, 12]\).
| Bước duyệt số \(i\) | Loại số | Hành động cập nhật các bội số \(j = i, 2i, 3i, \dots\) | Trạng thái mảng phi sau bước duyệt |
|---|---|---|---|
| Khởi tạo | - | phi[i] = i |
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] |
| \(i = 2\) | Nguyên tố | Nhân \((1 - 1/2) = 1/2\) cho \(j \in \{2, 4, 6, 8, 10, 12\}\) | [0, 1, 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6] |
| \(i = 3\) | Nguyên tố | Nhân \((1 - 1/3) = 2/3\) cho \(j \in \{3, 6, 9, 12\}\) | [0, 1, 1, 2, 2, 5, 2, 7, 4, 6, 5, 11, 4] |
| \(i = 4\) | Hợp số | Bỏ qua (vì phi[4] = 2 != 4, đã được số 2 cập nhật) |
Giữ nguyên |
| \(i = 5\) | Nguyên tố | Nhân \((1 - 1/5) = 4/5\) cho \(j \in \{5, 10\}\) | [0, 1, 1, 2, 2, 4, 2, 7, 4, 6, 4, 11, 4] |
| \(i = 7\) | Nguyên tố | Nhân \((1 - 1/7) = 6/7\) cho \(j \in \{7\}\) | [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 11, 4] |
| \(i = 11\) | Nguyên tố | Nhân \((1 - 1/11) = 10/11\) cho \(j \in \{11\}\) | [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4] |
Kết quả thu được: \(\phi(12) = 4\) (các số nguyên tố cùng nhau với 12 là \(\{1, 5, 7, 11\}\)), \(\phi(10) = 4\) (\(\{1, 3, 7, 9\}\)), \(\phi(9) = 6\). Toàn bộ mảng từ 1 đến 12 đều chính xác tuyệt đối.
Bốn ứng dụng và lưu ý sống còn trong lập trình thi đấu
-
Thuật toán tính lũy thừa tầng (Power Tower): Khi tính \(A^{B^C} \pmod M\), ta không thể lấy \(B^C \pmod M\). Theo định lý Euler mở rộng, số mũ ở tầng trên phải được chia lấy dư cho \(\phi(M)\): \[A^X \equiv A^{(X \bmod \phi(M)) + \phi(M)} \pmod M\] với \(X \ge \phi(M)\). Kỹ thuật đệ quy giảm số mũ bằng phi hàm Euler là cách giải tiêu chuẩn cho bài toán lũy thừa tầng trong các kỳ thi Olympic.
-
Đẳng thức Gauss và bài toán đếm phân số: Đẳng thức \(\sum_{d | n} \phi(d) = n\) là nền tảng để đếm số phân số tối giản trong đoạn \([0, 1]\) có mẫu số không vượt quá \(N\), còn được biết đến với tên gọi Dãy Farey bậc \(N\). Độ dài dãy Farey chính là \(1 + \sum_{i=1}^N \phi(i)\).
-
Tránh chia số thực gây sai số: Khi cài đặt công thức \(\phi(n) = n \cdot (1 - 1/p)\), không bao giờ dùng phép chia số thực
ans *= (1.0 - 1.0 / p). Luôn tính bằng phép toán số nguyên:ans -= ans / p. Cách viết này vừa tránh sai số dấu phẩy động (precision error), vừa chạy nhanh hơn. -
Xử lý số nguyên tố lớn hơn căn bậc hai: Sau khi đã chia hết cho mọi ước nguyên tố nhỏ hơn hoặc bằng \(\sqrt{N}\), nếu giá trị \(N\) còn lại vẫn lớn hơn 1, thì phần còn lại chắc chắn là một số nguyên tố cuối cùng. Cần cập nhật
ans -= ans / nmột lần nữa trước khi trả về kết quả.
Luyện ngay trên Big-O Coding
Để nắm vững cách ứng dụng phi hàm Euler vào các bài toán số học chuyên sâu, bạn hãy luyện tập ngay các bài tập sau:
Đẳng thức Gauss tổng các phi(d) với d chia hết n có ý nghĩa gì?
Đẳng thức này phát biểu rằng tổng giá trị phi hàm Euler của tất cả các ước số nguyên dương của \(n\) đúng bằng \(n\). Ý nghĩa trực quan của nó là phân hoạch tập các phân số \(\{\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}\}\) về dạng tối giản \(\frac{a}{d}\) với \(\gcd(a, d) = 1\). Số lượng phân số có mẫu số tối giản \(d\) đúng bằng \(\phi(d)\), và tổng số lượng mọi phân số bằng \(n\).
Sàng phi hàm Euler tuyến tính O(N) có nhanh hơn sàng O(N log log N) không?
Sàng tuyến tính sử dụng mảng ước nguyên tố nhỏ nhất (Linear Sieve) chỉ duyệt qua mỗi hợp số đúng một lần, đạt độ phức tạp chính xác \(O(N)\). Mặc dù về lý thuyết nhanh hơn, nhưng sàng \(O(N \log \log N)\) trình bày ở trên có bộ nhớ gọn hơn, dễ nhớ và tuy chậm hơn sàng tuyến tính khoảng 3 lần nhưng vẫn đủ nhanh cho các bài thi \(N \le 10^7\) (đo bằng g++ -O2 với \(N = 10^7\): khoảng 0.15 đến 0.2 giây, so với 0.05 đến 0.09 giây của sàng tuyến tính).
Nguồn tham khảo
- CP-Algorithms - Euler's totient function - Toàn văn lý thuyết và chứng minh toán học của phi hàm Euler
- VNOI Wiki - Phi hàm Euler - Chuyên đề số học đồng dư nâng cao cho học sinh chuyên Tin
- USACO Guide - Divisibility (Euler's Totient) - Các bài toán thực chiến áp dụng phi hàm Euler trong kỳ thi Olympic
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


