Teori Bilangan Keprimaan KPK

pengertian keprimaan, pengertian teori bilangan keprimaan, pengertian KPK, sifat-sifat keprimaan, dalil-dalil keprimaan.

Matematika Diskret

Teori Bilangan

Yang dimaksud dengan teori bilangan dalam Matematika Diskrit adalah teori mengenai bilangan bulat dan sifat-sifatnya, dimana bilangan yang dimakudkan adalah bilangan integer/bilangan bulat. Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, sebagai contoh disebutkan 1, 4, 7, 2010, -88 merupakan sekumpulan bilangan bulat/integer. Sedangkan lawan dari bilangan bulat/integer adalah bilangan riil, yaitu bilangan yang memiliki titik desimal, sebagai contoh 9.0, 26.5, 0.25.

Pada bagian ini akan dijelaskan prinsip-prinsip teori bilangan, meliputi :

·         Keterbagian (divisibility)

·         Pembagi persekutuan terbesar (greatest common divisors/gcd)

·         Kelipatan persekutuan terkecil (least common multiples/lcm), dan

·         Aritmetika modular (modular arithmetics)

Sifat Pembagian pada Bilangan Bulat

·         Misalkan a dan b adalah dua buah bilangan bulat dengan syarat a ¹ 0. Kita menyatakan bahwa a habis membagi b (a divides b) jika terdapat bilangan bulat c  sedemikian sehingga b = ac.

·         Notasi: a | b  jika b = ac, c Î Z dan a ¹ 0.         (Z = himpunan bilangan bulat)

·         Kadang-kadang pernyataan “a habis membagi b“ ditulis juga  “b  kelipatan a”.

Contoh :

4 | 12 karena 124 = 3 (bilangan bulat)

4 | 13 karena 134 = 3.25 (bukan bilangan bulat).

Rosen menyebutkan dalam bukunya :

Teorema I

If a and b are positif integer, then there exist integer s and t such that gcd(a,b) = sa + tb

Dalam penjabarannya dapat diasumsikan sebagai berikut :

Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n>0 (Integer Positif). Jika m dibagi dengan n maka terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga :

m = nq + r

dengan 0 £ r < n

Contoh :

Misal m = 2010 dan n = 44, maka :

2010 dibagi dengan 44 memberikan hasil 45 dengan sisa 30, dengan demikian :

q (quotient) = 45 dan r (remainder) = 30

Teori I yang disampaikan Rosen diatas dapat digunakan dalam menghitung PBB (Pembagi Bersama Terbesar) atau disebut dengan gcd (Greatest common divisor). Dari teori I tersebut, Euclid (matematikawan Yunani) telah menuliskan theorema untuk mencari gcd dari 2 integer, yang disebut dengan Theorema Euclidean.

Theorema Euclidean

1.      Jika n = 0 maka

       m adalah PBB(m, n);

       stop.

 tetapi jika n ¹ 0,

           lanjutkan ke langkah 2.

2.      Bagilah m dengan n dan misalkan r adalah sisanya.

3.      Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1.

Contoh :

 m = 80, n = 12 dan dipenuhi syarat m ³ n

  

Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB(80, 12) = 4.                       

Relatif Prima

 

Dua buah bilangan bulat a dan b dikatakan relatif prima jika PBB(a, b) = 1.

Contoh :

20 dan 3 relatif prima sebab PBB(20, 3) = 1

7 dan 11 relatif prima karena PBB(7, 11) = 1

20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 ¹ 1.

 

Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga :

ma + nb = 1

Contoh :

20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis

2 . 20 + (–13) . 3 = 1 , à dengan m = 2 dan n = –13.

20 dan 5 tidak relatif prima karena PBB(20, 5) = 5 ¹ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m . 20 + n . 5 = 1.

Aritmetika Modulo

Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m (dibaca “a modulo m”) memberikan sisa jika a dibagi dengan m.

 

a mod m = r  à a = mq + r, dengan 0 £ r < m

Bilangan m disebut modulus atau modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}

Contoh :

Beberapa hasil operasi dengan operator modulo:

