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 ,
__ 7

2 mod 5 ,
__ 10

0 mod 5 ,
__ 16

1 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
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