φ(n)
Thừa số nguyên tố
Tỉ lệ nguyên tố cùng nhau
Số ước

          Hiển thị

          Tìm hiểu thêm về hàm phi Euler

          Máy tính hàm phi Euler

          Trong các số từ 1 đến 12, chỉ có 1, 5, 7 và 11 không có ước chung nào với 12, nên φ(12) = 4. Hàm phi Euler đếm những số nguyên tố cùng nhau như vậy với mọi n. Nhập một số đến 10^18 để có φ(n) cùng các thừa số nguyên tố và công thức tích viết đầy đủ, xem các số từ 1 đến n với những số nguyên tố cùng nhau được làm nổi bật, kiểm tra định lý Euler, vẽ φ(k) cho tới 100.000 số cùng lúc, hoặc tìm mọi n có một giá trị φ(n) cho trước. Nhập một số nguyên n đến 10^18, hoặc chọn một ví dụ có lời giải. Các ô hiển thị φ(n), các thừa số nguyên tố của n, tỉ lệ các số từ 1 đến n nguyên tố cùng nhau với n và số ước, còn các bước viết ra công thức tích với các số của bạn. Đến n = 500, các số từ 1 đến n được vẽ ra: những số nguyên tố cùng nhau với n được tô đặc, các số còn lại mang màu của số nguyên tố nhỏ nhất mà chúng có chung với n. Trỏ vào một số để xem ƯCLN của nó với n, và nhấp vào để dùng nó làm a trong định lý Euler. Đồ thị cho thấy φ(k) với mọi k đến một giới hạn; nhấp vào một điểm để mở số đó. Ngược liệt kê mọi n có φ(n) = m; nhấp vào một số để mở nó.

          Cách nó hoạt động

          1. Nhập một số nguyên n đến 10^18, hoặc chọn một ví dụ có lời giải như φ(60), một môđun RSA hay số Carmichael 561.
          2. Đọc φ(n), các thừa số nguyên tố và công thức tích với các số của bạn. Đến 500, trỏ vào các số từ 1 đến n để xem ƯCLN của chúng với n, và nhấp vào một số để kiểm tra định lý Euler với số đó.
          3. Chuyển sang Đồ thị để xem φ(k) với mọi k đến 100.000, hoặc sang Ngược để liệt kê mọi n có φ(n) = m.

          Cách tính φ(n)

          Phân tích n ra thừa số nguyên tố và nhân n với (1 − 1/p) cho mỗi số nguyên tố p chia hết n. Với 60 = 2² × 3 × 5, ta được 60 × 1/2 × 2/3 × 4/5 = 16. Gạch bỏ cũng cho cùng kết quả: trong 60 số có 30 số chẵn; trong 30 số lẻ có 10 số là bội của 3; trong 20 số còn lại có 4 số là bội của 5, nên còn lại 16. Với lũy thừa của một số nguyên tố, công thức là φ(p^k) = p^(k−1)(p − 1), và các giá trị được nhân với nhau: φ(60) = 2 × 2 × 4. Phần khó là phân tích thừa số. Máy tính dùng phép chia thử, phép thử nguyên tố Miller–Rabin và phương pháp rho của Pollard, nên ngay cả tích 18 chữ số của hai số nguyên tố 9 chữ số cũng chỉ mất một phần nhỏ của giây.

          Hàm phi được dùng ở đâu

          φ(n) đếm các phân số k/n giữa 0 và 1 đã tối giản, các bước nhảy đưa kim đi qua mọi giờ trên một mặt đồng hồ n giờ (1, 5, 7 và 11 trên đồng hồ 12 giờ), và các số có nghịch đảo theo mô-đun n. Euler đã chứng minh rằng a^φ(n) ≡ 1 (mod n) với mọi a nguyên tố cùng nhau với n, và mã hóa RSA dựa trên điều đó: với n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3.120, và số mũ công khai 17 có cặp bí mật là 2.753, vì 17 × 2.753 = 15 × 3.120 + 1.

          Câu hỏi thường gặp

          Hàm phi Euler là gì?

          φ(n) là số các số nguyên từ 1 đến n không có ước chung nào với n ngoài 1. φ(9) = 6, vì 1, 2, 4, 5, 7 và 8 nguyên tố cùng nhau với 9, còn 3, 6 và 9 có chung thừa số 3. Theo quy ước, φ(1) = 1. Euler nghiên cứu hàm này vào những năm 1760; Gauss đặt cho nó ký hiệu φ năm 1801, và James Joseph Sylvester đặt tên tiếng Anh totient năm 1879.

          φ của một số nguyên tố bằng bao nhiêu?

          p − 1, vì mọi số từ 1 đến p − 1 đều nguyên tố cùng nhau với số nguyên tố p, nên φ(97) = 96. Với lũy thừa của một số nguyên tố, φ(p^k) = p^k − p^(k−1), vì chỉ các bội của p mới có ước chung với nó: φ(81) = 81 − 27 = 54.

          Định lý Euler nói gì?

          Nếu a và n nguyên tố cùng nhau thì a^φ(n) chia cho n dư 1. Với n = 60 và a = 7: φ(60) = 16, và 7^16 ≡ 1 (mod 60). Định lý nhỏ Fermat là trường hợp n nguyên tố. Thường thì một số mũ nhỏ hơn đã đủ: 7^4 = 2.401 = 40 × 60 + 1. Số mũ nhỏ nhất đúng với mọi a nguyên tố cùng nhau với n là hàm Carmichael λ(n), với 60 thì bằng 4.

          Hai số có thể có cùng giá trị phi không?

          Có, và thường là nhiều số: φ(n) = 24 với n = 35, 39, 45, 52, 56, 70, 72, 78, 84 và 90. Một số số chẵn không bao giờ là giá trị của φ, nhỏ nhất là 14, và không số lẻ nào lớn hơn 1 là giá trị của nó, vì φ(n) là số chẵn từ n = 3 trở đi. Robert Carmichael khẳng định năm 1907 rằng không có giá trị nào xuất hiện đúng một lần. Điều đó đến nay vẫn chưa được chứng minh, và Kevin Ford chỉ ra năm 1998 rằng một ngoại lệ phải lớn hơn 10^(10^10).

          Tôi có thể nhập số lớn đến mức nào?

          Bất kỳ số nguyên nào đến 10^18. Máy tính phân tích nó bằng số học số nguyên chính xác trong trình duyệt của bạn, nên φ(10^18) = 4 × 10^17 và φ(999.999.866.000.004.473) = 999.999.864.000.004.608 đúng đến chữ số cuối cùng. Các số từ 1 đến n được vẽ đến 500, đồ thị đến 100.000 và phép ngược dùng được cho các giá trị đến 10^10.

          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.

          Tới trình chỉnh sửa