Defenisi 2 (fungsi Euler Phi-Function digunakan dalam teorema Euler. Meskipun namanya menggunakan kata phi namun fungsi ini sama sekali tidak menggunakan nila. Penggunaan phi semata-mata untuk fungsiEuler phi functionadalah fungsi yang menghitung banyaknya bilangan bulatyang koprima dengancontoh

Karena dari sepuluh bilangan kurang dari atau sama dengan 10: 1,2,3,4,5,6,7,8,9,10terdapat 4 bilangan yang koprima dengan 10 yaitu 1,3,7,9

Berikut adalah teorema-teorema yang perlu diperhatikan dalam Euler Phi-Function:Teorema PertamaUntuk n bilangan prima, selalu berlakuContoh:******Teorema KeduaUntukbilangan prima danbilangan bulat positif, selalu berlaku

atau ekuivalen dengancontoh

*******Teorema Ketiga

Phi function adalah fungsi multiplikatif.Untuk mdan nsaling relatif prima (koprima), maka

contoh

******Kalau repot dengan seluruh rumus diatas, pakai saja konsep di bawahmerupakan faktorisasi prima dari bilangan bulat n, maka

contoh

*******Ingat bahwaselalu bernilai genap untuk

Fungsi phi-eulerKita tahuteorema kecil fermatmenyatakanUntuk sebarang bilangan bulatdan bilangan primayangcoprimekeberlaku

Nah..sekarang bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat masih berlaku?Tidak, sebgai contohnya jika kita ambildan,apakahTidak karena 15 tidak membagi.Akan tetapi ada cara memodifikasi teorema kecil fermat sehingga tetap berlaku meskupun modulusnya tidak prima. Teorema fermat yang udah dimodifikasi inilah yang disebut teorema euler.Nah..sebelum membahas teorema euler akan saya bahas mengenai fungsi euler-phiDefinisi: Fungsi phi-euler,adalah fungsi pada bilangan asliyang didefinisikan sebgai berikutadalah banyaknya bilangan padayang coprime keContoh:karena ada 4 bilangann asli yang kurang dari 8 yang coprime ke 8 ke-4 bilangan tersebut adalah 1,3,5,7.kerna semua bilangan padacoprime ke 11.Teorema1. Jikaprima maka2. Jikaprima danmakaBukti1. Jikaprima maka semu bilangan padacoprime ke, itu artinya2. Adaelemen pada himpunan. Elemen pada himpunan tersebut tidak coprime kejika hanya jika dapat dibagi oleh. Elemen pada himpunan yang dapat dibagi olehadalah

Ada sebanyakelemen yang tidak coprime kemaka banyaknya elemen yang coprime kesebanyakDefinisi:Sistem residu tereduksi mod(reduced residue system mod) adalah himpunan bilangan-bilangan

Yang memenuhi1. Jikamaka2. Untuk setiapcoprime keDengan demikian Sistem residu tereduksi modmerepresentasikan bilangan-bilangan yang coprime keContoh:dankeduanya merupakan sistem residu tereduksi modLemma:Diberikandanadalah Sistem residu tereduksi mod, berlaku:1. Untuk semua bilangan bulatmakamerupakan sistem residu tereduksi mod.2. Jikacoprime kemakamerupakan sistem residu tereduksi mod.Akibat:Diberikandanadalah Sistem residu tereduksi mod, jikacoprime kedansebarang bilangan bulat makamerupakan sistem residu tereduksi mod.Contoh:merupakan sistem residu tereduksi mod. tmabahkanpada setiap bilangan diperoleh, sistem residu tereduksi modlainnya, Kita tahu 6 coprime ke 25, jika kita kalikan sistem yang awal dengan 25 diperolehistem residu tereduksi modlainnya, terakhirjuga merupakan sistem residu tereduksi modSelanjutnya kita bahas teorema eulerTeorema Euler:Setiap bilangan bulatdanbilangan bulat positif yang coprime kemaka

Perhatikan jikaprima maka, teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa menganggap teorema euler sebagai generalisasi teorema kecil fermat.Bukti:Ambildanadalah Sistem residu tereduksi mod, diasumsikantermuat di.Karenadancoprime makajuga merupakans sistem residu tereduksi mod, Kedua sistem tersebut haruslah mempunyai hasil perkalian modulusyang sama

Karean setiapcoprime ke, jika dikalikan kedua sisi dengandiperolehatau dengan kata lain

MENGENAL EULER PHI-FUNCTIONEuler 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 functionPhi functionadalah fungsi yang mengitungbanyaknyaintegeruntukyang memenuhi syarat:dankoprima.

Note,dandikatakan 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 9Jadi, 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 1Untukbilangan prima

Contoh 5:

Dari bilangan 1, 2, 3, ... , 13terdapat 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 2Untukbilangan prima danpositif 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 3Phi function adalah fungsi multiplikatif.

Untukdansaling relatif prima (koprima), maka

ILUSTRASI BUKTI:Anggapdan, 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, ... ,, ... ,, misalkanmemiliki faktor dengan.Kita tulis kembali baris ke-, yaitu:

Karenamemiliki 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 tinjaubarisan yang koprima dengan.----Anggapdankoprima.Kita tulis kembali barissbb:

Karenadankoprima, maka semua elemen di baristersebut merupakan sistem komplit residu modulo. (Lihat teorema di kotak biru di bawah). Oleh karenanya, di baristersebut pasti terdapatbilangan yang koprima dengan.Sistem komplit residu moduloadalah kumpulanintegeryang 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:-14 mod 5 ,__33 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, karenadan. (kelas sisanya sama)TeoremaJikaadalah sistem komplit residu modulodan jikaadalah positif integer dimana,danadalah integer, maka:juga merupakan sistem komplit residu modulo

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

(LihatSINI) Karena, maka:

Namun, karena kita tahu bahwaadalah sistem komplit modulo, maka tidak mungkin ada kelas sisa yang sama antardan.

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

Karena terdapatbaris yang koprima terhadapDAN di setiap baris tersebut terdapatelemen yang koprima dengan, maka dapat disimpulkan bahwa:

TERBUKTI

Contoh 9:

Contoh 10:

Rumus Cepatmerupakan faktorisasi prima untuk positif integermaka

BUKTI:

TERBUKTI

Contoh 11:

Contoh 12:

Teorema 4selalu bernilai genap untuk

BUKTI:Anggap. (faktorisasi prima), maka

Dari teorema 2, kita tahu bahwa.Perhatikan bahwaselalu genap untuk setiap, kecuali untukDAN.Terdapat satu sajayang bernilai genap mengakibatkanjuga bernilai genap.TERBUKTI