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 ().
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
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 .
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:
Karena kita ingin memperhitungkan bilangan yang koprima dengan , maka kita tinjau barisan yang koprima dengan .
----
Anggap dan koprima.Kita tulis kembali baris sbb:
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)
dan jika adalah positif integer dimana ,
dan adalah integer, maka:
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 . ■
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:
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 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.
Situs Agen Judi Online daftar judi bola terbaik judi poker slot terbaik dan terpercaya 2020
ReplyDeleteSitus Daftar Judi Onlin
Judi Bola Online
Agen judi Bola Terpercaya
Agen Judi Online Resmi
Keren sekali dan bermanfaat tulisNnya ..
ReplyDelete