Teorema Fermat dan Wilson

BAB I

PENDAHULUAN

A.           Latar belakang

Dalam mengenal teori – teori bilangan ada dua matematikawan  yang memberikan kontribusi besar dalam pengembangan teori bilangan  yaitu Fermat, dan Wilson. Ketiga matematikawan ini menciptakan teorema – teorema  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 ke – 17. Pierre De Fermat, seorang pengacara  yang juga matematikawan amatir abad ke – 7, sering menulis komentar – komentar 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 matematikawan – matematikawan 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 = x² –  y²

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 x² – n =  y²

2.        Tentukan k bilangan bulat pertama dimana k² > n

3.        Urutkan bilangan berikut :

k² – n, (k  + 1) – n, (k  + 2)² – n, (k  + 3)² – n, .....

            Hingga langkah ke m sehingga (k  + m)² – n adalah bilangan kuadrat.

Contoh :

1.             Faktorkan bilangan n = 119143

Penyelesaian :

Menentukan k sehingga k²  119143

345² = 119025

346² = 119716

Ambil k = 346

2.            Uurutkan bilangan (k  + m)² – n, dengan m = 0, 1, 2, ….., n

Penyelesaian :

346² – n = 573

347² – n = 1266

348² – n = 1961

349² – n = 2658

350² – n = 3375

351² – n = 4058

352² – n = 4761

Ternyata sampai pada m = 6 sudah menghasilkan bilangan kuadrat  yaitu :

(346 + 6)² – 119143 = 4761 = 69². 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=x² –  y². Sekarang x dan  y lebih umum,  yaitu cukup memenuhi

x²  y² (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.

                                    x²   y² (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 579² 18²(mod 2189). Hitung gcd masing – masing ?

Penyelesaian :

                                    gcd (579 – 18,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 x₁,x_2,…,x_k sehingga (x₁ – n)…(x_k – n) bilangan kuadrat, katakan  y². Akibatnya dapat ditulis (x₁…x_k)  y²(mod n). ini menghasilkan factor tak sejati.

Contoh :

1.             Kita akan memfaktorkan n = 12499. ?

Penyelesaian :

Inspeksi awal 112² = 12544 (Karena k² harus lebih besar dari n)

Dimulai dari k = 112.

112² – n =            45        ®        112² 3²  5 (mod 12499)

117² – n =            1190    ®        117²   2  5  7  17 (mod 12499)

121² – n =            2142    ®        121^{2   2} (mod 12499)

Jika kita kalikan hasil – hasil ini maka akan di peroleh :

(112²  117²  121²) (2 ²  gagal?

Bila diambil kemungkinan yang lain, mis

113²          2 ² (mod 12499)

127^{2         2} (mod 12499)

Maka di peroleh :

(113 127)²  (2 ² (mod12499) ²  990²(mod 12499)

Karena 1852  maka kita berhasil.

E.            Teorema “Litle” Fermat

·           Teorema

Misalkan p prima dan andaikan p a maka a^{p – 1} 1(mod p).

ilustrasi : p = 3 maka untuk a = 5 berlaku 5^{3 – 1} 1 (mod 3). Tetapi untuk a = 6 tidak berlaku bahwa 6^{3 – 1}=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 a^p a(mod p) untuk sembarang bilangan bilat a.

·           Bukti

Ada 2 kemungkinan : bila p|a maka pernyataan otomatis berlaku. Bila p∤a maka dengan teorema fermat diperoleh a^{p – 1} 1(mod p). Kalikan kedua ruas dengan a, akibat ini terbukti.

Contoh :

Kita akan membuktikan 5³⁸ 4 (mod 11) ?

Penyelesaian :

Ambil p = 11

a = 5

Dengan fakta : 5² 11) maka di peroleh

5³⁸        =    ³ (5²)⁴

                                                                       

                                                                       

G.           Uji Primalitas dengan teorema fermat

Bila kongruensi a^p 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

a^p-1 1(mod p). selanjutnya, jika kedua ruas dikalikan a, maka diperoleh

a^p a(mod p). jika (a,p)=p maka a, sehingga a 0 (mod p) dan

a^p 0 (mod p) pula. Jadi, a^p a(mod p).

Contoh :

Misalkan n = 117 ?

Penyelesaian :

Ambil a           = 2

Ditulis 2²¹⁷         = (2⁷)¹⁶

Karena 2⁷           = 128  11(mod 117)

maka berlaku:

2¹¹⁷     

Tetapi 2²¹        = (2⁷)  

                                            

Akhirnya diperoleh 2¹¹⁷ = 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 bi – implikasi, 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.