Jumat, 22 Desember 2017

Teorema Fermat dan Wilson






BAB I
PENDAHULUAN

A.           Latar belakang
Dalam mengenal teoriteori bilangan ada dua matematikawan  yang memberikan kontribusi besar dalam pengembangan teori bilangan  yaitu Fermat, dan Wilson. Ketiga matematikawan ini menciptakan teoremateorema  yang diberikan nama sesuai nama mereka  yaitu Teori Fermart, dan  Teori Wilson.
Teorema dan konsep terkait  yang dikembangkan oleh dua matematikawan ini memotivasi kami sebagai mahasiswa untuk membuat makalah agar pembaca  lebih mengenal bagaimana teori ini digunakan dalam pengembangan ilmu pengetahuan. Dengan mempelajari teorema ini juga, kita bisa mengetahui apa sebenarnya teorema  yang didedikasikan oleh Fermat, dan Wilson serta bagaimana keterkaitan antara kedua teorema ini. Untuk lebih jelasnya akan dibahas pada makalah ini.
      
B.            Rumusan masalah
1.             Bagaimanakah teorema dari Fermat dan Wilson?
     
C.           Tujuan
Tujuan dari makalah ini dibuat selain sebagai tugas dari dosen, makalah ini dibuat untuk mengetahui :
1.             Untuk mengetahui apa dan bagaimanakah teorema dari Fermat, dan Wilson












BAB II
PEMBAHASAN

A.           Definisi Teorema Fermat
Teorema Fermat adalah salah satu teorema paling terkenal di dunia matematika dan dicetuskan oleh Pierre de Fermat pada abad ke17. Pierre De Fermat, seorang pengacara  yang juga matematikawan amatir abad ke7, sering menulis komentarkomentar dipinggiran bukunya. Dan  yang paling terkenal sepanjang sejarah adah Teorema Terkahir Fermat (Fermat Last Theorem). Dinamakan teorema terakhir bukan karena terakhir kali dipublikasikan, namun  yang terakhir kali dibuktikan. Teorema ini tidak berhasil dibuktikan oleh semua matematikawanmatematikawan dunia selama 357 tahun lebih.
Biasanya pemfaktoran n melalui tester,  yaitu faktor prima  yang tidak melebihi   diasumsikan n bulat ganjil. Metoda Fermat didasarkan pada ide penemuan bilangan bulat x dan  y sehingga n = x2 y2
n = (x  +  y) (x –  y)
Maka (x  +  y) dan (x y) adalah faktor dari n. Sebaliknya bila n = ab, a > b > 1, maka dapat dituslis :
Karena n ganjil maka a dan b harus ganjil, oleh karena itu  dan  tak negatif

B.            Algoritma
1.        Tulis x2 – n =  y2
2.        Tentukan k bilangan bulat pertama dimana k2 > n
3.        Urutkan bilangan berikut :
k2 – n, (k  + 1) – n, (k  + 2)2 – n, (k  + 3)2 – n, .....
            Hingga langkah ke m sehingga (k  + m)2 – n adalah bilangan kuadrat.
Contoh :
1.             Faktorkan bilangan n = 119143
Penyelesaian :
Menentukan k sehingga k2  119143
3452 = 119025
3462 = 119716
Ambil k = 346
2.            Uurutkan bilangan (k  + m)2 n, dengan m = 0, 1, 2, ….., n
Penyelesaian :
3462 n = 573
3472 n = 1266
3482 n = 1961
3492 n = 2658
3502 n = 3375
3512 n = 4058
3522 n = 4761
Ternyata sampai pada m = 6 sudah menghasilkan bilangan kuadrat  yaitu :
(346 + 6)2 119143 = 4761 = 692. Diperoleh x = 352 ,  y = 69
Faktorisasi  yang diperoleh adalah
119143 = ( x  +  y)(x  y) = (352  + 69) (352 69) = 421.283
Ciri bilangan kuadrat :
·         Angka terakhirnya kemungkinannya 0, 1, 4, 5, 6 dan 9
·         Dua angka terakhir ada 22 kemungkinan,

