Penjelasan fungsi totient Euler
Tuliskan bilangan 1 sampai 10 dan coret setiap bilangan yang memiliki faktor persekutuan dengan 10. Tersisa empat: 1, 3, 7, dan 9. Jumlah itu, φ(10) = 4, adalah totient Euler, salah satu fungsi yang paling banyak dipakai dalam teori bilangan, dari pecahan dan jam hingga enkripsi yang melindungi pembayaran daring.
Menghitung bilangan relatif prima
Dua bilangan relatif prima bila faktor persekutuan terbesarnya 1. φ(n) menghitung k dari 1 sampai n dengan FPB(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4, dan φ(1) = 1. Jumlah yang sama muncul di banyak tempat. Itu adalah banyaknya pecahan k/n antara 0 dan 1 yang sudah paling sederhana, banyaknya panjang langkah yang membawa jarum melewati setiap jam pada jam dengan n jam, dan banyaknya k yang memiliki invers modulo n, sehingga k × x ≡ 1 (mod n) dapat diselesaikan.
Rumus perkalian
Jika bilangan prima yang membagi n adalah p₁, p₂ …, maka φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Alasannya adalah sebuah saringan. Separuh dari semua bilangan genap, jadi membuang kelipatan 2 menyisakan bagian 1 − 1/2; dari bilangan yang tersisa, satu dari tiga adalah kelipatan 3, dan seterusnya. Menurut teorema sisa Tiongkok, syarat untuk bilangan prima yang berbeda saling bebas, sehingga bagian-bagiannya cukup dikalikan. Untuk 100 = 2² × 5² hasilnya 100 × 1/2 × 4/5 = 40. Dua sifat memberikan hasil yang sama dalam bentuk lain: φ(p^k) = p^(k−1)(p − 1), dan φ(mn) = φ(m) φ(n) bila m dan n relatif prima, jadi φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Teorema Euler
Fermat memperhatikan pada 1640 bahwa a^(p−1) ≡ 1 (mod p) untuk bilangan prima p dan setiap a yang tidak habis dibagi p. Euler membuktikan versi umumnya, yang diterbitkan pada 1763: a^φ(n) ≡ 1 (mod n) setiap kali FPB(a, n) = 1. Buktinya singkat. Kalikan φ(n) bilangan yang relatif prima terhadap n dengan a; hasil kalinya kembali relatif prima terhadap n dan semuanya berbeda modulo n, jadi itu adalah bilangan yang sama dalam urutan lain, dan membandingkan kedua hasil kali menyisakan a^φ(n) ≡ 1. Eksponen terkecil yang berlaku untuk a tertentu adalah ordenya, yang selalu membagi φ(n); yang terkecil yang berlaku untuk semua a sekaligus adalah fungsi Carmichael λ(n). Untuk 561 = 3 × 11 × 17, λ(561) = 80 membagi 560, sehingga a^560 ≡ 1 (mod 561) untuk setiap a yang relatif prima terhadap 561 walaupun 561 bukan bilangan prima. Itulah bilangan Carmichael terkecil, dan alasan mengapa uji Fermat saja tidak dapat membuktikan bahwa suatu bilangan prima.
Jumlah pembagi Gauss dan rata-ratanya
Jumlahkan φ(d) atas pembagi d dari n dan Anda selalu mendapatkan n kembali: untuk 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss membuktikannya dalam Disquisitiones Arithmeticae tahun 1801; hal ini terlihat bila pecahan 1/12, 2/12 … 12/12 disederhanakan lalu dikelompokkan menurut penyebutnya. Rata-rata φ(k) sekitar 0,61 k: rata-rata φ(k)/k mendekati 6/π² ≈ 0,6079, yang juga merupakan peluang dua bilangan bulat acak relatif prima, dan φ(1) + … + φ(N) mendekati 3N²/π². Untuk N = 1.000 jumlahnya 304.192, dibandingkan 3N²/π² ≈ 303.964.
Nilai yang tidak pernah muncul
φ(n) genap untuk setiap n mulai dari 3, karena bilangan yang relatif prima terhadap n datang berpasangan k dan n − k. Tidak setiap bilangan genap pula merupakan nilai: 14, 26, 34, 38, dan 50 adalah yang pertama yang tidak pernah muncul, sedangkan 24 adalah nilai dari sepuluh bilangan berbeda, dari 35 sampai 90. Menemukannya adalah pencarian berhingga, karena untuk setiap bilangan prima p yang membagi n, p − 1 harus membagi φ(n). Pada 1907 Robert Carmichael menyatakan bahwa tidak ada nilai yang muncul tepat satu kali. Buktinya keliru, pernyataan itu masih terbuka, dan pengecualian mana pun harus lebih besar dari 10^(10^10). D. H. Lehmer bertanya pada 1932 apakah φ(n) dapat membagi n − 1 untuk n komposit; belum ada contoh yang diketahui.
Totient dalam RSA
RSA memilih dua bilangan prima besar p dan q lalu memublikasikan n = pq dan sebuah eksponen e. Karena φ(n) = (p − 1)(q − 1), siapa pun yang dapat memfaktorkan n dapat menghitung φ(n), dan dari situ eksponen privat d dengan e × d ≡ 1 (mod φ(n)); teorema Euler kemudian menjamin bahwa (m^e)^d ≡ m (mod n). Dalam contoh buku teks n = 3233 = 61 × 53, φ(n) = 3.120, e = 17, dan d = 2.753. Banyak implementasi memakai λ(n) = KPK(p − 1, q − 1) sebagai gantinya, di sini 780, yang memberikan d lebih kecil, yaitu 413. Menghitung φ(n) untuk modulus RSA 600 digit sama sulitnya dengan memfaktorkannya: dari n dan φ(n), kedua bilangan prima diperoleh dengan satu akar kuadrat.
Jelajahi sendiri
Buka kalkulator dan masukkan n berapa pun hingga 10^18 untuk melihat φ(n) beserta faktor prima dan rumusnya. Hingga 500, bilangan 1 sampai n digambar, yang relatif prima diisi penuh dan yang lain diwarnai menurut bilangan prima terkecil yang mereka miliki bersama n, sehingga rumus perkalian menjadi saringan yang bisa dihitung. Pilih bilangan a untuk memeriksa teorema Euler, beralih ke Grafik untuk melihat φ(k) hingga 100.000 dengan bilangan prima pada garis φ(p) = p − 1, atau ke Invers untuk menemukan setiap n dengan φ(n) = m.
Pertanyaan yang sering diajukan
Mengapa φ(1) = 1?
Karena FPB(1, 1) = 1: satu-satunya bilangan dari 1 sampai 1 relatif prima terhadap 1. Kesepakatan ini juga membuat rumus-rumus tetap berlaku, misalnya jumlah Gauss atas pembagi n, yang untuk n = 1 hanyalah φ(1) = 1.
Apakah φ sama dengan fungsi pencacah bilangan prima?
Tidak. π(n) menghitung bilangan prima hingga n, φ(n) menghitung bilangan hingga n yang relatif prima terhadap n. φ(10) = 4 menghitung 1, 3, 7, dan 9, sedangkan π(10) = 4 menghitung 2, 3, 5, dan 7. Keduanya sama di sini hanya kebetulan: φ(12) = 4, tetapi π(12) = 5.
Seberapa cepat φ(n) dapat dihitung?
Secepat n dapat difaktorkan. Dengan faktor prima yang diketahui, cukup beberapa perkalian; tanpanya tidak ada metode cepat yang diketahui, dan di situlah RSA bertumpu. Untuk bilangan hingga 10^18, pemfaktoran butuh beberapa milidetik di peramban; untuk bilangan dengan ratusan digit, bisa butuh bertahun-tahun.
Bilangan mana yang φ(n)-nya paling kecil dibandingkan n?
Bilangan dengan banyak faktor prima kecil. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… hanya bergantung pada bilangan prima mana yang membagi n, bukan pada pangkatnya: untuk setiap perpangkatan 2 nilainya tepat 1/2, dan untuk 30 = 2 × 3 × 5 nilainya 8/30, sekitar 27%. Hasil kali 15 bilangan prima pertama, 614.889.782.588.491.410, memiliki φ(n)/n ≈ 14%, nilai terendah dari semua bilangan hingga 10^18.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Buka kalkulator totient