Fungsi Totient Euler (Euler’s Totient Function)

, , Leave a comment

Fungsi Totient Euler adalah sebuah fungsi untuk mencari banyaknya bilangan asli yang kurang dari sama dengan n yang relatif prima terhadap n. Dua bilangan disebut “relatif prima” jika FPB (Faktor persekutuan terbesar) kedua bilangan tersebut sama dengan 1. Fungsi ini biasa dinotasikan dengan simbol \phi(), dibaca “fi”. Sebagai contoh, ada 4 buah bilangan yang relatif prima terhadap 8, yaitu 1, 3, 5, dan 7. Maka \phi(8)=4

Formula

Misalkan x adalah sebuah bilangan bulat positif, dan kita faktorisasikan sehingga x=p_1^{a_1}p_2^{a_2}p_3^{a_3} \ldots p_n^{a_n} maka formulanya adalah sebagai berikut

\phi(x)=x \prod_{i=1}^{n} (1-\frac{1}{p_i})

Sebagai contoh, 20=2^2\cdot5 maka p_1=2, p_2=5, sehingga

\phi(20)=20(1-\frac{1}{2})(1-\frac{1}{5})

\phi(20)=20(\frac{1}{2})(\frac{4}{5})

\phi(20)=8

Sifat-sifat

  1. \phi(1)=1
  2. Untuk setiap bilangan prima p dan bilangan bulat k \ge 1, \phi(p^k)=p^k-p^{k-1}※ Untuk kasus k=1, sifat di atas menjadi \phi(p)=p-1
  3. Jika FPB(m,n)=1, maka \phi(mn)=\phi(m)\cdot\phi(n)

Sebagai alternatif dari formula umum, kita dapat menghitung nilai \phi(x) dengan sifat-sifat di atas. Contohnya kita coba hitung \phi(20) lagi dengan sifat-sifat saja:

Pertama, menggunakan sifat 3, kita pecah \phi(20) menjadi beberapa fungsi sesuai dengan faktorisasi prima dari 20:

\phi(20)=\phi(2^2)\phi(5)

Kemudian nilai \phi(2^2) dan \phi(5) kita evaluasi dengan sifat 2:

\phi(20)=(2^2-2)(5-1)

\phi(20)=2\cdot4

\phi(20)=8

Nilai-nilai \phi(x) untuk beberapa nilai x pertama dapat dilihat di OEIS A000010. OEIS adalah sebuah pustaka web berisi barisan-barisan bilangan yang penting dan kerap muncul dalam matematika.

Aplikasi

Aplikasi fungsi totient Euler ada dalam ilmu kriptografi, dimana algoritma RSA menggunakannya untuk menentukan private key. Bacaan lebih lanjut terdapat pada pranala yang tertera.

Selain itu, di ranah matematika yang lebih murni, fungsi ini menghitung banyak generator sebuah grup siklis bilangan bulat modulo n. Fungsi ini adalah kunci dari Teorema Euler, yang merupakan generalisasi dari Teorema Kecil Fermat,dan digeneralisasi lagi lebih jauh menjadi Teorema Carmichael. Ketiga teorema ini akan menjadi bahasan untuk artikel minggu depan.

 

 

Leave a Reply