C.       Generalisasi metoda faktorisasi fermat
Pada metode sebelumnya, bilangan bulat x dan  y memenuhi n=x2  y2. Sekarang x dan  y lebih umum,  yaitu cukup memenuhi
x2  y2 (mod n)
misalkan d = gcd (x – y, n) atau d = gcd (x + y, n) maka d|n.
Permasalahannya, apakah d factor sejati,  yaitu 1 < d < n ?
dengan asumsi n = pq, p, q prima dengan p < q maka kemungkinan d adalah 1, p, q atau pq.
                                    x2   y2 (mod n)  pq | (x –  y)(x + y)
lemma euclid  p dan q membagi salah satu faktornya. Bila  yang terjadi adalah
·         p|(x –  y) dan q|(x –  y)  pq|(x –  y)  y (mod n), atau
·         p|(x + y) dan q|(x + y) pq|(x + y) - y (mod n).
situasi di mana x    y (mod n) dikesampingkan. Jadi, d adalah salah satu p atau q.
Contoh :
1.             Kita ingin memfaktorkan n =2189 dengan memperoleh 5792 182(mod 2189). Hitung gcd masingmasing ?
Penyelesaian :
                                    gcd (57918,2189) = gcd (561,2189)=11
                                    gcd (579 +18,2189) = gcd (579,2189)=199
maka diperoleh 2189=11.199

