Euler's Totient Function
Euler Phi-Function sering disebut juga sebagai Euler totient function.
yang memenuhi syarat:
dan 
koprima.
Note, dan dikatakan koprima jika 
.
=======================================================================
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
.
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.
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.
Untuk
dan 
saling relatif prima (koprima), maka
Contoh 9:
Contoh 10:
merupakan faktorisasi prima untuk positif integer
Contoh 11:
Contoh 12:
selalu bernilai genap untuk 
=======================================================================
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 ().
) 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
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
Contoh 2:
terdapat 2 bilangan yang koprima dengan 6 yaitu 1 dan 5.
Contoh 3:
terdapat 3 bilangan yang memiliki faktor dengan 9, yaitu 3, 6, dan 9
Jadi, terdapat 6 bilangan yang koprima dengan 9.
Contoh 4:
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 primaContoh 5:
terdapat 1 bilangan yang memiliki faktor dengan 13, yaitu 13.
Jadi, terdapat 12 bilangan yang koprima dengan 13.
Contoh 6:
Teorema 2
Untuk bilangan prima dan positif integeratau dapat ditulis:
Contoh 7:
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:
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 .
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 .
Karena terdapat baris yang koprima terhadap DAN di setiap baris tersebut terdapat elemen yang koprima dengan , maka dapat disimpulkan bahwa:
TERBUKTI ■
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: 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: 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:
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)
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:
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 . ■
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
4 mod 5 ,__ 3 3 mod 5 ,__ 72 mod 5 ,__ 100 mod 5 ,__ 161 mod 5Apakah (-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:
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.
Anggap
. (faktorisasi prima), maka.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
, 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.
http://en.wikipedia.org/wiki/Euler%27s_totient_function
http://mathworld.wolfram.com/TotientFunction.html
Buku Elementary Number Theory oleh Kenneth H Rosen.
0 Comments
