Mengenal Euler Phi-Function

Euler Phi-Function sering disebut juga sebagai Euler totient function.

Dalam bahasa Indonesia, kita dapat menyebutnya dengan fungsi phi atau fungsi totient. Meskipun fungsi ini memiliki nama phi, namun fungsi ini dalam perhitungannya sama sekali tidak menggunakan phi () yang bernilai 1,61803399.. Sebaliknya, fungsi ini hanya memperhitungkan bilangan integer.

Alasan mengapa dinamakan fungsi phi adalah karena fungsi ini menggunakan lambang phi ().

Definisi phi function

Phi function adalah fungsi yang mengitung banyaknya integer untuk

yang memenuhi syarat:

dan koprima.

Note, dan dikatakan koprima jika .

Bilangan integer positif yang lebih kecil atau sama DAN relatif prima dengan suatu bilangan lain yang diberikan disebut bilangan totatif. Oleh karenanya, fungsi ini disebut juga sebagai fungsi totient.

=======================================================================

Untuk lebih jelasnya mengenai fungsi phi ini, maka sebaiknya kita gunakan contoh.

Contoh 1:
Sesuai definisi, maka

karena gcd(1,1) = 1.

Contoh 2:

Dari enam bilangan: 1, 2, 3, 4, 5, dan 6,
terdapat 2 bilangan yang koprima dengan 6 yaitu 1 dan 5.

Contoh 3:

Dari sembilan bilangan: 1, 2, 3, 4, 5, 6, 7, 8, dan 9,
terdapat 3 bilangan yang memiliki faktor dengan 9, yaitu 3, 6, dan 9
Jadi, terdapat 6 bilangan yang koprima dengan 9.

Contoh 4:

Dari dua belas bilangan: 1, 2, 3, ... , 11, 12,
terdapat 8 bilangan yang memiliki faktor dengan 12, yaitu 2, 3, 4, 6, 8, 9, 10, dan 12.
Jadi, terdapat 4 bilangan yang koprima dengan 12.
Dapat dikatakan juga: Banyaknya bilangan totatif dari 12 adalah 4.

Untuk bilangan-bilangan awal, kita dapat membuat tabelnya sbb:

Sekarang, kita akan membahas property unik dari .

Teorema 1

Untuk bilangan prima

Contoh 5:

Dari bilangan 1, 2, 3, ... , 13
terdapat 1 bilangan yang memiliki faktor dengan 13, yaitu 13.
Jadi, terdapat 12 bilangan yang koprima dengan 13.

Contoh 6:

Ingat bahwa 97 adalah bilangan prima.

Teorema 2

Untuk bilangan prima dan positif integer


atau dapat ditulis:

Contoh 7:

Dari bilangan 1, 2, 3, 4, ... , 121,
terdapat 11 bilangan yang memiliki faktor dengan 121, yaitu 11, 22, 33, 44, ... , 121.
Jadi, terdapat (121 - 11) = 110 bilangan yang koprima dengan 121.

Contoh 8:

Dari bilangan 1, 2, 3, 4, ... , 125,
terdapat 25 bilangan yang memiliki faktor dengan 125, yaitu 5, 10, 15, 20, ... , 125.
Jadi, terdapat (125 - 25) = 100 bilangan yang koprima dengan 125.

Teorema 3

Phi function adalah fungsi multiplikatif.

Untuk dan saling relatif prima (koprima), maka

ILUSTRASI BUKTI:
Anggap dan , maka . Kita akan mencacah bilangan 1, 2, 3, ... , 36 dalam suatu bagan seperti di bawah:

Bilangan yang diberi warna biru adalah bilangan yang koprima dengan 36.
Dari bagan di atas, kita tahu bahwa

BUKTI:
dapat digambarkan dalam bentuk seperti di bawah:

(Lihat kolom pertama)
Dari barisan 1, 2, 3, ... , , ... , , misalkan memiliki faktor dengan .
Kita tulis kembali baris ke-, yaitu:

Karena memiliki faktor dengan , maka semua elemen barisan di atas juga memiliki faktor dengan . Otomatis, semua elemen tersebut juga memiliki faktor dengan .

Karena kita ingin memperhitungkan bilangan yang koprima dengan , maka kita tinjau barisan yang koprima dengan .

----

Anggap dan koprima.
Kita tulis kembali baris sbb:

Karena dan koprima, maka semua elemen di baris tersebut merupakan sistem komplit residu modulo . (Lihat teorema di kotak biru di bawah). Oleh karenanya, di baris tersebut pasti terdapat bilangan yang koprima dengan .

Sistem komplit residu modulo adalah kumpulan integer yang tiap elemennya akan menghasilkan kelas sisa yang berbeda-beda jika dibagi oleh .
Contoh:

1, 2, 3, 4, 5 merupakan sistem komplit residu 5.

-1, 3, 7, 10, 16 merupakan sistem komplit residu 5.
Perhatikan bahwa:

-1 4 mod 5 ,__ 3 3 mod 5 ,__ 72 mod 5 ,__ 100 mod 5 ,__ 161 mod 5

Apakah (-10, 7, 18, 22, 30, 32, 46, 65) merupakan sistem komplit residu 9?
Jawab: bukan, karena jumlah elemennya hanya 8.

Apakah (-10, 7, 18, 22, 30, 32, 46, 65, 73) merupakan sistem komplit residu 9?
Jawab: bukan, karena dan . (kelas sisanya sama)

Teorema

Jika adalah sistem komplit residu modulo
dan jika adalah positif integer dimana ,
dan adalah integer, maka:

juga merupakan sistem komplit residu modulo

BUKTI:
Asumsikan bahwa ada dua elemen yang kongruen, maka:

(Lihat SINI) Karena , maka:

Namun, karena kita tahu bahwa adalah sistem komplit modulo, maka tidak mungkin ada kelas sisa yang sama antar dan .

Kontradiksi dengan asumsi awal, maka tidak ada dua elemen yang kongruen modulo . Dengan demikian, merupakan sistem komplit modulo . ■

Karena terdapat baris yang koprima terhadap DAN di setiap baris tersebut terdapat elemen yang koprima dengan , maka dapat disimpulkan bahwa:

TERBUKTI ■

Contoh 9:


Contoh 10:

Rumus Cepat

merupakan faktorisasi prima untuk positif integer

maka

BUKTI:

TERBUKTI ■

Contoh 11:


Contoh 12:

Teorema 4

selalu bernilai genap untuk

BUKTI:
Anggap . (faktorisasi prima), maka

Dari teorema 2, kita tahu bahwa .
Perhatikan bahwa selalu genap untuk setiap , kecuali untuk DAN .
Terdapat satu saja yang bernilai genap mengakibatkan juga bernilai genap.

TERBUKTI ■

=======================================================================

Selain bisa ditulis sebagai , phi function juga bisa ditulis dalam bentuk . Ini hanya merupakan masalah bentuk simbol phi saja. Ada yang curly, ada yang straight.

Phi function memiliki banyak kegunaan, terutama di bidang kriptografi (persandian). Namun, karena keterbatasan tempat dan waktu, kita tidak membahasnya sekarang. Di post ini, kita hanya belajar mengenai perhitungan phi function saja.

Lihat lanjutan post ini: Teorema Euler

Sumber:
http://en.wikipedia.org/wiki/Euler%27s_totient_function
http://mathworld.wolfram.com/TotientFunction.html
Buku Elementary Number Theory oleh Kenneth H Rosen.