Bilangan Bulat

Teori Bilangan Bulat

Bilangan Bulat

• Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, misalnya 8, 21, 8765, -34, 0
• Berlawanan dengan bilangan bulat adalah bilangan riil yang mempunyai titik desimal, seperti 8.0, 34.25, 0.02.

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 1: 4 | 12 karena 124 = 3 (bilangan bulat) atau 12 = 4 ´ 3. Tetapi 4 | 13 karena 134 = 3.25 (bukan bilangan bulat).

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

                                m = nq + r                                                           (1)

dengan 0 £ r < n.

Contoh 2.

(i)  1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47:

                        1987 = 97 × 20 + 47

(ii) –22 dibagi dengan 3 memberikan hasil bagi –8 dan sisa 2:          

–22 = 3(–8) + 2          

tetapi –22 = 3(–7)  – 1 salah karena r = –1 tidak memenuhi syarat 0 £ r < n.

                                                                                          

Pembagi Bersama Terbesar (PBB)

• Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar (PBB – greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini kita nyatakan bahwa PBB(a, b) = d.

·         Contoh 3. Faktor pembagi 45: 1, 3, 5, 9, 15, 45;

Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36;

Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, 9

PBB(45, 36) = 9.

Teorema 2. Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n > 0 sedemikian sehingga

               m = nq + r    , 0 £ r < n

maka PBB(m, n) = PBB(n, r)

Contoh 3: m = 60, n = 18,

60 = 18 × 3  + 12

                      maka PBB(60, 18) = PBB(18, 12) = 6

Algoritma Euclidean

·         Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat.

·         Euclid, penemu algoritma Euclidean, adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.

Misalkan m dan n adalah bilangan bulat tak negatif dengan

m ³ n. Misalkan r₀ = m dan r₁ = n.

Lakukan secara berturut-turut pembagian untuk memperoleh

            r₀ = r₁q₁ + r₂                0 £ r₂ £ r₁,

            r₁ = r₂q₂ + r₃                0 £ r₃ £ r₂,

            r_{n– 2} = r_n–1 q_n–1  + r_n      0 £ r_n £ r_n–1,

            r_n–1  = r_nq_n  + 0

Menurut Teorema 2,

            PBB(m, n) = PBB(r₀, r₁) = PBB(r₁, r₂) = … =

         PBB(r_{n– 2}, r_{n– 1})  = PBB(r_{n– 1}, r_n) = PBB(r_n, 0) = r_n

Jadi, PBB dari m dan n adalah sisa terakhir yang tidak nol dari runtunan pembagian tersebut

·         Diberikan dua buah bilangan bulat tak-negatif m dan n (m ³ n). Algoritma Euclidean berikut mencari  pembagi bersama terbesar dari m dan n.

Algoritma 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.

procedure Euclidean(input m, n : integer,                     output PBB : integer) { Mencari PBB(m, n) dengan syarat m dan n bilangan tak-negatif dan m ³ n   Masukan: m dan n, m ³ n dan m, n ³ 0   Keluaran: PBB(m, n) } Deklarasi    r : integer Algoritma:    while n ¹ 0 do       r¬m mod n       m¬n       n¬r    endwhile      { n = 0, maka PBB(m,n) = m }    PBB¬m

Contoh 4. m = 80, n = 12 dan dipenuhi syarat m ³ n

       

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

·         PBB dua buah bilangan bulat a dan b dapat dinyatakan sebagai kombinasi lanjar (linear combination) a dan b dengan dengan koefisien-koefisennya.

Teorema 3. Misalkan a dan b adalah dua buah bilangan bulat positif, maka terdapat bilangan bulat m dan n sedemikian sehingga PBB(a, b) = ma + nb.

Misalnya PBB(80, 12) = 4 , dan 4 = (-1) × 80 + 7 × 12.

Contoh 5. Nyatakan PBB(60, 18) = 6 sebagai kombinasi lanjar dari 60 dan 18.

Relatif Prima

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

·         Contoh 6. 20 dan 3 relatif prima sebab PBB(20, 3) = 1. Begitu juga 7 dan 11 relatif prima karena PBB(7, 11) = 1. Tetapi 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                                                                 (2)

·         Contoh 7. Bilangan 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. Tetapi 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.

·         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 8. 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 9.

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 10.

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 11.

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 12.

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 13.

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 14.

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 15.

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)