·         23 mod 5 = 3               à (23 = 5 × 4 +  3)

·         0 mod 12 = 0               à (0 = 12 × 0 + 0)

·         – 41 mod 9 = 4            à (–41 = 9 (–5) + 4)

·         – 39 mod 13 = 0          à (–39 = 13(–3) + 0)

Penjelasan :

Karena a negatif, bagi |a| dengan m mendapatkan sisa r’.  Maka

 

a mod m = m – r’ bila r’ ¹ 0.

à |– 41| mod 9 = 5,

à –41 mod 9 = 9 – 5 = 4.                                                                  

Kongruen

Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka kita katakan 38 º 13 (mod 5) (baca: 38 kongruen dengan 13 dalam modulo 5).  Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0, maka :

 

a º b (mod m) , m habis membagi a – b.

a º b (mod m) ßàa = b + km,  k adalah bilangan bulat

a mod m = r  ßà a º r (mod m)

Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a º/ b (mod m) .

Contoh :

17 º 2 (mod 3)         à        ( 3 habis membagi 17 – 2 = 15)

–7 º 15 (mod 11)     à        (11 habis membagi –7 – 15 = –22)

12 º/ 2 (mod 7)        à        (7 tidak habis membagi 12 – 2 = 10 )

           

17 º 2 (mod 3)         à        17 = 2 + 5 × 3

–7 º 15 (mod 11)     à        –7 = 15 + (–2)11                                         

23 mod 5 = 3            à        dapat ditulis sebagai 23 º 3 (mod 5)

27 mod 3 = 0            à        dapat ditulis sebagai 27 º 0 (mod 3)

Teorema 2. Misalkan m adalah bilangan bulat positif.

1. Jika a º b (mod m) dan c adalah sembarang bilangan bulat maka

(i)  (a + c) º (b + c) (mod m)

(ii) ac º bc (mod m)

(iii) a^p º b^p (mod m) untuk suatu bilangan bulat tak negatif p.

2. Jika a º b (mod m) dan c º d (mod m), maka

(i)  (a + c) º (b + d) (mod m)

(ii) ac º bd (mod m)

Contoh :

Misalkan 17 º 2 (mod 3) dan 10 º 4 (mod 3), maka menurut Teorema 2,

·         17 + 5 = 2 + 5 (mod 3)         Û        22 = 7 (mod 3)                       

·         17 . 5 = 5 × 2 (mod 3)           Û        85 = 10 (mod 3)                     

·         17 + 10  = 2 + 4 (mod 3)      Û        27 = 6 (mod 3)                       

·         17 . 10 = 2 × 4 (mod 3)         Û        170 = 8 (mod 3)                     

Perhatikanlah bahwa Teorema 2 tidak berlaku operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi. Misalnya:

·         10 º 4 (mod 3) dapat dibagi dengan 2 karena 10/2 = 5 dan 4/2 = 2, dan 5 º 2 (mod 3)

·         14 º 8 (mod 6) tidak dapat dibagi dengan 2, karena 14/2 = 7 dan 8/2 = 4, tetapi  7 º/ 4 (mod 6).  

Kekongruenan Lanjar (The Linier Congruences)

Kekongruenan lanjar adalah kongruen yang berbentuk

 

ax º b (mod m)

m                     = bilangan bulat positif

a dan b            = bilangan bulat

x                      = peubah bilangan bulat.

Nilai-nilai x dicari sebagai berikut:

     ax = b + km            atau       

dengan k adalah sembarang bilangan bulat. k = 0, 1, 2, … dan k = –1, –2, … yang menghasilkan x sebagai bilangan bulat.

Contoh :

Tentukan solusi: 4x º 3 (mod 9) dan 2x º 3 (mod 4)

Penyelesaian:

·         4x º 3 (mod 9)

           

