Fungsi total Euler, ditulis φ(n), menghitung berapa banyak bilangan bulat positif hingga n yang tidak mempunyai faktor persekutuan dengan n. Ini tampak seperti latihan penghitungan sederhana, tetapi ini mendasari aritmatika modular, generalisasi teorema kecil Fermat oleh Euler, dan langkah pembuatan kunci kriptografi RSA. Kalkulator ini menghitung φ(n) melalui faktorisasi prima, menunjukkan penurunan langkah demi langkah, dan — untuk n kecil — mencantumkan setiap bilangan bulat koprima secara langsung.
Berapa φ(n) yang sebenarnya penting
φ(n) menghitung bilangan bulat positif k dalam rentang 1 ≤ k ≤ n yang mana gcd(k, n) = 1 — yaitu, k dan n adalah koprima. Untuk n = 1, φ(1) = 1 berdasarkan konvensi. Untuk bilangan prima p, setiap bilangan bulat di bawahnya otomatis koprima, jadi φ(p) = p − 1. Tab Daftar Koprime kalkulator ini mencantumkan bilangan bulat ini secara langsung setiap kali n cukup kecil (hingga 2.000) untuk menampilkan semuanya.
Bagaimana faktorisasi prima memberikan rumusnya
Cara tercepat untuk menghitung φ(n) untuk n yang besar bukanlah dengan memeriksa koprimalitas setiap bilangan bulat — melainkan dengan memfaktorkan prima n terlebih dahulu. Total Euler adalah fungsi perkalian, artinya φ(mn) = φ(m)φ(n) setiap kali gcd(m, n) = 1. Dikombinasikan dengan fakta bahwa φ(p^k) = p^k − p^(k-1) = p^k(1 − 1/p) untuk pangkat prima apa pun, maka diperoleh rumus umum φ(n) = n·Π(1 − 1/p) pada setiap faktor prima berbeda p dari n — eksponennya sendiri tidak dimasukkan dalam rumus seluruhnya. Tab Faktorisasi Prima kalkulator ini menunjukkan dengan tepat derivasi ini, suku demi suku, untuk berapa pun n yang Anda masukkan.
Mengapa kriptografi peduli dengan φ(n)
Enkripsi RSA menghasilkan pasangan kunci publik/pribadi dari dua bilangan prima besar p dan q yang berbeda, sehingga n = pq menjadi modulus publik. Eksponen hasil bagi diturunkan menggunakan φ(n) = (p−1)(q−1) — rumus yang sama yang disorot oleh garis interpretasi kalkulator ini setiap kali n faktor menjadi dua bilangan prima yang berbeda. Dalam implementasi RSA nyata p dan q panjangnya ratusan digit, namun perhitungan total yang mendasarinya identik dengan yang ditunjukkan di sini untuk contoh kecil. Alat terkait seperti Kalkulator Faktorisasi Prima dan Kalkulator Modulo berguna untuk menjelajahi landasan teori bilangan lain di balik aritmatika modular dan kriptografi.