Teorema Wilson Dan Teorema Euler PDF [PDF]

Citation preview

MATA KULIAH : TEORI BILANGAN TEOREMA WILSON DAN TEOREMA EULER



Nama : Ni Kadek Sumarwati Nim : 1308405036



JURUSAN MATEMATIKA FAKULTAS MIPA UNIVERSITAS UDAYANA TAHUN AJARAN 2016/2017



TEOREMA WILSON



1. Pengertian Dalam buku yang dipublikasikan tahun 1770, seorang matematikawan Inggris Edward Waring menyatakan bahwa muridnya menemukan (p-1)!+1 habis dibagi oleh p berapapun p yang merupakan bilangan prima. Namun, tidak ada dari keduanya yang mampu membuktikannya. Tahun 1771, Joseph Lagrange membuktikan teorema ini, yang selanjutnya dikenal sebagai teorema Wilson.



2. Teorema Jika 𝑝 adalah bilangan prima, maka (𝑝 − 1)! ≡ −1 𝑚𝑜𝑑 𝑝



3. Bukti Teorema Sebelum pembuktian, kita lihat ilustrasi ide di balik pembuktian ini. Tentukan sisa pembagian (7 − 1)! dibagi 7 (7 − 1)! = 6! = 1.2.3.4.5.6 Selain 1 dan 6, maka kita akan menyusun pasangan-pasangan yang merupakan invers modulo. 2.4 ≡ 1 𝑚𝑜𝑑 7 3.5 ≡ 1 𝑚𝑜𝑑 7 Oleh karenanya, kita lakukan grouping sebagai berikut: 6! = 1. (2.4). (3.5). 6 Jadi, 6! ≡ 1. (1). (1). 6 𝑚𝑜𝑑 7 6! ≡ 6 𝑚𝑜𝑑 7 6! ≡ −1 𝑚𝑜𝑑 7



1



Bukti Teorema Wilson : Ingat : 𝑎 adalah invers dari 𝑏 modulo 𝑐, jika 𝑎. 𝑏 ≡ 1 𝑚𝑜𝑑 𝑐. Untuk 𝑝 = 2 , maka (2 − 1)! ≡ 1 𝑚𝑜𝑑 2 ≡ −1 𝑚𝑜𝑑 2 adalah benar. Jadi, teorema itu benar untuk 𝑝 = 2 . Sekarang, asumsikan 𝑝 adalah bilangan prima yang lebih besar 2. Dari bilangan 1,2,3,4,5,..., (p-2), (p-1), bilangan yang memiliki invers modulo p terhadap dirinya sendiri hanya 1 dan (p-1). Bukti : Kita tahu bahwa 1 memiliki invers modulo dirinya sendiri, karena 1.1 ≡ 1 𝑚𝑜𝑑 𝑝. (𝑝 − 1) memiliki invers modulo dirinya sendiri, karena: (𝑝 − 1)(𝑝 − 1) ≡ (−1)(−1) 𝑚𝑜𝑑 𝑝 ≡ 1 𝑚𝑜𝑑 𝑝 Lalu bagaimana dengan bilangan selain 1 dan (p-1). Seandainya 𝑎 adalah sembarang integer yang mempunyai invers modulo terhadap dirinya sendiri dan 1 < 𝑎 < 𝑝 − 1, maka kondisi ini harus berlaku: 𝑎. 𝑎 ≡ 1 𝑚𝑜𝑑 𝑝 𝑎2 − 1 ≡ 0 𝑚𝑜𝑑 𝑝 (𝑎 + 1)(𝑎 − 1) ≡ 0 𝑚𝑜𝑑 𝑝 𝑝|𝑎 + 1 ∨ 𝑝|𝑎 − 1 𝑎 ≡ −1 𝑚𝑜𝑑 𝑝 ∨ 𝑎 ≡ 1 𝑚𝑜𝑑 𝑝 Kondisi ini ternyata berkontradiksi dengan pernyataan awal bahwa 1 < 𝑎 < 𝑝 − 1. Jadi, bilangan 𝑎 dalam 1 < 𝑎 < 𝑝 − 1 selalu mempunyai pasangan invers modulo dengan bilangan yang lainnya. Selanjutnya, kita dapat melakukan grouping sbb: (𝑝 − 1)! = 1. (𝑎. 𝑎̅). (𝑏. 𝑏̅ ) … (c. 𝑐̅). (𝑑. 𝑑̅ ). (𝑝 − 1) (𝑝 − 1)! ≡ 1. (1). (1) … (1). (1). (𝑝 − 1) 𝑚𝑜𝑑 𝑝 (𝑝 − 1)! ≡ −1 𝑚𝑜𝑑 𝑝∎



