teori fermat

PEMBAHASAN

A.      Teorema Fermat

Menguji keprimaan suatu bilangan bulat n dengan cara membaginya dengan sejumlah bilangan prima yang    tentu kurang efektif untuk n yang besar, karena kita harus menentukan terlebih dahulu semua bilangan  prima yang lebih kecil dari . Terdapat metode lain yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat yang dikenal dengan nama teorema Fermat (biasanya disebut dengan Fermat’s little theorem).

Sebelum teorema Fermat dijelaskan, teorema berikut perlu diperhatikan.

Teorema 1 Jika (a,m)=1 maka sisaan terkecil suatu mod m barisan: a, 2a, 3a,..., (m-1)a adalah suatu permutasi dari 1,2,3,...,(m-1)

Dengan perkataan lain, berdasarkan teorema 1 dapat dikatakan bahwa jika (a,m)=1 maka  tiap bilangan bulat kongruen modulo m dengan tepat satu dari 0, a, 2a,..., (m-1)a.

Perlu diingat bahwa himpunan tiap bilangan bulat akan kongruen modulo m dengan tepat satu dari 0,1,2,3,..., (m-1).

Bukti:

·         Perhatikan barisan bilangan: a, 2a, 3a, ..., (m-1)a....- (1)

·         Bilangan pada barisan (1) tidak ada satu pun yang kongruen modulo m dengan 0 (nol).

·         Selanjutnya, kita harus membuktikan bahwa bilangan 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  .

·         Karena (a,m) 1, maka kita dapat menggunakan sifat penghapusan a dari kekongruenan itu, sehingga diperoleh r  s(mod m).

·         Tetapi, karena ra dan sa adalah suku-suku dari barisan (1), maka r dan s adalah sisaan terkecil modulo m, sehingga r  s.

·         Hal ini kontradiksi dengan pengandaian bahwa  , sehingga pengandaian tersebut tidak benar.

·         Jadi, tidak ada dua bilangan dari barisan (1) yang kongruen modulo m. Ini berarti bahwa bilangan dalam barisan (1) masing-masing kongruen modulo m dengan tepat satu dari 1, 2, 3,.., (m-1). Terbukti.

Teorema 2 (Teorema kecil Fermat) Jika p suatu bilangan prima dan (a,p) =1 untuk suatu bilangan bulat a, maka ap-1  1(mod p).

 

Teorema ini dapat dinyatakan dengan cara lain, “jika p adalah bilangan prima dan a prima relatif  dengan p maka a^p-1 – 1 dapat dibagi oleh p”.

Bukti:

·         Ambil sembarang bilangan prima p dan bilangan bulat a sedemikian (a,p) =1.

·         Menurut teorema 1, residu (sisa) terkecil mod p dari a, 2a, 3a, ..., (p-1), a adalah suatu permutasi dari 1, 2, 3, ...,(p-1) , sehingga hasilkalinya akan kongruen mod p juga, yaitu:

a.2a.3a....(p-1)a   (mod p).

Dengan demikian,

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, maka kita dapat menggunkan sifat penghapusan (p-1)  dari kekongruenan terakhir ini, sehingga diperoleh

a^p-1  1 (mod p), dimana a^p-1  1 (mod p) bermakna sama   (a^p-1 - 1).

Terbukti

Contoh 2.1:

Jika p=5 dan a=2 berarti (2,5)=1

maka a^p-1 – 1 = 2^5-1 – 1= 2⁴ – 1 = 16 – 1 = 15

15 dapat dibagi oleh p=5 atau dapat ditulis 16  1 (mod 5).

Teorema Fermat tersebut diatas dapat dinyatakan secara lebih umum dengan menghilangkan syarat (a,p)=1 sebagai berikut.

Teorema 3 Jika p suatu bilangan prima, maka ap  a(mod p) untuk himpunaniap bilangan bulat a.

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 p|a, sehingga a0(mod p) dan a^p0(mod p) pula. Jadi, a^p a(mod p). Terbukti.

