Fungsi ɸ (Phi) Dan Teorema Euler [PDF]

Citation preview

MAKALAH TEORI BILANGAN FUNGSI PHI DAN TEOREMA EULER



Dosen Pengampu : Dra. Dewi Iriani M. Pd Disusun oleh : Kelompok 8 Kelas R-001 1. Dita Nur Syaharani



A1C221078



2. Novi Rahmayanti



A1C221079



3. M Kms Abdul Zaqi



A1C221077



PROGRAM STUDI PENDIDIKAN MATEMATIKA JURUSAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS JAMBI TAHUN 2022



i



KATA PENGANTAR Puji syukur kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya sehingga kami dapat menyelesaikan tugas makalah yang berjudul “Fungsi Phi dan Teorema Euler” ini tepat pada waktunya. Kami mengucapkan terima kasih kepada Dosen Pengampu dan berbagai pihak yang telah memberikan arahan dan dukungan dalam pembuatan makalah ini sehingga dapat kami selesaikan dengan tepat waktu. Kami berharap, semoga makalah ini bermanfaat bagi para pembaca yang dapat menambahkan ilmu pengetahuan dan wawasan serta dapat diimplikasikan dalam kehidupan seharihari. Penyusunan makalah ini masih belum dikatakan sempurna. Hal ini karena keterbatasan kemampuan kami sebagai insaniah yang masih selalu belajar memperbaiki kesalahan-kesalahan kami. Dengan demikian, kami mengharapkan kritik dan saran yang membangun dari para pembaca untuk memperbaiki makalah ini.



Jambi, 9 April 2022



Kelompok 8



DAFTAR ISI



ii



KATA PENGANTAR.............................................................................................................ii DAFTAR ISI..........................................................................................................................iii BAB I PENDAHULUAN........................................................................................................1 A.



Latar Belakang.................................................................................................................1



B.



Rumusan Masalah............................................................................................................1



C.



Tujuan Penulisan..............................................................................................................1



BAB II.....................................................................................................................................2 PEMBAHASAN......................................................................................................................2 A.



Fungsi ɸ Euler..................................................................................................................2



B.



Teorema Euler..................................................................................................................3



BAB III PENUTUP...............................................................................................................10 A.



Kesimpulan....................................................................................................................10



B.



Saran..............................................................................................................................10



DAFTAR PUSTAKA............................................................................................................11



iii



BAB I PENDAHULUAN A. Latar Belakang Matematika sebagai salah satu ilmu dasar yang dewasa ini semakin dirasakan interaksinya dengan bidang – bidang ilmu seperti teknologi, rekayasa, ekonomi, permainan, bahkan hampir semua aspek kehidupan sehari – hari. Dalam kehidupan sehari – hari sering kali diharapakan pada suatu keadaan yang menuntut untuk menghitung atau mencacah sesuatu, mulai dari hal yang sederhana sampai yang sulit. Dalam kehidupan atau pembelajaran sehari – hari pasti kita tidak asing dengan kata teorema, mau itu disekolah ataupun dilingkungan. Teorema adalah pernyataan yang dapat dibuktikan kebenarannya atau pernyataan yang dapat dbuktikan atas dasar asumsi yang telah disetujui sebelumnya. Dalam logika teorema adalah pernyataan dalam bahasa formal dan saat diturunkan dengan mengaplikasikan aturan inferensi dan aksioma dari sebuah system deduktif. Fungsi phi euler didefinisikan sebagai fungsi yang menyatakan banyaknya bilangan bulat positif yang lebih kecil dari sebuah bilangan bulat dan relatif prima terhadap bilangan bulat tersebut. Jadi jika terdapat bilangan bulat positif n, maka nilai adalah banyaknya bilangan bulat positif yang lebih kecil dari n dan relatif prima terhadap n. Teorema Euler menjadi dasar algoritma RSA, yang banyak digunakan dalam sistem komunikasi di Internet. Dalam algoritma ini, teorema Euler digunakan bersama sebuah bilangan n yang merupakan hasil kali dari dua bilangan prima besar. Tingkat keamanan algoritma tersebut didasarkan pada tingkat kesulitan untuk memfaktorkan bilangan n.



