Giải thích hàm phi Euler
Hãy viết các số từ 1 đến 10 và gạch bỏ mọi số có ước chung với 10. Còn lại bốn số: 1, 3, 7 và 9. Con số đó, φ(10) = 4, chính là hàm phi Euler, một trong những hàm được dùng nhiều nhất trong lý thuyết số, từ phân số và đồng hồ đến mã hóa bảo vệ các giao dịch thanh toán trực tuyến.
Đếm các số nguyên tố cùng nhau
Hai số nguyên tố cùng nhau khi ước chung lớn nhất của chúng bằng 1. φ(n) đếm các k từ 1 đến n có ƯCLN(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 và φ(1) = 1. Cùng con số đó xuất hiện ở nhiều nơi. Đó là số phân số k/n giữa 0 và 1 đã tối giản, số bước nhảy đưa kim đi qua mọi giờ trên một mặt đồng hồ n giờ, và số các k có nghịch đảo theo mô-đun n, để phương trình k × x ≡ 1 (mod n) có nghiệm.
Công thức tích
Nếu các số nguyên tố chia hết n là p₁, p₂ …, thì φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Lý do là một cái sàng. Một nửa tất cả các số là số chẵn, nên bỏ đi các bội của 2 còn lại phần 1 − 1/2; trong các số còn lại, cứ ba số có một số là bội của 3, và cứ thế tiếp tục. Theo định lý số dư Trung Hoa, các điều kiện cho các số nguyên tố khác nhau là độc lập, nên các phần đơn giản được nhân với nhau. Với 100 = 2² × 5², ta được 100 × 1/2 × 4/5 = 40. Hai tính chất cho cùng kết quả dưới dạng khác: φ(p^k) = p^(k−1)(p − 1), và φ(mn) = φ(m) φ(n) khi m và n nguyên tố cùng nhau, nên φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Định lý Euler
Fermat nhận thấy năm 1640 rằng a^(p−1) ≡ 1 (mod p) với số nguyên tố p và mọi a không chia hết cho p. Euler chứng minh dạng tổng quát, công bố năm 1763: a^φ(n) ≡ 1 (mod n) mỗi khi ƯCLN(a, n) = 1. Chứng minh rất ngắn. Nhân φ(n) số nguyên tố cùng nhau với n với a; các tích lại nguyên tố cùng nhau với n và đôi một khác nhau theo mô-đun n, nên chúng là cùng các số đó theo thứ tự khác, và so sánh hai tích thì còn lại a^φ(n) ≡ 1. Số mũ nhỏ nhất đúng với một a cho trước là cấp của nó, luôn chia hết φ(n); số mũ nhỏ nhất đúng với mọi a cùng lúc là hàm Carmichael λ(n). Với 561 = 3 × 11 × 17, λ(561) = 80 chia hết 560, nên a^560 ≡ 1 (mod 561) với mọi a nguyên tố cùng nhau với 561, dù 561 không phải số nguyên tố. Đó là số Carmichael nhỏ nhất, và là lý do phép thử Fermat một mình không thể chứng minh một số là số nguyên tố.
Tổng theo ước của Gauss và giá trị trung bình
Cộng φ(d) trên các ước d của n và bạn luôn nhận lại n: với 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss chứng minh điều này trong Disquisitiones Arithmeticae năm 1801; có thể thấy điều đó khi rút gọn các phân số 1/12, 2/12 … 12/12 rồi xếp chúng theo mẫu số. Trung bình φ(k) vào khoảng 0,61 k: trung bình của φ(k)/k tiến tới 6/π² ≈ 0,6079, cũng là xác suất để hai số nguyên chọn ngẫu nhiên nguyên tố cùng nhau, và φ(1) + … + φ(N) gần với 3N²/π². Với N = 1.000, tổng là 304.192, so với 3N²/π² ≈ 303.964.
Những giá trị không bao giờ xuất hiện
φ(n) là số chẵn với mọi n từ 3 trở đi, vì các số nguyên tố cùng nhau với n đi thành cặp k và n − k. Cũng không phải số chẵn nào cũng là một giá trị: 14, 26, 34, 38 và 50 là những số đầu tiên không bao giờ xuất hiện, trong khi 24 là giá trị của mười số khác nhau, từ 35 đến 90. Tìm chúng là một phép tìm kiếm hữu hạn, vì với mỗi số nguyên tố p chia hết n, p − 1 phải chia hết φ(n). Năm 1907, Robert Carmichael khẳng định rằng không có giá trị nào xuất hiện đúng một lần. Chứng minh của ông sai, khẳng định đó vẫn còn bỏ ngỏ, và bất kỳ ngoại lệ nào cũng phải lớn hơn 10^(10^10). D. H. Lehmer hỏi năm 1932 liệu φ(n) có thể chia hết n − 1 với một hợp số n hay không; chưa có ví dụ nào được biết.
Hàm phi trong RSA
RSA chọn hai số nguyên tố lớn p và q rồi công bố n = pq và một số mũ e. Vì φ(n) = (p − 1)(q − 1), ai phân tích được n thì tính được φ(n), và từ đó số mũ bí mật d với e × d ≡ 1 (mod φ(n)); định lý Euler sau đó bảo đảm rằng (m^e)^d ≡ m (mod n). Trong ví dụ sách giáo khoa n = 3233 = 61 × 53, φ(n) = 3.120, e = 17 và d = 2.753. Nhiều bản cài đặt dùng λ(n) = BCNN(p − 1, q − 1) thay thế, ở đây là 780, cho ra d nhỏ hơn là 413. Tính φ(n) cho một môđun RSA 600 chữ số cũng khó như phân tích nó: từ n và φ(n), hai số nguyên tố được suy ra chỉ với một phép khai căn bậc hai.
Tự khám phá
Mở máy tính và nhập bất kỳ n nào đến 10^18 để xem φ(n) cùng các thừa số nguyên tố và công thức. Đến 500, các số từ 1 đến n được vẽ ra, những số nguyên tố cùng nhau được tô đặc và các số khác được tô theo số nguyên tố nhỏ nhất mà chúng có chung với n, nên công thức tích trở thành một cái sàng có thể đếm được. Chọn một số a để kiểm tra định lý Euler, chuyển sang Đồ thị để xem φ(k) đến 100.000 với các số nguyên tố nằm trên đường thẳng φ(p) = p − 1, hoặc sang Ngược để tìm mọi n có φ(n) = m.
Câu hỏi thường gặp
Vì sao φ(1) = 1?
Vì ƯCLN(1, 1) = 1: số duy nhất từ 1 đến 1 nguyên tố cùng nhau với 1. Quy ước này cũng giữ cho các công thức đúng, chẳng hạn tổng Gauss theo các ước của n, mà với n = 1 chỉ là φ(1) = 1.
φ có giống hàm đếm số nguyên tố không?
Không. π(n) đếm các số nguyên tố đến n, còn φ(n) đếm các số đến n nguyên tố cùng nhau với n. φ(10) = 4 đếm 1, 3, 7 và 9, trong khi π(10) = 4 đếm 2, 3, 5 và 7. Chúng bằng nhau ở đây chỉ là trùng hợp: φ(12) = 4, nhưng π(12) = 5.
φ(n) có thể tính nhanh đến đâu?
Nhanh bằng tốc độ phân tích n ra thừa số. Khi đã biết các thừa số nguyên tố thì chỉ cần vài phép nhân; nếu không thì chưa có phương pháp nhanh nào được biết, và RSA dựa đúng vào điều đó. Với các số đến 10^18, việc phân tích trong trình duyệt mất vài mili giây; với các số hàng trăm chữ số, nó có thể mất nhiều năm.
Những số nào có φ(n) nhỏ nhất so với n?
Những số có nhiều thừa số nguyên tố nhỏ. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… chỉ phụ thuộc vào những số nguyên tố nào chia hết n, không phụ thuộc vào số mũ của chúng: với mọi lũy thừa của 2 nó đúng bằng 1/2, và với 30 = 2 × 3 × 5 nó bằng 8/30, khoảng 27%. Tích của 15 số nguyên tố đầu tiên, 614.889.782.588.491.410, có φ(n)/n ≈ 14%, thấp nhất trong mọi số đến 10^18.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở máy tính hàm phi