Bukti alternatif:

Teorema 3 dapat digunakan dengan menggunakan induksi matematika pada a sebagai berikut:

·         Jika a = 1, maka pernyataan 1^p  1(mod p) jelas benar.

·         Demikian pula jika diambil a=0, pernyataan pun benar.

·         Selanjutnya, diasumsikan a^p  a(mod p) benar untuk suatu bilangan bulat positif a.

·         Kemudian, harus ditunjukkan bahwa untuk a+1, yaitu (a+1)p  a+1 (mod p) juga benar. Hal ini ditunjukkan sebagai berikut. Menurut teorema binomial, maka:

(a+1)^p = a^p + a^p-1 + a^p-2 + ... + a^p-k + ... + a+1

·         Karena p suatu bilangan prima, maka p | berarti,

= 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 demikian induksi matematika pada a, dapat disimpulkan bahwa, jika p suatu bilangan prima, maka :

a^p  a(mod p) untuk setiap bilangan bulat a.

·         Selanjutnya, jika a suatu bilangan bulat negatif, bukan lagi menjadi persoalan, sebab untuk setiap bilangan bulat negatif a berlaku bahwa a  r(mod p) dengan 0rp-1. Jadi, a^p  r^p r a(mod p) . Terbukti.

Contoh 3.1:

Ambil a=8 dan p=3, (a,p)=1 atau p – a. Dengan demikian, diperoleh

a^p-1 = 8^3-1 = 8² = 64. Tetapi, 64  1(mod 3) (sesuai dengan teorema 2). Menurut teorema 3,

8³ = 512 dan 512 8(mod 3).

Teorema Fermat mempunyai banyak kegunaan khususnya dalam mengembangkan teori bilangan. Salah satu kegunaan teori Fermat dijelaskan dalam contoh berikut.

Contoh 3.2:

Berapakah sisa pembagian 5³⁸ oleh 11 ?

Penyelesaian:

Menurut teori Fermat, 5¹⁰  1(mod 11), yaitu dari hasil a^p-1  1(mod p).

Untuk a=5 dan p=1, (a,p) = 1.

Maka, 5³⁸ = 5^(10)(3)+8 = (5¹⁰)³(5²)⁴, sehingga

5³⁸  (1)³(3)⁴(mod 11)

       81(mod 11)

        4(mod 11)

Jadi, 5³⁸ dibagi 11 bersisa 4.

Kontraposisi dari teorema 3 juga benar, yaitu jika untuk suatu bilangan bulat a, dengan a^pa(mod p) maka p bukan bilangan prima.

Jadi, teori Fermat dapat pula digunakan untuk menguji apakah suatu bilangan bulat merupakan bilangan komposit atau bilangan prima.

Contoh 3.4:

Apakah 117 suatu bilangan prima atau komposit?

Penyelesaian:

Misalkan kita mengambil bilangan bulat a=2 (boleh a bilangan lain). Kita akan memeriksa kebenaran 2¹¹⁷ = 2^7(16)+5 . 2⁵, dan 2⁷ = 12811(mod 117), sehingga 

   2¹¹⁷     (11⁶ . 2⁵)(mod 117)

 121⁸ . 2⁵(mod 117)

             4⁸ . 2⁵(mod 117)

  2²¹(mod 117)

              (2⁷)³(mod 117)

              11³(mod 117)

              121 . 11(mod 117)

              4 . 11(mod 117)

              44 (mod 117)

Jadi, diperoleh 2¹¹⁷  44(mod 117), dan ini berarti 2¹¹⁷  2(mod 117). Dengan demikian, 117 bukan bilangan prima tetapi bilangan komposit. Kenyataan memang 117 = 13 . 9.

Teorema 4 Misalkan p dan q adalah dua bilangan prima yang tidak sama. Jika ap a(mod q) dan aq  a(mod p), maka apq  a(mod pq).