1



B. Rumusan Masalah Adapun rumusan masalah dari makalah ini, sebagai berikut : 1.Apa yang dimaksud dengan fungsi ɸ euler? 2.Bagaimana bentuk dari teorema-teorema yang digunakan pada teorema euler?



C. Tujuan Penulisan Adapun tujuan penulisan dari makalah ini, sebagai berikut : 1.Dapat mengetahui apa itu fungsi ɸ euler. 2.Dapat mengetahui teorema-teorema yang digunakan pada teorema euler.



2



BAB II PEMBAHASAN A. Fungsi ɸ Euler Misalkan n adalah bilangan bulat positif dan a adalah bilangan bulat yang relative prima dengan n, maka a ϕ (n ) ≡1 modn dengan ɸ(n) (ɸ dibaca phi) adalah fungsi phi euler (Euler’s Torient Function), yaitu fungsi yang menghitung banyaknya bilangan bulat positif kurang dari n yang relatif prima dengan n. Definisi 1 : Sistem residu sederhana modulan adalah himpunan semua bilangan bulat positif yang memenuhi (r,m) = 1, dengan ri ≠ rj (mod m) untuk i ≠ j Contoh : {1,2,3,4,5,6,7,8} adalah himpunan semua residue terkecil 9. Apabila dari unsur – unsur himpunan ini dipilih yang saling prima dengan 9 yaitu {1,2,4,5,7,8}, maka himpunan terakhir ini disebut



system residu



sederhana mod 9. System residu sederhana mod 9 yang lain diantaranya adalah {19, 11,22,5,16,98}. Definisi 2 : Misalkan m suatu bilangan bulat positif, maka ɸ (m) menyatakan banyaknya elemen dari himpunan residu sederhana modulo m. Contoh



:



Himpunan



residu



sederhana



modulo



30



adalah



{1,7,11,13,17,19,23,29}. Banyaknya elemen dari himpunan ini adalah 8, maka dikatakan bahwa ɸ(30) = 8. Definisi 3 : Suatu fungsi f yang didefinisikan pada himunan semua bilangan bulat positif disebut fungsi ganda apabila untuk setiap bilangan – bilangan bulat psotif m dan n dengan (m,n) = 1 maka f(mn) = f(m) f(n). Lebih luas definisi 3 dapat dinyatakn sebagai berikut



3



F suatu fungsi fansa apabila untuk setiap bilangan bulat positif m1, m2, m3,..., mk dengan (m1,m2) = 1untuk I,j = 1,2,3,..,k dan i ≠ j maka f (m 1, m2, m3,...,mk) = f(m1), f(m2), f(m3),..., f(mk). Contoh : Misalkan f (n) = n2, untuk setiap bilangan asli n. untuk sembarang bilangan asli m dan n dengan (m,n) = 1, maka f (mn) = (mn) 2 = m2 n2 = f(m) f(n). sehingga fungsi f tersebut adalah fungsi ganda.



B. Teorema Euler Teorema 1 : Jika p adalah bilangn prima, maka ϕ ( p )= p−1 Sebaliknya, jika p adalah bilangan bulat positif dengan ϕ ( p )= p−1, maka p adalah bilangan prima. Bukti : Nampak disini bahwa apabila p suatu bilangan prima, maka setiap bilangan bulat positif yang kurang dari p selalu saling prima terhadap p, sehingga ϕ ( p )= p−1 . Tetapi apabila n>1 suatu bilangan komposit, maka n mempunyai suatu pembagi, misalnya d dengan 1 2. Apabila n suatu bilangan prima, maka n prima ganjil sehingga ɸ (n) = n – 1. Jadi ɸ (n) bilangan genap, dan apabila n suatu bilangan komposit, maka n mempunyai factor prima gankil p, misalnya n = P = Pk m dengan (Pk, m) = 1 sehingga, ɸ (n) = ɸ (Pkm) = ɸ (Pk) ɸ (m) = Pk-1 (P-1) ɸ (m)