D.       Metoda Kraitchik (1920)
Idenya adalah mencari bilangan x1,x2,…,xk sehingga (x1n)…(xkn) bilangan kuadrat, katakan  y2. Akibatnya dapat ditulis (x1xk)  y2(mod n). ini menghasilkan factor tak sejati.
Contoh :
1.             Kita akan memfaktorkan n = 12499. ?
Penyelesaian :
Inspeksi awal 1122 = 12544 (Karena k2 harus lebih besar dari n)
Dimulai dari k = 112.
1122n =            45        ®        1122 32  5 (mod 12499)
1172n =            1190    ®        1172   2  5  7  17 (mod 12499)
1212 n =            2142    ®        1212   2 (mod 12499)
Jika kita kalikan hasilhasil ini maka akan di peroleh :
(1122  1172  1212) (2 2  gagal?
Bila diambil kemungkinan yang lain, mis
1132          2 2 (mod 12499)
1272         2 (mod 12499)
Maka di peroleh :
(113 127)2  (2 2 (mod12499) 2  9902(mod 12499)
Karena 1852  maka kita berhasil.

E.            Teorema “Litle” Fermat
·           Teorema
Misalkan p prima dan andaikan p a maka ap1 1(mod p).
ilustrasi : p = 3 maka untuk a = 5 berlaku 531 1 (mod 3). Tetapi untuk a = 6 tidak berlaku bahwa 631=36 1(mod 3)
·           Bukti
Kumpulkan p – 1 kelipatan pertama a, yaitu V = {a, 2a, 3a, …, (p )a}. Diperoleh fakta :
1.      Tidak ada anggota V yang kongruen satu sama lainnya
2.      Tidak ada anggota V  yang kongruen dengan nol. Maka setiap anggota V pasti kongruen modulo pterhadap salah satu 1,2,…..(p . Kalikan semua kongruensi ini diperoleh a

F.            Akibat teorema Fermat
·           Kesimpulan
Bila p prima maka ap a(mod p) untuk sembarang bilangan bilat a.
·           Bukti
Ada 2 kemungkinan : bila p|a maka pernyataan otomatis berlaku. Bila pa maka dengan teorema fermat diperoleh ap1 1(mod p). Kalikan kedua ruas dengan a, akibat ini terbukti.
Contoh :
Kita akan membuktikan 538 4 (mod 11) ?
Penyelesaian :
Ambil p = 11
a = 5
Dengan fakta : 52 11) maka di peroleh
538        =
                                                                        3 (52)4
                                                                       
                                                                       
G.           Uji Primalitas dengan teorema fermat
Bila kongruensi ap a(mod p) tidak berlaku untuk suatu a maka dipastikan p komposit.
Bukti :
Ambil sembarang bilangan prima p dan sembarang bilangan bulat a, maka (a,p)=1 atau (a,p)=p. jika (a,p)=1, menurut teorema 2 diperoleh bahwa
ap-1 1(mod p). selanjutnya, jika kedua ruas dikalikan a, maka diperoleh
ap a(mod p). jika (a,p)=p maka a, sehingga a 0 (mod p) dan
ap 0 (mod p) pula. Jadi, ap a(mod p).
Contoh :
Misalkan n = 117 ?
Penyelesaian :
Ambil a           = 2
Ditulis 2217         = (27)16
Karena 27           = 128  11(mod 117)
maka berlaku:
2117     
Tetapi 221        = (27)  
                       
                       
                       
                       
Akhirnya diperoleh 2117 = 44  2 (mod 117). Jadi di simpulkan 117 komposit, faktanya
177 = 9
H.           Teorema Wilson
Teorema Wilson adalah salah satu teorema yang menggambarkan sifat dari bilangan prima. Menurut teorema wilson, p adalah bilangan prima jika p membagi (p – 1)! + 1. Begitu pula sebaliknya suatu bilangan p yang membagi (p – 1)! + 1 maka bilangan tersebut adalah prima. Secara formal teorema wilson ditulis sebagai berikut:

Teorema wilson : bilangan bulat 1 < p adalah prima jika hanya jika
(p – 1)!

Bukti : “Karena teorema ini berbentuk biimplikasi, kita harus membuktikannya secara dua arah.
Þ Diberikan bilangan prima p maka dapat dibentuk himpunan bilangan G = {1, 2, ...., p – 1} yang merupakan grup atas perkalian modulo p. Karena G grup maka setiap elemen   mempunyai elemen invers sedemikian hingga .  Jika   maka
 
   
Diperoleh nilai  atau  . Dengan kata lain hanya 1 dan    yang merupakan invers terhadap dirinya sendiri sedangkan elemen lainnya pada  mempunyai invers  yang berbeda. Itu berati setiap elemen di  berbentuk pasangan {  -1} dengan   -1  kecuali untuk 1 dan  . Jika semua elemen dikalikan, diperoleh
1  
1   ) (
                  
Dengan kata lain hasil dari  ! pada adalah   dengan . Dapat disimpulkan  

  Diketahui   andaikan  komposite tidak prima maka mempunyai faktor prima   dengan   . Itu berarti   membagi   dan juga membagi , Jelas itu suatu mustahil. Dengan kata lain  adalah hal  yang mustahil jika  tidak prima.
I.       Bukti Teorema Wilson
"a adalah invers dari b modulo c" jika  . Istilah ini akan kita pakai dalam pembuktian teorema ini.
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.


Oleh karenanya, kita lakukan grouping sebagai berikut:
6! = 1.(2.4).(3.5).6
Jadi, 
.

Selain mod 7, kalian juga bisa coba misalnya dengan modulo yang lain, misalnya modulo 11.

Untuk 
, maka   adalah benar. Jadi, teorema itu benar untuk  .

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 
 dan  . (Bukti ada di kotak di bawah.)
Kita tahu bahwa   memiliki invers modulo dirinya sendiri, karena  .
 memiliki invers modulo dirinya sendiri, karena
.

Lalu bagaimana dengan bilangan selain 
 dan  .
Seandainya 
 adalah sembarang integer yang mempunyai invers modulo terhadap dirinya sendiri dan  , maka kondisi ini harus berlaku:




Kondisi ini ternyata berkontradiksi dengan pernyataan awal bahwa  . Jadi, bilangan   dalam  selalu mempunyai pasangan invers modulo dengan bilangan yang lainnya.

Selanjutnya, kita dapat melakukan grouping sbb:

_______

_______

Jadi, teorema Wilson pun TERBUKTI.



Tidak ada komentar:

Posting Komentar