BAB 4. TEOREMA FERMAT DAN WILSON

BAB 4. TEOREMA FERMAT DAN WILSON Julan HERNADI1 Program Studi Pendidikan Matematika Universitas Muhammadiyah, Ponorogo

May 25, 2014

Julan HERNADI

Teorema Fermat dan Wilson

Metoda Faktorisasi Fermat (1643) Biasanya pemfaktoran n melalui tester, yaitu faktor prima yang p 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 a b itu a+b 2 dan 2 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 k 2 Urutkan bilangan berikut k2

n, (k + 1)2

n, (k + 2)2

n, (k + 3)2

hingga langkah ke m sehingga (k + m)2 kuadrat.

n n, · · ·

n adalah bilangan

Example Faktorkan bilangan n = 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

2

348

n = 1961

3492

n = 2658

2

n = 3375

2

n = 4058

2

n = 4761

350 351 352

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: Digit terakhirnya kemungkinannya 0, 1, 4, 5, 6 dan 9 (mengapa?) Dua digit terakhirnya ada 22 kemungkinan, temukan angka berapa saja! Petunjuk: Gunakan modulo 10 untuk mendeteksi kemungkinan digit terakhir, dan modulo 100 untuk mendeteksi 2 digit terakhir. Latihan 1: Faktorkan bilangan 2027651281 dengan 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 “Litle” Fermat Theorem Misalkan p prima dan andaikan p - a maka ap

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) ! ap 1 (p 1)! ⌘ (p 1)!(mod p) ! ap 1 ⌘ 1(mod p) (Why ?). Julan HERNADI


Akibat Teorema Fermat Corollary Bila p prima maka ap ⌘ 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, a = 5 ! 5 - 11 ! 510 ⌘ 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 a maka dipastikan n komposit. 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). 3

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.

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, define set E = {1, 2, · · · , p 1}. For any a 2 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 , define 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 2 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 satisfied 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: ax 2 + bx + c ⌘ 0(mod n), where a 0(mod n). Theorem x 2 + 1 ⌘ 0(mod p), p odd prime has solution

!p ⌘ 1(mod 4).

Proof. Refer to textbook! Examples 1.

Julan HERNADI


BAB 4. TEOREMA FERMAT DAN WILSON

Recommend Documents