BAB 4. TEOREMA FERMAT DAN WILSON

BAB 4. TEOREMA FERMAT DAN WILSON

Julan HERNADI1 Program Studi Pendidikan Matematika Universitas Muhammadiyah, Ponorogo

June 24, 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 . Karena dapat ditulis n

= (x + y )(x − y )

maka (x + y ) dan (x − y ) adalah faktor-faktor dari n. Sebaliknya bila n = ab, a ≥ b ≥ 1, maka dapat ditulis n

=

a

+b

2

2

−

a

−b

2

2 .

Karena n ganjil maka a dan b harus ganjil (mengapa?), oleh karena itu a+2 b dan a−2 b taknegatif. Bilangan bulat dapat difaktorkan bhb ia dapat disajikan sebagai selisih kuadrat bil taknegatif

Julan HERNADI


Algoritma 1 2 3

Tulis x 2 − n = y 2 Tentukan k bilangan bulat pertama dimana Urutkan bilangan berikut k

2

k

2

≥n

− n, (k + 1)2 − n, (k + 2)2 − n, (k + 3)2 − n, · · ·

hingga langkah ke kuadrat. Example Faktorkan bilangan

n

m

sehingga (k + m)2 − n adalah bilangan

= 119143.

Penyelesaian. Menentukan k sehingga k 2 ≥ 119143. Cek! 3452 = 119025, 3462 = 119716. Ambil k = 346. Urutkan bilangan (k + m)2 − n, m = 0, 1, 2, · · · . Hasilnya sebagai berikut: Julan HERNADI


Algoritma (lanjutan...)

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 bil 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. Julan HERNADI


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


Generalisasi metoda faktorisasi Fermat

Pada metoda sebelumnya, bilangan bulat x dan y memenuhi 2 2 n = x − y . Sekarang x dan y lebih umum, yaitu cukup memenuhi x

2

≡ y 2 (mod n).

Misalkan d = gcd(x − y , n) atau d = gcd(x + y , n), maka d |n. Permasalahannya, apakah d faktor 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

2

≡ y 2 (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 ) → x ≡ y (mod n ), atau p |(x + y ) dan q |(x + y ) → pq |(x + y ) → x ≡ −y (mod n ). Situasi dimana x ≡ ±y (mod n) dikesampingkan. Jadi, d adalah salah satu p atau q . Julan HERNADI