k = 0 à x = (3 + 0 × 9)/4 = 3/4            (bukan solusi)

            k = 1 à x = (3 + 1 × 9)/4 = 3

            k = 2 à x = (3 + 2 × 9)/4 = 21/4          (bukan solusi)

            k = 3, k = 4                                          tidak menghasilkan solusi

            k = 5 à x = (3 + 5 × 9)/4 = 12

            …

            k = –1 à x = (3 – 1 × 9)/4 = –6/4        (bukan solusi)

            k = –2 à x = (3 – 2 × 9)/4 = –15/4      (bukan solusi)

            k = –3 à x = (3 – 3 × 9)/4 = –6 

            …

            k = –6 à x = (3 – 6 × 9)/4 = –15 

            …

            Nilai-nilai x yang memenuhi: 3, 12, … dan –6, –15, …

·         2x º 3 (mod 4)

Karena 4k genap dan 3 ganjil maka penjumlahannya menghasilkan ganjil, sehingga hasil penjumlahan tersebut jika dibagi dengan 2 tidak menghasilkan bilangan bulat. Dengan kata lain, tidak ada nilai-nilai x  yang memenuhi 2x º 3 (mod 5).

Balikan Modulo (modulo invers)

 

Teorema 3. Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan (invers) dari a modulo m. Balikan dari a modulo m adalah bilangan bulat  sedemikian sehingga

a º 1 (mod m)

Contoh :

Tentukan balikan dari 17 (mod 7), dan 18 (mod 10).

Penyelesaian:

·         Dari algoritma Euclidean diperoleh  rangkaian pembagian berikut:

17 = 2 × 7 + 3   (i)

7 =  2 × 3 + 1    (ii)

3 = 3 × 1 + 0     (iii)       (yang berarti: PBB(17, 7) = 1) )

Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada.

      Susun (ii) menjadi:

            1 = 7 – 2 × 3     (iv)

      Susun (i) menjadi

            3 = 17 – 2 × 7   (v)

     Sulihkan (v) ke dalam (iv):

            1 = 7 – 2 × (17 – 2 × 7) = 1 × 7 – 2 × 17 + 4 × 7 = 5 × 7 – 2 × 17

         atau        –2 × 17  + 5 × 7 = 1

        Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari 17 modulo 7. 

–2 × 17 º 1 (mod 7)     (7 habis membagi –2 × 17 – 1 = –35)

·         Karena PBB(18, 10) = 2 ¹ 1, maka balikan dari 18 (mod 10) tidak ada.

Chinese Remainder Problem

Pada abad pertama, seorang matematikawan China yang bernama Sun Tse mengajukan pertanyaan sebagai berikut:

           

”Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7”.

Pertanyaan Sun Tse dapat dirumuskan kedalam sistem kongruen lanjar:

            x º 3 (mod 5)

            x º 5 (mod 7)

            x º 7 (mod 11)

 

Teorema 4. (Chinese Remainder Theorem) Misalkan m₁, m₂, …, m_n adalah bilangan bulat positif sedemikian sehingga PBB(m_i, m_j) = 1 untuk i ¹ j. Maka sistem kongruen lanjar

                                 x º a_k (mod m_k) à k = 1, 2, 3, ...

mempunyai sebuah solusi unik modulo m = m₁ × m₂ × … × m_n.

Contoh :

Tentukan solusi  dari pertanyaan Sun Tse di atas.

x º 3 (mod 5)

            x º 5 (mod 7)

            x º 7 (mod 11)

Penyelesaian:

Menurut persamaan diatas, kongruen pertama,

x º 3 (mod 5), à x = 3 + 5k₁ untuk beberapa nilai k.

Sulihkan ini ke dalam kongruen kedua menjadi,

x º 5 (mod 7), à 3 + 5k₁        º 5 (mod 7)

à k₁                º 6 (mod 7)

à k₁                = 6 + 7k₂  , untuk beberapa nilai k₂.

Jadi kita mendapatkan

x          = 3 + 5k₁

= 3 + 5(6 + 7k₂)

= 33 + 35k₂

yang mana memenuhi dua kongruen pertama. Jika x memenuhi kongruen yang ketiga, maka :

x º 7 (mod 11)            à 33 + 35k₂    º 7 (mod 11)