7



Karena p bilangan ganjil, maka p -1 suatu bilangan genap, sehingga P k1



(P-1) ɸ (m) suatu bilangan genap pula. Jadi ɸ (n) suatu bilangan genap.



Teorema 7 : Untuk setiap bilangan bulat positif n, maka



∑ ɸ ( t ) =n t ∨12



Bukti : Perhatikan bilangan bulat positif 1,2,3,4,...,n. Kita akan meletakkan bilangan ini dalam himpunan Ct dengan t|n, yaitu bilangan itu yang dengan n, factor persekutuan terbesarnya sama dengan t. Dengan kata lain, m∈Ct jika dan hanya jika (m,n) = t sedangkan (m,n) = t jika dan hanya jika



( mt , nt )=1



Menurut definisi fungsi ɸ Euler, banyaknya elemen dalam C t adalah



( nt ). Maka banyaknya elemen penggabungan semua himpunan C adalah ∑ ɸ n . Mengingat setiap bilangan 1,2,3,...,n hanya terdapat dalam tepat t∨n ( t ) ∑ ɸ ( t )= ∑ ɸ n =n satu himpunan dari C , maka t∨n t∨n ( t ) ɸ



t



t



Contoh : 1,2,4,5,7,8 masing – masing adalah saling prima terhadap 9. Apabila setiap bilangan tersebut dikalikan 10 menjadi 10,20,40,50,70,80. Selanjutnya, jika bilangan – bilangan dicari residu terkecil modulo 9 maka diperoleh : 10 = 1 (modul 9) 20 = 2 (modul 9) 40 = 4 (modul 9) 50 = 5 (modul 9) 70 = 7 (modul 9) 80 = 8 (modul 9) Jika ruas – ruas dari kekongruenan ini dikalikan, kita akan memperoleh 10,20,40,50,70,0 = 1,2,4,5,7,8 (mod 9) 8



106 (1,2,4,5,7,8) = 1,2,4,5,7,8 (mod 9) 106 = 1 (mod 9), Mengapa? Karena ɸ (9) = 6 Teorema 8 : Jika (a,m) = 1 dan r 1 , r 2 , r 3 , … , r Φ(m) adalah bilangan – bilangan bulat positif yang kurang dari m dan masing – masing prima dengan m, maka residu – residu terkecil mod m dari bilangan – bilangan ar 1 , ar 2 , ar 3 ,… , ar Φ (m ) adalah suatu permutasi dari r 1 , r 2 , r 3 , … , r Φ(m). Bukti : ɸ (m) adalah banyaknya elemen dari himpunan {ar 1 , ar 2 , ar 3 , … , ar Φ(m) .



Untuk



membuktikan



bahwa



residu



–



residu



terkecil



dari



ar 1 , ar 2 , ar 3 ,… , ar Φ (m ) }...(1) adalah suatu permutasi dari r 1 , r 2 , r 3 , … , r Φ(m),



kita harus menunjukan bahwa ar i ≢ ar j (mod m) untuk



1 ≤ i, j ≤ ɸ (m)



dengan i ≠ j serta masing – masing harus ditunjukkan saling prima dengan m. misalkan ar i ≢ ar j (mod m) untuk



1 ≤ i, j ≤ ɸ (m) dengan i ≠ j.



karena (a,m) = , maka kita dapat melenyapkan a dari kekongruenan itu, sehingga diperoleh r i ≡r j(mod m). dan karena ri dan rj masing – masing adalah residu – residu terkecil modulo m, maka maka ri ≠ rj. Jadi jika ari ≢ arj (mod m), maka ri ≠ rj. sehingga kontraposisinya benar pula bahwa jika ri = rj maka ari ≡ arj (mod m) hal ini berarti bahwa bilangan-bilangan pada (1) tidak ada yang kongruen mod m. Selanjutnya akan ditunjukkan bahwa ar 1 , ar 2 , ar 3 ,… , ar Φ (m ) masing – masing prima dengan m. Andaikan ada suatu bilangan prima P yang merupakan factor persekutuan dari arid an m maka P|ari dan P|m. P|ari dan P suatu bilangan prima, maka P|a atau P|r i. Jadi P merupakan factor prsekutuan dari a, ri, dan m. hal ini tidak mungkin, karena (a,m) + (m, r i) =1. Jadi (ari, m) =1 untuk 1 ≤ i, j ≤ ɸ(m). Contoh : 1,3,5,7 masing – masing saling prima dengan 8 dan ɸ (8) = 4, maka 9.1, 9.3, 9.5, 9.7 masing – masing mempunyai residu terkecil mod 8 dengan tepat satu dari 1,3,5 dan7, karena (8,9) = 1. Hal ini diperiksa sebagai berikut :