Example Kita ingin memfaktorkan n = 2189 dengan memperoleh 5792 ≡ 182 (mod 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. Bagaimana mendapatkan 5792 ≡ 182 (mod 2189)? Jelaskan langkah-langkahnya?

Julan HERNADI


Metoda Kraitchik (1920)

Idenya adalah mencari bilangan x1 , x2 , · · · , xk sehingga (x1 − n) · · · (xk − n) bil kuadrat, katakan y 2 . Akibatnya dapat ditulis (x1 · · · xk )2 ≡ y 2 (mod n). Ini menghasilkan faktor taksejati n seperti sebelumnya. Example Kita akan memfaktorkan n = 12499. Inspeksi awal 1122 = 12544. Dimulai dari k = 112. Tidak diurutkan seperti metoda Fermat, tetapi cukup 1122 − n = 45 → 1122 ≡ 32 · 5(mod 12499) 1172 − n = 1190 → 1172 ≡ 2 · 5 · 7 · 17(mod 12499) 1212 − n = 2142 → 1212 ≡ 2 · 32 · 7 · 17(mod 12499) Kita kalikan hasil-hasil ini diperoleh (1122 · 1172 · 1212 ) ≡ (2 · 32 · 5 · 7 · 17)2 (mod 124999) → 1585584 ≡ 10710(mod 12499)→gagal ? Julan HERNADI


Example (lanjutan) Ambil kemungkinan lain, mis 1132 ≡ 2 · 5 · 33 (mod 12499) 1272 ≡ 2 · 3 · 5 · 112 (mod 12499) maka diperoleh (113 · 127)2 ≡ (2 · 32 · 5 · 11)2 (mod 12499) → 18522 ≡ 9902 (mod 12499). Karena 1852 6= ±990(mod 12499) maka kita berhasil. Hitung gcd masing-masing seperti sebelumnya diperoleh faktorisasi 12499 = 29 · 431.

Julan HERNADI


Teorema Litle Fermat

Theorem Misalkan p prima dan andaikan p

-a

maka a

p −1

≡ 1(mod p ).

Ilustrasi: p = 3 maka untuk a = 5 berlaku 53−1 ≡ 1(mod 3), tetapi untuk a = 6 tidak berlaku bahwa 63−1 = 36 ≡ 1(mod 3). 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 (p − 1)! ≡ (p − 1)!(mod p ) → ap −1 ≡ 1(mod p ) (Why ?). a Julan HERNADI


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 ap−1 ≡ 1(mod p ). Kalikan kedua ruas dengan a, Akibat ini terbukti. Example Kita akan membuktikan 538 ≡ 4(mod 11). Ambil p = 11, 10 a = 5 → 5 - 11 → 5 ≡ 1(mod 11). Dengan fakta 52 ≡ 3(mod 11) maka diperoleh 538 = 510·3+8 = (510 )3 (52 )4 ≡ 1 · 34 (mod 11) ≡ 4(mod 11). Julan HERNADI


Uji Primalitas dengan Teorema Fermat

Bila kongruensi an ≡ a(mod n) tidak berlaku untuk suatu dipastikan n komposit.

a

maka

Example Misalkan n = 117. Ambil a = 2. Tulis 2117 = 27 27 = 128 ≡ 11(mod 117) maka berlaku

16

· 25 . Karena

2117 ≡ 1116 · 25 ≡ (121)8 · 25 ≡ 48 · 25 ≡ 221 (mod 117). Tetapi 221 = 27 ≡ 113 = 121 · 11 ≡ 4 · 11 ≡ 44(mod 117). Akhirnya diperoleh 2117 ≡ 44 2(mod 117). Jadi disimpulkan 117 komposit, faktanya 117 = 9 · 13. 3

Julan HERNADI


The Wilson Theorem

Historical notes: Announced in 1770 by Edward Waring (1741-1793), conjecture by John Wilson (his former student), proved by Lagrange in 1771. Theorem p prime

→ (p − 1)! ≡ −1(mod p ),

or written as p

|(p − 1)! + 1.

Proof. Cases p = 2 and p = 3 as being evident. For p > 3, dene set E = {1, 2, · · · , p − 1}. For any a ∈ E , the congruence ax ≡ 1(mod p ) always has a unique solution a0 (why ?). Since a0 solution then 1 ≤ a0 ≤ p − 1 and aa0 ≡ 1(mod p ). The following statement holds For aa0 ≡ 1(mod p ): a = 1 or a = p − 1 ←→ a = a0 . (why?)

Julan HERNADI


Proof (cont...)

Equivalently, for aa0 ≡ 1(mod p ): a 6= 1 and a 6= p − 1 ←→ a 6= a0 . Deleting these elements from E , dene E1 = {2, 3, · · · , p − 2} consist of p − 3 elements, an even integer (why ?). There are p−2 3 pairs (a, a0 ) where a, a0 ∈ E1 and a 6= a0 such that aa0 ≡ 1(mod p ). Multiply together and rearrange the factors, we obtain 2 · 3 · 4 · · · · · (p − 2) ≡ 1(modp ). (why???) Finally, multiply both sides by p − 1, theorem is proved. (why??) Convers of Wilson's theorem also holds: Theorem (n − 1)! ≡ −1(mod n) → n prime. Proof. Supposed n composite, n has a factor d where 2 ≤ d ≤ n − 1. It must be satised d |(n − 1)!. On the other hand, n|(n − 1)! + 1. It implies d |(n − 1)! + 1 (why???). Since d |(n − 1)! + 1 and d |(n − 1) then it neccesary d |1 (why ???). The last statement is contra. Julan HERNADI


Primality test using the Wilson's theorem is more theoretical than practical, because as n increases, (n − 1)! rapidly becomes unmanageable in size. Example Take p = 13 and E1 = {2, 3, · · · , 11}, then we have p−2 3 = 5 pairing of numbers where each product is congruent to 1 modulo 13, i.e. 2 · 7 ≡ 1(mod 13), 3 · 9 ≡ 1(mod 13), 4 · 10 ≡ 1(mod 13), 5 · 8 ≡ 1(mod 13), 6 · 11 ≡ 1(mod 13). Finally, it holds 11! ≡ 1(mod 13).

Julan HERNADI


Application of Wilson Theorem

Quadratic Congruences: a 0(mod n ). Theorem 2 x + 1 ≡ 0(mod p ),

ax

2

+ bx + c ≡ 0(mod n), where

p odd prime has solution

Julan HERNADI

←→p ≡ 1(mod 4).


BAB 4. TEOREMA FERMAT DAN WILSON

Recommend Documents