k₂         º 9 (mod 11)

k₂         = 9 + 11k₃.

Sulihkan k₂ ini ke dalam kongruen yang ketiga menghasilkan :

x          = 33 + 35k₂

= 33 + 35(9 + 11k₃)

º 348 + 385k₃ (mod 11).

Dengan demikian, x º 348 (mod 385) yang memenuhi ketiga konruen tersebut. Dengan kata lain, 348 adalah solusi unik modulo 385. Catatlah bahwa 385 = 5 × 7 × 11.

Solusi unik ini mudah dibuktikan sebagai berikut.

m         = m₁ × m₂ × m₃

= 5 × 7 × 11

= 5 × 77

= 11 × 35.

Karena 77  3 º 1 (mod 5), 55 × 6 º 1 (mod 7), dan 35 × 6 º 1 (mod 11), solusi unik dari sistem kongruen tersebut adalah :

                        x º 3 × 77 × 3 + 5 × 55 × 6  + 7 × 35 × 6 (mod 385)

                           º 3813 (mod 385) º 348 (mod 385)

Bilangan Prima

Bilangan bulat positif p (p > 1) disebut bilangan prima jika pembaginya hanya 1 dan p. Contoh: 23 adalah bilangan prima karena ia hanya habis dibagi oleh 1 dan 23.  Karena bilangan prima harus lebih besar dari 1, maka barisan bilangan prima dimulai dari 2, yaitu 2, 3, 5, 7, 11, 13, …. Seluruh bilangan prima adalah bilangan ganjil, kecuali 2 yang merupakan bilangan genap.

Bilangan selain prima disebut bilangan komposit (composite). Misalnya 20 adalah bilangan komposit karena 20 dapat dibagi oleh 2, 4, 5, dan 10, selain 1 dan 20 sendiri.

The Fundamental Theorem of Arithmetic

Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

Contoh :

            9 = 3 ´ 3                      (2 buah faktor prima)

            100 = 2 ´ 2 ´ 5 ´ 5     (4 buah faktor prima) 

            13 = 13                        (atau 1 ´ 13)    (1 buah faktor prima) 

Untuk menguji apakah n merupakan bilangan prima atau komposit, kita cukup membagi n dengan sejumlah bilangan prima, mulai dari 2, 3, … , bilangan prima £ Ön.

·         Bilangan Komposit           à n habis dibagi dengan salah satu dari bilangan prima.

·         Bilangan Prima                  à n tidak habis dibagi oleh semua bilangan prima.

Contoh :

Tunjukkan apakah 171 dan 199 merupakan bilangan prima atau komposit.

Penyelesaian:

·         Ö171 = 13.077.

Bilangan prima yang £ Ö171 adalah 2, 3, 5, 7, 11, 13.

Karena 171 habis dibagi 3, maka 171 adalah bilangan komposit.

·         Ö199 = 14.107.

Bilangan prima yang £ Ö199 adalah 2, 3, 5, 7, 11, 13.

Karena 199 tidak habis dibagi 2, 3, 5, 7, 11, dan 13, maka 199 adalah bilangan prima.                                  

Terdapat metode lain yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat, yang terkenal dengan Teorema Fermat. Fermat (dibaca “Fair-ma”) adalah seorang  matematikawan Perancis pada tahun 1640.

 

Teorema 5 (Teorema Fermat). Jika p adalah bilangan prima dan a adalah bilangan bulat  yang tidak habis dibagi dengan p,  yaitu PBB(a, p) = 1, maka

a^p–1 º 1 (mod p)

Contoh :

Kita akan menguji apakah 17 dan 21 bilangan prima atau bukan. Di sini kita mengambil nilai a = 2 karena PBB(17, 2) = 1 dan PBB(21, 2) = 1.

Untuk 17,

2^17–1 = 65536 º 1 (mod 17)     à Bilangan Prima

karena 17 habis membagi 65536 – 1 = 65535    (6553517 = 3855).

Untuk 21,

2^21–1 =1048576 º\ 1 (mod 21)             à Bilangan Komposit

