BAB 4. TEOREMA FERMAT DAN WILSON
Julan HERNADI
1
Program Studi Pendidikan Matematika Universitas Muhammadiyah, Ponorogo
June 11, 2012
Julan HERNADI
Teorema Fermat dan Wilson
Metoda Faktorisasi Fermat (1643) Biasanya pemfaktoran n melalui tester, yaitu faktor prima yang tidak melebihi
√
n . Diasumsikan n bulat ganjil.
Metoda Fermat didasarkan pada ide penemuan bilangan bulat x dan y sehingga n
= x 2 − y 2. n
maka bila n
Karena dapat ditulis
= (x + y )(x − y )
(x + y ) dan (x − y ) adalah faktor-faktor = ab, a ≥ b ≥ 1, maka dapat ditulis n
=
a
+b
2
2
−
a
−b 2
dari n . Sebaliknya
2 .
Karena n ganjil maka a dan b harus ganjil (mengapa?), oleh karena itu
a+b 2
dan
a−b 2
taknegatif.
Bilangan bulat dapat difaktorkan bhb ia dapat disajikan sebagai selisih kuadrat bil taknegatif
Julan HERNADI
Teorema Fermat dan Wilson
Algoritma 2
−n = y2
1
Tulis x
2
Tentukan k bilangan bulat pertama dimana k
3
Urutkan bilangan berikut k
2
2
≥n
− n, (k + 1)2 − n, (k + 2)2 − n, (k + 3)2 − n, · · ·
hingga langkah ke m sehingga
(k + m)2 − n
adalah bilangan
kuadrat. Example Faktorkan bilangan n
= 119143.
Penyelesaian.
≥ 119143. Cek! 3452 = 119025, 2 346 = 119716. Ambil k = 346. 2 Urutkan bilangan (k + m ) − n , m = 0, 1, 2, · · · . Hasilnya Menentukan k sehingga k
2
sebagai berikut:
Julan HERNADI
Teorema Fermat dan Wilson
Algoritma (lanjutan...)
346 347 348 349 350 351 352
2
− n = 573
2
− n = 1266
2
− n = 1961
2
− n = 2658
2
− n = 3375
2
− n = 4058
2
− n = 4761
= 6 sudah menghasilkan bil kuadrat yaitu (346 + 6) − 119143 = 4761 = 692 . Diperoleh x = 352,y = 69. Ternyata sampai pada m 2
Faktorisasi yang diperoleh adalah 119143
= (x + y )(x − y ) = (352 + 69)(352 − 69) = 421 · 283. Julan HERNADI
Teorema Fermat dan Wilson
Ciri bilangan kuadrat: Angka terakhirnya kemungkinannya 0, 1, 4, 5, 6 dan 9 (mengapa?) Dua angka terakhirnya ada 22 kemungkinan, temukan angka berapa saja! Petunjuk: Gunakan modulo 10 untuk mendeteksi kemungkinan 1 angka terakhir, dan modulo 100 untuk 2 angka terakhir. Latihan 1: Faktorkan bilangan 2027651281dengan metoda Fermat! Lengkapi keterangan setiap langkahnya! Metoda faktorisasi Fermat akan sangat efektif jika selisih magnitud kedua faktornya kecil. Example Faktorkan bilangan n
= 23449.
Mulailah dengan k
= 154
maka
hanya dibutuhkan 2 langkah, diperoleh faktorisasi yang dimaksud adalah 23449
= 179 · 131. Julan HERNADI
Teorema Fermat dan Wilson
Generalisasi metoda faktorisasi Fermat Pada metoda sebelumnya, bilangan bulat x dan y memenuhi n
= x 2 − y 2.
Sekarang x dan y lebih umum, yaitu cukup memenuhi x
Misalkan d
2
= gcd(x − y , n)
≡ y 2 (mod n).
atau d
= gcd(x + y , n), maka d |n. < d < n? Dengan p < q maka kemungkinan d
Permasalahannya, apakah d faktor sejati, yaitu 1 asumsi n
= pq , p , q
prima dengan
adalah 1, p , q atau pq . x
2
≡ y 2 (mod n) → pq |(x − y )(x + y )
Lemma Euclid→ p dan q membagi salah satu faktornya. Bila yang terjadi adalah
|(x − y ) p |(x + y ) p
Situasi
dan q |(x
− y ) → pq |(x − y ) → x ≡ y (mod n), atau dan q |(x + y ) → pq |(x + y ) → x ≡ −y (mod n ). dimana x ≡ ±y (mod n ) dikesampingkan. Jadi, d adalah
salah satu p atau q .
Julan HERNADI
Teorema Fermat dan Wilson
Example Kita ingin memfaktorkan n 579
2
≡ 182 (mod
= 2189
dengan memperoleh
2189). Hitung gcd masing-masing, yaitu
gcd(579 − 18, 2189)
= gcd(561, 2189) = 11
gcd(579 + 18, 2189)
= gcd(597, 2189) = 199
maka diperoleh 2189
= 11 · 199. 2
Bagaimana mendapatkan 579
≡ 182 (mod
2189)? Jelaskan
langkah-langkahnya?
Julan HERNADI
Teorema Fermat dan Wilson
Metoda Kraitchik (1920) Idenya adalah mencari bilangan x1 , x2 , · · · , xk sehingga
(x1 − n) · · · (xk − n) bil kuadrat, katakan y 2 . Akibatnya dapat 2 2 ditulis (x1 · · · xk ) ≡ y (mod n ). Ini menghasilkan faktor taksejati n seperti sebelumnya. Example Kita akan memfaktorkan n Dimulai dari k
= 112.
= 12499.
2
Inspeksi awal 112
= 12544.
Tidak diurutkan seperti metoda Fermat,
tetapi cukup 112 117 121
2
− n = 45 → 1122 ≡ 32 · 5(mod 2
12499)
2
− n = 1190 → 117 ≡ 2 · 5 · 7 · 17(mod
2
2
12499)
2
− n = 2142 → 121 ≡ 2 · 3 · 7 · 17(mod
12499)
Kita kalikan hasil-hasil ini diperoleh
(1122 · 1172 · 1212 ) ≡ (2 · 32 · 5 · 7 · 17)2 (mod 10710(mod 12499)→gagal ? Julan HERNADI
124999)
→ 1585584 ≡
Teorema Fermat dan Wilson
Example (lanjutan) Ambil kemungkinan lain, mis 113 127
2
≡ 2 · 5 · 33 (mod
2
≡ 2 · 3 · 5 · 112 (mod
12499) 12499)
(113 · 127)2 ≡ (2 · 32 · 5 · 11)2 (mod 12499) → (mod 12499). Karena 1852 6= ±990(mod 12499)
maka diperoleh 1852
2
≡ 990
2
maka kita berhasil. Hitung gcd masing-masing seperti sebelumnya diperoleh faktorisasi 12499
= 29 · 431.
Julan HERNADI
Teorema Fermat dan Wilson
Teorema Litle Fermat Theorem Misalkan p prima dan andaikan p
Ilustrasi: p untuk a
=
=3
maka untuk a
=5
-a
maka a
p −1
3
−1 6 tidak berlaku bahwa 6
−1
≡ 1(mod 3), = 36 ≡ 1(mod 3).
berlaku 5 3
≡ 1(mod p ). tetapi
Proof. Kumpulkan p − 1 kelipatan pertama a, yaitu V
= {a, 2a, 3a, · · · , (p − 1)a}.
Diperoleh fakta
Tidak ada anggota V yang kongruen satu sama lainnya (mengapa?) Tidak ada anggota V yang kongruen dengan nol (mengapa ?) Maka setiap anggota V pasti kongruen modulo p terhadap salah satu 1, 2, · · · , p − 1. Kalikan semua kongruensi ini diperoleh a
· 2a · 3a · · · · · (p − 1)a ≡ 1 · 2 · 3 · · · · · (p − 1)(mod p ) → p −1 ≡ 1(mod p ) (Why p) → a
p −1 (p − 1)! ≡ (p − 1)!(mod a
Julan HERNADI
Teorema Fermat dan Wilson
?).
Akibat Teorema Fermat Corollary Bila p prima maka a
p
≡ a(mod p )untuk
sebarang bil bulat a.
Proof. Ada 2 kemungkinan: bila p |a maka pernyataan otomatis berlaku. Bila p
-a
maka mk dg Teorema Fermat diperoleh a
p −1
≡ 1(mod p ).
Kalikan kedua ruas dengan a, Akibat ini terbukti. Example
a
= 5 → 5 - 11 → 5
10
38
≡ 4(mod 11). Ambil p = 11, ≡ 1(mod 11). Dengan fakta 52 ≡ 3(mod
Kita akan membuktikan 5
maka diperoleh 5
38
= 510·3+8 = (510 )3 (52 )4 ≡ 1 · 34 (mod ≡ 4(mod
Julan HERNADI
11)
11).
Teorema Fermat dan Wilson
11)
Uji Primalitas dengan Teorema Fermat
Bila kongruensi a
n
≡ a(mod n)
tidak berlaku untuk suatu a maka
dipastikan n komposit. Example
= 117. Ambil a = 2. Tulis 2117 = 7 2 = 128 ≡ 11(mod 117) maka berlaku Misalkan n
2
117
7
16
· 25 .
≡ 1116 · 25 ≡ (121)8 · 25 ≡ 48 · 25 ≡ 221 (mod =
2
7
Karena
117).
3
≡ 113 = 121 · 11 ≡ 4 · 11 ≡ 44(mod 117). 117 Akhirnya diperoleh 2 ≡ 44 2(mod 117). Jadi disimpulkan komposit, faktanya 117 = 9 · 13.
Tetapi 2
21
2
Julan HERNADI
Teorema Fermat dan Wilson
117