2



4. Contoh Soal  Soal 1 Berapakah hasil dari 70! Dibagi 71 ? Penyelesaian : Dik : p=71 (prima) 70! = (71 − 1)! ≡ 70 𝑚𝑜𝑑 71 ≡ −1 𝑚𝑜𝑑 71  Soal 2



Tentukan sisa pembagian 14!.12!.10! dibagi 13 ! Penyelesaian : 14! .12! .10! = 14.13.12! .12! .10! ≡ 14.13. (−1). (−1). 10! (𝑚𝑜𝑑 13) ≡ 0 (mod 13)



3



TEOREMA EULER



1. Pengertian Fermat's Little Theorem (FLT) bekerja dengan baik jika bilangannya adalah prima. Namun, hal ini kurang memuaskan para matematikawan karena kurang praktis. Bagaimana dengan bilangan komposit? Tahun 1736, Leonhard Euler berhasil membuktikan FLT. Kemudian, 24 tahun kemudian, FLT digeneralisasi oleh Euler. Selanjutnya generalisasi ini disebut dengan teorema Euler.



2. Teorema



 Definisi 1 Fungsi phi-euler dalah fungsi pada bilangan asli n yang didefinisikan sebgai berikut : 𝜑(𝑛) adalah banyaknya bilangan pada {1,2,3,4,...,n-1} yang relatif prima ke 𝑛. Contoh : 𝜑(8) = 4, karena ada 4 bilangann asli yang kurang dari 8 yang relatif prima ke 8, ke-4 bilangan tersebut adalah 1,3,5,7. 𝜑(11) = 10, karena semua bilangan pada {1,2,3,4,...,10} relatif prima ke 11.  Teorema 1. Jika 𝑝 prima maka 𝜑(𝑝) = 𝑝 − 1 2. Jika 𝑝 prima dan 𝑛 ≥ 1 maka 𝜑(𝑝𝑛 ) = 𝑝𝑛 − 𝑝𝑛−1



4



Bukti : 1. Jika p prima maka semua bilangan pada {1,2,3,4,...,p-1} relatif prima ke p, itu artinya 𝜑(𝑝) = 𝑝 − 1. 2. Ada 𝑝𝑛 elemen pada himpunan {1,2,3,4,..., 𝑝𝑛 } . Elemen pada himpunan tersebut tidak relatif prima ke p jika hanya jika dapat dibagi oleh p. Elemen pada himpunan yang dapat dibagi oleh p adalah : 1𝑝, 2𝑝, 3𝑝, … , 𝑝𝑛−1 Ada sebanyak 𝑝𝑛−1 elemen yang tidak relatif prima ke p maka banyaknya elemen yang relatif prima ke p sebanyak 𝑝𝑛 − 𝑝𝑛−1  Definisi Sistem residu tereduksi mod n adalah himpunan bilangan {1,2,3,4,...,n-1} yang memenuhi : • Jika 𝑖 ≠ 𝑗 maka 𝑎𝑖 ≢ 𝑎𝑗 𝑚𝑜𝑑 𝑛 • Untuk setiap 𝑎𝑖 relatif prima ke 𝑛 Dengan demikian sistem residu tereduksi mod n merepresentasikan bilangan-bilangan yang relatif prima ke 𝑛. Contoh : 1. {1,5,7,11} merupakan sistem residu tereduksi mod 12.  Lemma Diberikan 𝜑(𝑛) = 𝑘 dan {𝑎1 , 𝑎2 , … , 𝑎𝑘 } adalah Sistem residu tereduksi mod n, berlaku : • Untuk semua bilangan bulat m maka {𝑎1 + 𝑚𝑛, 𝑎2 + 𝑚𝑛, … , 𝑎𝑘 + 𝑚𝑛} merupakan sistem residu tereduksi mod n. • Jika m relatif prima ke n maka {𝑚𝑎1 , 𝑚𝑎2 , … , 𝑚𝑎𝑘 }merupakan sistem residu tereduksi mod n.