Bukti:

• Menurut teorema 3, (a^p)^q  a^q(mod p) sebab p suatu bilangan prima.
• Selanjutnya, karena diketahui a^q  a(mod p) maka kekongruenan tersebut menjadi (a^q)^p  a (mod p), ini berarti bahwa p  (a^pq - a) …. (1)
• Menurut teorema 3 lagi, (a^p)^q  a^q(mod q) sebab q suatu bilangan prima.
• Selanjutnya karena diketahui bahwa a^p  a(mod q) maka kekongruenan tersebut menjadi a^pq  a(mod q).
• Ini berarti q | (a^pq - a) …. (2)
• Dari (1) dan (2) dapat disimpulkan bahwa pq | (a^pq - a), akibatnya a^pq  a(mod pq).

Teorema 4 menunjukkan bahwa kebalikan pernyataan teori Fermat (teori 2) tidak benar yakni, jika hubungan a^n-1  1(mod n) untuk suatu bilangan bulat a, maka n tidak perlu suatu bilangan prima.

Contoh 4.1:

Tunjukkanlah bahwa 2³⁴⁰  1(mod 341).

Penyelesaian:

Perhatikan bahwa 341 = 31 . 11 dan 2¹⁰ = 1024 = 31 . 33 + 1.

Dengan demikian, 2¹⁰  1(mod 31).

Selanjutnya, 2¹¹ = 2 x 2¹⁰  2(mod 31) dan 2¹⁰ = 1024 = 31 x 3 x 11 + 1,

sehingga 2¹⁰  1(mod 11).

Jika kedua ruas dipangkatkan dengan 3 maka,

 2³⁰  1(mod 11)

 2³¹  2(mod 11).

Menurut teorema 4, 2¹¹  2(mod 31) dan 2³¹  2(mod 11).

Karena 11 dan 31 bilangan prima, maka:

(2¹¹)³¹  2(mod 11 . 31), sehingga

    2³⁴¹  2(mod 341).

Jika kedua ruas dibagi 2, diperoleh 2³⁴⁰   1(mod 341). Tidak dapat disimpulkan bahwa 341 suatu bilangan prima.

Contoh 4.2:

Berapa sisa jika 20⁵⁰ dibagi 7?

Penyelesaian:

Diketahui 20  -1(mod 7), sehingga 20⁵⁰  (-1) ⁵⁰(mod 7) atau 20⁵⁰ 1(mod 7).

Jadi, 20⁵⁰ dibagi 7 bersisa 1.

Contoh 4.3:

Berapa sisa jika 3¹⁹ dibagi 14?

Penyelesaian:

3¹⁹  (mod 14)

    3^{3 x 6 + 1}  (mod 14)

    (3³) ⁶.3¹  (mod 14)

          ( (27) ⁶ x 3)  (mod 14)

 (2 x 14 - 1) ⁶ x 3¹  (mod 14)

 (-1) ⁶ x 3¹  (mod 14)

                              3(mod 14)

Jadi, 3¹⁹   3 (mod 14), sehingga sisa pembagian 3¹⁹ oleh14 adalah 3.

Contoh 4.4:

Berapa sisa jika 3¹⁹⁹⁰ dibagi 41?

Penyelesaian:

       3¹⁹⁹⁰ (mod 41)

      3^{4 x 497 + 2}  (mod 41)

            ((3⁴) ⁴⁹⁷ x 3²)  (mod 41)

           ((81) ⁴⁹⁷ x 3² )  (mod 41)

((2 x 41 - 1) ⁴⁹⁷ x 3²)  (mod 41)

 ((-1) ⁴⁹⁷ x 9)  (mod 41)

   (-9)  (mod 41)

            (41-9)  (mod 41)

          32(mod 41)

Jadi, sisa pembagian 3¹⁹⁹⁰ jika dibagi 41 adalah 32.