9



9.1 ≡ 1 (mod 8), 9.3 ≡ 3 (mod 8), 9.5 ≡ 5 (mod 8), dan 9.7 ≡ 7 (mod 8). Teorema 9 : Jika m suatu bilangan bulat positif dan(a,m) =1, maka a ɸ(m) ≡ 1 (mod m). Bukti : Misalkan r 1 , r 2 , r 3 , … , r Φ(m) adalah bilangan – bilangan bulat positif yang kuran dari m dan masing – masing prima dengan m. karena (a,m) = 1, maka residu – reside terkecil modulo m dari ar 1 , ar 2 , ar 3 ,… , ar Φ (m ) adalah suatu permutasi dari r 1 , r 2 , r 3 , … , r Φ(m) sehingga diperoleh. (ar 1),(ar 2 ), (ar 3 ), … ,( ar Φ ( m) ) ≡ r 1 r 2 r 3 … r Φ(m ) (mod m)



arɸ(m) = [ r 1 , r 2 , r 3 , … , r Φ ( m) ] ≡ r 1 , r 2 , r 3 , … , r Φ(m) (mod m) karena r 1 , r 2 , r 3 , … , r Φ(m) masing – masing saling prima dengan m, maka hasil kali bilangan – bilangan itu saling prima dengan m. sehingga kita dapat menyelenggarakan r 1 , r 2 , r 3 , … , r Φ(m) dari kekongruenan terakhir dan diperoleh aɸ(m) ≡ 1 (mod m)



10



BAB III PENUTUP A. Kesimpulan Adapun kesimpulan dari makalah ini,yaitu: 1. Misalkan n adalah bilangan bulat positif dan a adalah bilangan bulat yang relative prima dengan n, maka aØ(n) ≡ 1 modn dengan ɸ(n) (ɸ dibaca phi) adalah fungsi phi euler (Euler’s Torient Function), yaitu fungsi yang menghitung banyaknya bilangan bulat positif kurang dari n yang relatif prima dengan n. 2.Teorema-teorema pada teorema euler ini meliputi: 1,



Teorema 1: Jika p adalah bilangn prima, maka ϕ(p) = p – 1. Sebaliknya, jika



p adalah bilangan bulat positif dengan ϕ(p) = p – 1, maka p



adalah bilangan prima. 2.



Teorema 2: Apabila p suatu bilangan prima dan k suatu bilangan bulat positif, maka ɸ(pk) = pk-1(p-1).



3. Teorema 3: Apabila p adalah bilangan prima dan a adalah bilangan bulat positif. Maka ɸ (pa)=pa – pa-1.. 4. Teorema 4: Misalkan m dan n adalah bilangan bulat positif yang prima relatif, maka ϕ(mn) = ϕ(m) ϕ(n).



B. Saran Diharapkan kepada pihak guru, orangtua maupun peserta didik bekerjasama dengan baik. Adakalanya bakat itu tidak disadari dengan cepat tanpa adanya motivasi maupun dorongan dari faktor eksternal. Begitupun untuk guru dan peserta didik haruslah cenderung terbuka satu sama lain agar guru dapat mengenali bakat anak dan peserta didik dapat mengembangkan bakatnya. 11



DAFTAR PUSTAKA Sukarman, Herry. 1993. Materi Pokok Teori Bilangan. Jakarta: Universitas Terbuka, Depdikbud.



1