karena 21 tidak habis membagi 1048576 – 1 = 1048575.           

Pseudoprimes / Bilangan Prima Semu        

                                             

Kelemahan Teorema Fermat: terdapat bilangan komposit n sedemikian sehingga

 

2^n–1 º 1 (mod n).

Bilangan bulat seperti itu disebut bilangan prima semu (pseudoprimes).

Misalnya komposit 341 (yaitu 341 = 11 × 31) adalah bilangan prima semu karena menurut teorema Fermat,  2³⁴⁰ º 1 (mod 341)

Contoh :

Periksalah bahwa 3¹⁶ º 1 (mod 17) dan 18⁶ º 1 (mod 49).

Penyelesaian:

·         Dengan mengetahui bahwa kongruen 3³ º 10 (mod 17), kuadratkan kongruen tersebut menghasilkan

3¹ º 3 º 3  (mod 17)

      3³ º 27 º 10  (mod 17)

            …

       Kuadratkan lagi untuk menghasilkan

            3¹² º 4 (mod 17)

      Dengan demikian, 3¹⁶ º 3¹² × 3³  × 3 º 4 × 10 × 3 º 120 º 1 (mod 17)       

·         Caranya sama seperti penyelesaian (i) di atas:

           

            18² º 324 º 30 (mod 49)

            18⁴ º 900 º 18 (mod 49)

            18⁶ º 18⁴ × 18² º 18 × 30 º 540 º 1 (mod 49)

           

Fungsi Euler f

Fungsi Euler f medefinisikan f(n) untuk n ³ 1 yang menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n.

Contoh :

Tentukan f(20).

Penyelesaian:

Bilangan bulat positif yang lebih kecil dari 20 adalah 1 sampai 19. Di antara bilangan-bilangan tersebut, terdapat f(20) = 8 buah yang relatif prima dengan 20, yaitu 1, 3, 7, 9, 11, 13, 17, 19.

Untuk n = 1, 2, …, 10, fungsi Euler adalah

            f(1) = 0                                   f(6) = 2

            f(2) = 1                                   f(7) = 6

            f(3) = 2                                   f(8) = 4

            f(4) = 2                                   f(9) = 6

            f(5) = 4                                   f(10) = 4

Jika n prima, maka setiap bilangan bulat yang lebih kecil dari n relatif prima terhadap n. Dengan kata lain, f(n) = n – 1 hanya jika n prima.

Contoh :

·         f(3) = 2                 à f(3) = 3 – 1 = 2 à 3 adalah bilangan prima

·         f(5) = 4                 à f(5) = 5 – 1 = 4 à 5 adalah bilangan prima

·         f(7) = 6                 à f(7) = 7 – 1 = 6 à 7 adalah bilangan prima

·         f(11) = 10             à f(11) = 11 – 1 = 10 à 11 adalah bilangan prima

·         f(13) = 12             à f(13) = 13 – 1 = 12 à 13 adalah bilangan prima

Jika n = pq adalah bilangan komposit dengan p dan q prima, maka

f(n) = f(p) f(q) = (p – 1)(q – 1).

Contoh :

Tentukan f(21).

Penyelesaian:

Karena 21 = 7 × 3, maka :

f(21) = f(7) f(3) = 6 × 2 = 12

Terdapat 12 buah bilangan bulat yang relatif prima terhadap 21, yaitu

1, 2, 4, 5, 8, 10, 11, 13, 14, 17, 19, 20.

 

Jika p bilangan prima dan k > 0, maka

f(p^k) = p^k – p^k-1 = p^k-1(p – 1) .

Contoh :

Tentukan f(16).

Penyelesaian:

Karena f(16) = f(2⁴) = 2⁴ – 2³ = 16 – 8 = 8,

maka ada delapan buah bilangan bulat yang relatif prima terhadap 16, yaitu

1, 3, 5, 7, 9, 11, 13.

Euler’s generalization of Fermat theorem

Jika PBB(a, n) = 1, maka

           

a^f(n) mod n = 1             (atau a^f(n) º 1 (mod n) )