 |
| Materi Matematika SMA |
Apa itu Fungsi Totient Euler?
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@$
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 Euler’s Totient Function
- @$\phi(1)=1@$
- 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@$
- 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.
Source: https://aryasaktiwirasena.web.ugm.ac.id/2021/01/10/fungsi-totient-euler-eulers-totient-function/
0 Komentar