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.

·       Notasi: a mod m = r  sedemikian sehingga 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} (mengapa?). 

Contoh Beberapa hasil operasi dengan operator modulo:

(i)   23 mod 5 = 3         (23 = 5 × 4 +  3)

                   (ii)  27 mod 3 = 0        (27 = 3 × 9 + 0)

                   (iii) 6 mod 8 = 6          (6 = 8 × 0 + 6)    

                   (iv)  0 mod 12 = 0       (0 = 12 × 0 + 0)

                   (v) – 41 mod 9 = 4      (–41 = 9 (–5) + 4)

                   (vi) – 39 mod 13 = 0   (–39 = 13(–3) + 0)

Penjelasan untuk (v): Karena a negatif, bagi |a| dengan m mendapatkan sisa r’. Maka a mod m = m – r’ bila r’ ¹ 0. Jadi |– 41| mod 9 = 5, sehingga  –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) jika m habis membagi a – b.

·       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 )

–7 º/ 15 (mod 3)         (3 tidak habis membagi –7 – 15 = –22)

               

·       Kekongruenan a º b (mod m) dapat pula dituliskan dalam hubungan        

a = b + km                                                                    (3)

yang dalam hal ini k adalah bilangan bulat.

Contoh 

17 º 2 (mod 3)   dapat ditulis sebagai 17 = 2 + 5 × 3

–7 º 15 (mod 11) dapat ditulis sebagai –7 = 15 + (–2)11                            

·       Berdasarkan definisi aritmetika modulo, kita dapat menuliskan a mod m = r  sebagai

                   a º r (mod m)

Contoh 

Beberapa hasil operasi dengan operator modulo berikut:

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

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

                                                (iii) 6 mod 8 = 6         dapat  ditulis sebagai 6 º 6 (mod 8)       

                                                (iv)  0 mod 12 = 0      dapat ditulis sebagai 0 º 0 (mod 12)

                                                (v) – 41 mod 9 = 4     dapat ditulis sebagai –41 º 4 (mod 9)

                                                (vi) – 39 mod 13 = 0  dapat ditulis sebagai – 39 º 0 (mod 13)                             

Teorema 4. 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)

Bukti (hanya untuk 1(ii) dan 2(i) saja):

          1(ii)  a º b (mod m) berarti:

                             Û a = b + km              

                             Û a – b = km

                             Û (a – b)c = ckm                 

                             Û ac = bc + Km          

                             Û ac º bc (mod m)                                                                                                 

                  

     2(i)   a º b (mod m)     Û     a = b + k₁m

              c º d (mod m)     Û     c = d + k₂m  +

                                      Û     (a + c) = (b + d) + (k₁ + k₂)m

                                      Û     (a + c) = (b + d) + km     ( k = k₁ + k₂)

Û             (a + c) = (b + d) (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 4 tidak memasukkan operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi. Misalnya:

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

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

Balikan Modulo (modulo invers)

·       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)

Bukti: Dari definisi relatif prima diketahui bahwa PBB(a, m) = 1, dan menurut persamaan (2) terdapat bilangan bulat p dan q sedemikian sehingga

                   pa + qm = 1

yang mengimplikasikan bahwa

          pa + qm º 1 (mod m)

Karena  qm º 0 (mod m), maka

pa º 1 (mod m)

                                        

Kekongruenan yang terakhir ini berarti bahwa p adalah balikan dari a modulo m.                    ¾

·       Pembuktian di atas juga menceritakan bahwa untuk mencari balikan dari a modulo m, kita harus membuat kombinasi lanjar dari a dan m sama dengan 1. Koefisien a dari kombinasi lanjar tersebut merupakan balikan dari a modulo m.

Contoh 

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

Penyelesaian:

(a)  Karena PBB(4, 9) = 1, maka balikan dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa

9 = 2 × 4 + 1

      Susun persamaan di atas  menjadi

                   –2 × 4 + 1 × 9 = 1

      Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari 4 modulo 9. Periksalah bahwa

–2 × 4 º 1 (mod 9)        (9 habis membagi –2 × 4 – 1 = –9)

         

(b) Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada. 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) )

      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)

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

Kekongruenan Lanjar

·       Kekongruenan lanjar adalah kongruen yang berbentuk

                ax º b (mod m)

dengan m adalah bilangan bulat positif, a dan b sembarang bilangan bulat,  dan x adalah peubah bilangan bulat.

·       Nilai-nilai x dicari sebagai berikut:

     ax = b + km

yang dapat disusun menjadi

         

dengan k adalah sembarang bilangan bulat. Cobakan untuk 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:

(i) 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, …

(ii)  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).

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 5. (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)

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

Contoh 

Tentukan solusi  dari pertanyaan Sun Tse di atas.

Penyelesaian:

Menurut persamaan (5.6), kongruen pertama, x º 3 (mod 5), memberikan x = 3 + 5k₁ untuk beberapa nilai k. Sulihkan ini ke dalam kongruen kedua menjadi 3 + 5k₁ º 5 (mod 7), dari sini kita peroleh k₁ º 6 (mod 7), atau 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, kita harus mempunyai 33 + 35k₂ º 7 (mod 11), yang mengakibatkan k₂ º 9 (mod 11) atau k₂ = 9 + 11k₃. Sulihkan k₂ ini ke dalam kongruen yang ketiga menghasilkan x = 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.  Solusi tersebut modulo 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)