Dalam sejarah matematika, minat terhadap bilangan berbentuk 2ⁿ – 2 sudah lama ada. Bilangan berbentuk 2ⁿ – 2 ditemukan oleh matematikawan Cina dan menyatakan bahwa n suatu bilangan prima jika n | (2ⁿ – 2), dan kenyataannya kriteria ini benar untuk semua bilangan prima n<340. Contoh 4.1 meruntuhkan pernyataan ini. Kita memperoleh fakta bahwa 341 | (2³⁴¹ – 2), walaupun 341 bukan bilangan prima. Suatu bilangan komposit m yang memenuhi m | (2^m – 2) dinamakan bilangan prima semu (pseudoprima). Beberapa diantara bilangan prima semu adalah 341, 561, 645 dan 1105.

B.       Teorema Wilson

Teorema 5

Jika p suatu bilanagan prima, maka pengkongruenan x²  1 (mod p)

Mempunyai tepat dua solusi, yaitu 1 dan p-1

Bukti:

• Misalkan r adalah suatu solusi dari pengkongruenan x²  1 (mod p), maka:

r² – 1  1 (mod p)

      (r + 1)(r – 1)  1 (mod p)

• Pengkongruenan terakhir ini berati p | (r + 1)(r – 1), karena p suatu bilangan prima, maka:

p | (r + 1) (r - 1) atau p | (r – 1) yaitu r +1 0 (mod p) atau r -1  0 (mod p)

r  -1 (mod p) atau r  1 (mod p)

r  (p – 1)(mod p) atau r  1 (mod p)

• Karena r suatu solusi dari pengkongruenan x²  1 (mod p), maka r adalah residu terkecil mod p. Jadi, 1 dan p – 1 adalah solusi dari  x²  1 (mod p).
• Bukti lain yang lebih mudah, apabila (p – 1) dan 1, masing-masing disubstitusikan pada x dalam pengkongruenan x²  1 (mod p).

Contoh 5.1:

Selesaikan pengkongruenan x²  1 (mod 7)

Penyelesaian:

Himpunan residu terkecil (mod 7) selain 0 yaitu T = { 1, 2, 3, 4, 5, 6 }. Mudah diperoleh solusi berikut ini:

Solusi dari x  1 (mod 7) adalah 1

Solusi dari 2x  1 (mod 7) adalah 4

Solusi dari 3x  1 (mod 7) adalah 5

Solusi dari 4x  1 (mod 7) adalah 2

Solusi dari 5x  1 (mod 7) adalah 3

Solusi dari 6x  1 (mod 7) adalah 6

Teorema 6 Misalkan p suatu bilangan prima selain 2 dan a’ adalah solusi dari ax  1(mod p) dengan a = 1,2,3, …., p – 1 (yaitu aa’  1 (mod p), dengan 0 < a’ < p ), maka: (i) jika a  b (mod p) maka a’  b’ (mod p) (ii) jika a =1 atau a = p – 1 maka a’  a (mod p)

Bukti:

• a = 1,2,3, … , p – 1, maka (a, p) = 1, sehingga ax   1 (mod p) mempunyai tepat 1 solusi. Ini berati a’ ada, sedemekian sehingga a a’  1 (mod p)
• Bagian (i) dibuktikan kontraposisinya, yaitu jika a’  b’ (mod p), maka a  b (mod p)

Misal: a’  b’ (mod p ), maka:

            aa’  ab’ 1(mod p). Ingat bahwa a’ dan b’ adalah solusi.

            aa’b  ab’b  b (mod p) dengan b = 1,2,3, …, (p – 1)

            a  b (mod p) sebab bb’  1(mod p)

Jadi, (i) telah terbukti.

• Bagian (ii) dibulatkan sebagai berikut:

Jika a = 1, yaitu x  1 (mod p), maka solusinya a’ = 1, sehingga a’  a (mod p)

Jadi, a = p – 1, yaitu (p – 1)x  1 (mod p)

-x  1 (mod p)

x  -1 (mod p)