Akibatnya : Diberikan 𝜑(𝑝) = 𝑘 dan {𝑎1 , 𝑎2 , … , 𝑎𝑘 } adalah Sistem residu tereduksi mod n, jika s relatif prima ke n dan t sebarang bilangan bulat maka {𝑠𝑎1 + 𝑡, 𝑠𝑎2 + 𝑡, … , 𝑠𝑎𝑘 + 𝑡} merupakan sistem residu tereduksi mod n.



5



Contoh : {1,5} merupakan sistem residu tereduksi mod 6. Tambahkan 12=2x6 pada setiap bilangan diperoleh {13,17} sistem residu tereduksi mod 6 lainnya, Kita tahu 6 relatif prima ke 25, jika kita kalikan sistem yang awal dengan 25 diperoleh {25,125}sistem residu tereduksi mod 6 lainnya, terakhir {25 + 12, 125 + 12} = {37,137}juga merupakan sistem residu tereduksi mod 6.



 Teorema Euler Setiap bilangan bulat 𝑎 dan 𝑛 bilangan bulat positif yang relatif prima ke 𝑎 maka , 𝑎𝜑(𝑛) = 1 𝑚𝑜𝑑 𝑛 Bukti : Ambil 𝜑(𝑛) = 𝑘 dan {𝑎1 , 𝑎2 , … , 𝑎𝑘 } adalah Sistem residu tereduksi mod n, diasumsikan 𝑎𝑖 termuat di {1,2,3,4,...,n-1} Karena a dan n relatif prima maka {𝑎𝑎1 , 𝑎𝑎2 , … , 𝑎𝑎𝑘 } juga merupakan sistem residu tereduksi mod n. Kedua sistem tersebut haruslah mempunyai hasil perkalian modulus n yang sama (𝑎𝑎1 ), (𝑎𝑎2 ), … , (𝑎𝑎𝑘 ) ≡ 𝑎1 , 𝑎2 , … , 𝑎𝑘 (𝑚𝑜𝑑 𝑛) 𝑎𝑘 (𝑎1 , 𝑎2 , … , 𝑎𝑘 ) ≡ 𝑎1 , 𝑎2 , … , 𝑎𝑘 (𝑚𝑜𝑑 𝑛) Karean setiap 𝑎𝑖 relatif prima ke n, jika dikalikan kedua sisi dengan 𝑎1 ̅̅̅, ̅̅̅, 𝑎2 … , ̅̅̅̅ 𝑎𝑘 diperoleh : 𝑎𝑘 ≡ 1 𝑚𝑜𝑑 𝑛 𝑎𝑡𝑎𝑢 𝑎𝜑(𝑛) = 1 𝑚𝑜𝑑 𝑛



6



3. Contoh Soal  Soal 1



Tentukan sisa pembagian 79 oleh 3 ! Penyelesaian : 𝜑(3) = 3 − 1 = 2 1 𝑚𝑜𝑑 3 (𝑏𝑒𝑟𝑑𝑎𝑠𝑎𝑟𝑘𝑎𝑛 𝑡𝑒𝑜𝑟𝑒𝑚𝑎), 𝑑𝑖𝑝𝑒𝑟𝑜𝑙𝑒ℎ : 79 = 72(4) . 7 ≡ 14 . 7 𝑚𝑜𝑑 3 ≡ 7 𝑚𝑜𝑑 3 ≡ 1 𝑚𝑜𝑑 7  Soal 2



Tentukan 𝜑(84 )! Penyelesaian : 𝜑(84 ) = 𝜑((2.2.2)4 ) = 𝜑(24 ). 𝜑(24 ). 𝜑(24 ) = (25 − 24 ). (25 − 24 ). (25 − 24 ) = (32 − 16). (32 − 16). (32 − 16) = 16.16.16 = 4096



7



DAFTAR PUSTAKA 1. Blogspot : Aria Turns. 2010. Teorema Euler 2. http://en.wikipedia.org/wiki/Wilson%27s_theorem 3. Kenneth H Rosen. Elementary Number Theory



8