TEOREMA FERMAT
Perhatikan barisan bilangan : 4,8,12,16,20,24.
Bilangan-bilangan dalam barisan ini kongruen modulo 7 berturut-turut dengan 4,1,5,2,6,3.
Tampak pada barisan bilangan terakhir ini, suku-sukunya adalah bilangan-bilangan asli kurang dari 7, yaitu unsur-unsur dari himpunan residu terkecil modulo 7.
Coba, tentukan residu-residu terkecil modulo 8 dari bilangan-bilangan dalam barisan :
3,6,9,12,15,18,21.
residu-residu terkecil modulo 8 dari bilangan-bilangan dalam barisan itu berturut-turut adalah 3,6,1,4,7,2,5.
Tampak pula bahwa residu-residu terkecil dari bilangan-bilangan dalam barisan tadi adalah semua bilangan asli kurang dari 8.
Residu-residu terkecil mod 9 dari bilangan-bilangan dalam barisan : 3,6,9,12,15,18,21,24.
Berturut-turut adalah
3,6,0,3,6,0,3,6
Tampak disni bahwa residu-residu terkecilnya ternyata tidak memuat semua bilangan asli yang kurang dari 9.
Contoh-contoh tersebut merupakan suatu ilustrasi dari teorema berikut ini :
Teorema 6.1:
Dengan perkataan lain, Teorema 6.1 dapat dikatakan bahwa jika (a, m)=1, maka setiap bilangan bulat kongruen modulo m dengan tepat satu dari 0, a, 2a, 3a,....(m-1)a.
Ingat bahwa setiap bilangan bulat akan kongruen modulo m dengan tepat satu dari o, 1, 2, 3, 4,....(m-1).
Bukti Teorema 6.1 :
Perhatikan barisan bilangan : a, 2a, 3a,....(m-1)a,....(1)
Bilangan-bilangan pada barisan ini tidak ada satupun yang kongruen modulo m dengan 0 (nol). Mengapa? Selanjutnya, kita harus membuktikan bahwa bilangan-b ilangan (suku-suku) dalam barisan (1) masing-masing kongruen modulo m dengan tepat satu dari 1,2,3,...,(m-1).
Andaikan ada dua suku dari barisan (1) yang kongruen modulo m, misalnya:
Ra≡sa(mod m)dengan 1 ≤r < s < m
Karena (a ,m ) = 1, maka kita dapat melenyap kan a dari kengkorueanan itu , sehingga diperoleh
r ≡ s (mod m).
Tetapi,karena ra dan sa adalah suku-suku dari barisan (1), maka r dan s adalah residu-residu terkecil modulo m, sehingga r = s. Hal ini kontradiksi dengan pengandaian bahwa 1≤ r < s < m, maka pengandaian tersebut tidak benar
Jika tidak ada dua suku dari barisan (1) yang kongruen modulo m,
Ini berarti bahwa suku-suku dalam barisan (1) masing-masing Kongruen modulo m dengan tepat satu dari 1,2,3. . . (m-1).
Perhatikan barisan bilangan : 4,8,12,16,20,24.
Residu-residu terkecil mod 7 dari masing-masing suku dari barisan ini adalah :
4 ≡ 4 (mod 7)
8 ≡ 1 (mod 7)
12 ≡ 5 (mod 7)
16 ≡ 2 (mod 7)
20 ≡ 6 (mod 7)
24 ≡ 3 (mod 7)
Tampak pada enam kekongruenan tersebut bahwa residu-residu terkeci modulo 7 dari suku-suku pada barisan : 1,2,3,4,5,6.
Jika semua bilangan pada ruas kiri dari 6 kekongruenan imi di kalikan, maka hasil nya akan kongruen mod 7 dengan hasil kali semua bilangan pada ruas kanan nya,yaitu:
4.8.12.16.20.24 ≡ 4.1.5.2.6.3 (mod 7)
4^6 (1.2.3.4.5.6) ≡ 1. 2. 3. 4. 5. 6. (mod 7)
4^6 .6! ≡ 6! (mod 7)
4^(6 ) ≡ 1 (mod 7)
Dengan cara seperti itu, cobalah tunjukkan bahwa :
a) 5^6 ≡ 1 (mod 7)
b) 3^10 ≡ 1(mod 11)
c) 4^12 ≡ 1 (mod 13)
d) 8^4 ≡ 1 (mod 5)
e) 〖13〗^16 ≡ 1 (mod 17)
Contoh-contoh tersebut merupakan penerapan dari Teorema fermat berikut ini :
Teorema 6.2 : (Teorema fermat ).
Bukti:
Ambil sembarang bilangan prima p dan bilangan bulat a sedemikian (a, p) =1, maka menurut teorema 6.1. residu-residu terkecil mod p dari a,2a,3a, ......, (p-1)a adalah suatu permulasi dari 1, 2, 3, ...... (p-1) sehingga hasil kalinya akan kongruen mod p juga yaitu :
a, 2a, 3a, .. .(p-1)a ≡ 1.2.3.... (p-1) (mod p)
a^(p-1) (1.2.3....(p-1) ) ≡ (p-1)! (mod p)
a^(p-1) (p-1)! ≡ (p-1)! (mod p)
Karena p dan (p-1)! Saling prima (mengapa.?), maka kita dapat melenyapkan (P-1)! Dari kekongruenan terakhir ini , sehingga diperoleh a^(p-1) ≡ 1 (mod p)
Teorema tersebut dapat dinyatakan lebih umum dengan meniadakan ketentuan (a,p) =1 sebagai berikut :
Teorema 6.3
Bukti :
Ambil sembarang bilangan prima p dan sembarang bilangan bulat a, maka (a,p) = 1, atau (a, p) =p, apakah ada kemungkinan lain antara FPB dari a dan p? Jika (a p) = 1, maka menurut Teorema 6.2 diperoleh bahwa a^(p-1) ≡ 1(mod p).
Jika (a, p) = p, maka p│a, sehingga a ≡ 0 (mod p) dan a^p ≡ a (mod p) pula.
Jadi a^p ≡ a (mod p).
Bukti lain dari teorema 6.3 dengan menggunakan induksi matematik pada a.
Jika a = 1, maka pernyataan 1^p ≡ 1 (mod p) jelas benar. Demikian pula, jika diambil a = 0.
Selajutnya di asumsikan a^p ≡ a (mod p) benar untuk suatu bilangan bulat positif a, dan harus ditunjukkan benar untuk (a+1). Yaitu 〖(a+1)〗^p ≡ a + 1 (mod p) hal ini ditunjukkan sebagai berikut:
Menurut teorema binomial, maka :
〖(a+1)〗^p = a^p +(█(p@1)) a^(p-1) +(█(p@2)) a^(p-2) +...+(█(p@k)) a^(p-k) +...+(█(p@p-1))a+1
Ingat bahwa (█(p@k)) = p!/(k(p-k)) = (p(p-1)(p-2)…(p-k+1))/(1.2.3…k), karena p suatu bilangan prima, maka
p│(█(p@k)) berarti (█(p@k)) ≡ 0 (mod p) untuk 1≤k≤p-1.
Jadi kita memperoleh bahwa :
〖(a+1)〗^p = a^p +0 + 0...+0+1(mod p)
〖(a+1)〗^p = a^p +1 (mod p)
Karena a^p ≡ a(mod p) maka 〖(a+1)〗^p≡ a+1 (mod p).
Dengan induksi matematik pada a kita telah membuktikan bahwa a^p ≡ a (mod p) untuk setiap bilangan asli a. Selanjutnya jika a bilangan bulat negatif, bukan lagi menjadi persoalan, sebab untuk setiap bilangan bulat negatif a berlaku bahwa a ≡ r (mod p) dengan 0≤ r < p-1. Jadi a^p ≡ r^p ≡ r ≡ a (mod p).
Teorema fermat mempunyai banyak kegunaan, khususnya dalam mengembangkan teori bilangan.
Contoh 6.1 :
Berapakah sisa pembagian 5^38 oleh 11 ?
Jawab :
Menurut teorema fermat, 5^10 ≡ 1 (mod 11), Maka
5^38 ≡ 5^(10 3+8) ≡ 〖(5〗^10)^3 〖(5〗^2)^4 ≡ 1^3.3^4 ≡ 81 ≡ 4 (mod 11)
Jadi 5^38 : 11 bersisa 4
Bacalah lg dengan seksama teorema 6.3 tersebut kontra posisi dari teorema itu benar pula, yaitu : jika untuk suatu bilangan bulat a,a^p (mod p) maka p bukan lah bilangan prima.
Hal ini menunjujkkan bahwa teorema fermat dapat digunakan untuk menguji apakah suatu bilangan bulat n merupakan bilangan nkomposit atau bukan.
Contoh 6.2
Apakah 117 suatu bilangan prima.??
Jawab :
Untuk memeriksa ini dipilih bilangan bulat positif yg cukup kecil, misalkan 2, slnjutnya priksa apakah2^117 ≡2 (mod 117)
2^117 = 2^(7.16+5) = (2^7)^16.2^5
2^7 = 128 ≡ 11 (mod 117). Maka
2^117 ≡ 〖(11)〗^(16 ) . 2^5 (mod 117)
≡〖(121)〗^8 .2^5 (mod 117)
≡4^8 2^5 (mod 117)
≡2^21 (mod 117)
≡(2^7)^3 (mod 117)
≡〖11〗^3 (mod 117)
≡121 . 11 (mod 117)
≡4 . 11 (mod 117)
≡44 (mod 117)
Sehingga diperoleh bahwa 2^117 = 44 ≠ 2 (mod 117).
Hal ini brarti bahwa 117 adalah bilangan komposit dan kenyataan bahwa 117 = 13.9
Contoh 6.3
Tampa menggunakan teorema fermat, tunjukkan bahwa 3^16 ≡1 (mod 17)
Jawab : 3^3 ≡27 ≡10 (mod 17 ) dikuadratkan
3^6 ≡100 (mod 17 )
3^6 ≡ -2 (mod 17 ) dikuadratkan
3^12 ≡4 (mod 17 )
Sehingga 3^16 ≡ 3^12.3^3.3 ≡4 .10 .3 (mod 17 )
120 ≡1 (mod 17 )
Jadi 3^16 ≡1 (mod 17 )
Perhatikan kembali teorema fermat di atas. Perlu ditekankan disini bahwa konvers dari teorema tersebut tidak benar, yaitu :
Jika a^(n-1) ≡1 (mod n) untuk suatu bilangan bulat a, maka n tidak perlu suatu bilangan prima.
Untuk melanjutkan contohnya, terlebih dahulu kita bicarakan teorema berikut ini yang merupakan akibat dari teorema fermat.
Teorema 6.4
Bukti :
Menurut Teorema 6.3, karena p suatu bilangan prima maka (a^q)^p ≡ a^q ( mod p). Selanjutnya, karena diketahui bahwa a^(q )≡a (mod p), maka kekongruenan tersebut menjadi a^pq≡a (mod p). ini brarti bahwa p │ (a^pq- a)..............(1)
Menurut Teorema 6.3 lagi. Karena q suatu bilangan prima maka (a^p)^q≡ a^p (mod q). Selanjutnya, karena diketahui bahwa ap≡ a (mod q).maka kekongruenan tersebut menjadi apq ≡a(mod q).ini beari bahwa q │(apq –a).........................(2)
Dari (1) dan (2) disimpulkan bahwa pq │(apq-a)dan dapatdinyatakan sebagai apq ≡ a
(mod pq).
Contoh 6.4 :
Tunjukan bahwa 2340≡ 1(mod 341)
Jawaban :
341 =11.31
210 =1024 =31.33+1,sehingga
210 ≡1 (mod 31)
211 ≡2 (mod 31)
210 =1024 =31.33 + 1,sehingga
210 ≡ 1 (mod 11),jika kedua ruas dipangkatkan 3,maka: (210)3 ≡ 13 (mod 11)
230 ≡ 1 (mod 11)
231 ≡ 2 (mod 11)
Menurut teorema 6.4 ,dari 211 ≡ 2 (mod 31) dan 231 ≡ 2 (mod 11), maka 211.31 ≡ 2(mod 11) dan karena 211.31 ≡ 2 (mod 31) maka 211. 31 ≡2 (mod 11.31) yaitu:
234 ≡ 2 (mod 341)
Jika kedua ruas dibagi dua,maka diperoleh 2340 ≡ 1(mod 341) dan tidak dapat disimpulkan bahwa 341 suatu bilangan prima.dalam sejarahnya, bilangan berbentuk 2n -2 ditemukan oleh matematikawan cina pada 25 abad yang lalu dan menyatakan bahwa :
N suatu bilangan prima jika dan hanya jika n │2n -2 dalam kenyataan , kriteria ini benar untuk semua bilangan prima n < 345 .dan pada contoh diatas,kita memperoleh fakta bahwa 341│2341 -2,walaupun 341 bukan bilangan prima.selanjutnya,bilangan komposit n sedemikian hingga n│(2n -2) disebut bilangan prima semu (pseudoprima). ada tak terhingga banyaknya bilangan prima semu.empat bilangan prima semupertana adalah341,561,645, dan 1105.