x  p – 1 (mod p)

Jadi, a’ = p – 1, sehingga a’  a (mod p)

(ii) telah terbukti.

Contoh 6.1:

Pandang pengkongruenan ax  1 (mod 11) dan a’ adalah solusinya, sehingga aa’  1(mod11)

Penyelesaian:

Maka dari itu, hubungan a, a’, dan aa’ nampak dari tabel berikut ini.

a	1	2	3	4	5	6	7	8	9	10
a’	1	6	4	3	9	2	8	7	5	10
aa’	1	1	1	1	1	1	1	1	1	1

Hasil kali pasangan yang kongruen modulo 11 dapat dituliskan sebagai berikut:

2.6  1 (mod 11)

3.4  1 (mod 11)

5.9  1 (mod 11)

7.8  1 (mod 11)

Teorema 7 Jika p suatu bilangan prima, maka (p – 1)!  -1 (mod p)

Bukti:

• Menurut teorema 6, kita dapat memasangkan a dan a’ dari 2,3,4, …. (p - 2) sedemikian sehingga a.a’  1(mod p). Dan terdapat ½ (p – 3) pasangan bilangan tersebut yang kongruen mod p dengan 1.
• Jika ruas kiri dari ½ (p – 3) kekongruenan mod p tersebut dikalikan, maka hasil kalinya akan kongruen mod p dengan 1 pula, yaitu:

2.3.4.5 … (p – 2)  1 (mod p)

1.2.3.4 … (p – 2)(p – 1)  (p – 1)(mod p)

(p – 1)!  -1 (mod p).  Terbukti.

Contoh 7.1:

Diambil p = 13, maka kita dapat memasangkan a dan a’ dari 2.3.4, …, 11, sehingga terdapat 5 pasang yang hasilkalinya kongruen mod 13 dengan 1, yaitu:

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)

Hasil kali ruas dari 5 kekongruenan ini adalah (2.7) (3.9) (4.10) (5.8) (6.11)  1 (mod 13)

1.2.3.4.5. … 11.12  12 (mod 13)

12!  -1 (mod 13)

Teorema 8 Jika p suatu bilanagn prima ganjil, maka pengkongruenan x2 + 1  0 (mod p) Mempunyai solusi jika dan hanya jika p  1 (mod 4)

Bukti :

• Misalkan a adalah suatu solusi dari x² + p  0 (mod p) maka a²  -1 (mod p) dan (a,p) = 1. Karena (a,p) =1, menurut Teorema Fermat, maka:

a^p-1  1 (mod p)

(a²) ^{½ (p-1)}  1 (mod p)

(-1) ^{½ (p-1)}  (mod p)

• Bilangan prima berbentuk 4k + 3 nampak tidak memenuhi, sebab akan di dapat

(-1) ^{2k + 1}  1 (mod p) atau -1  1 (mod p), yaitu p|2 yang jelas SALAH. Jadi, bilangan prima p berbentuk 4k + 1. Untuk sebaliknya dibuktikan sebagai berikut:

Perhatikan bahwa:

            p – 1  -1 (mod p)

            p – 2  -2 (mod p)

Hal ini berartimemenuhi pengkongruenan x² + 1  0 (mod p).

Jadi, pengkongruenan itu mempunyai solusi.

Contoh 8.1:

Selesaikanlah pengkongruenan x² + 1  0 (mod 13).

Penyelesaian:

Karena 13 adalah bilanagan prima berbentuk 4k + 1, maka pengkongruenan tersebut mempunyai solusi:

       Dapat diperiksa kebenarannya dengan substitusi 5 pada x  dari pengkongruenan, yaitu:

       5² + 1 = 26  5 (mod 13)

DAFTAR PUSTAKA

Diktat teori bilangan Universitas Terbuka

Arifin ummathematic.blogspot.com

Lutfi-nurul-auliablogspot.com

Dodyliza.blogspot.com

Sahatfp.blogspot.com