Kamis, 19 Januari 2012

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 r0 = m dan r1 = n.

Lakukan secara berturut-turut pembagian untuk memperoleh

            r0 = r1q1 + r2                0 £ r2 £ r1,

            r1 = r2q2 + r3                0 £ r3 £ r2,

*

            rn– 2 = rn–1 qn–1  + rn      0 £ rn £ rn–1,

            rn–1  = rnqn  + 0

Menurut Teorema 2,

            PBB(m, n) = PBB(r0, r1) = PBB(r1, r2) = … =
         PBB(rn– 2, rn– 1)  = PBB(rn– 1, rn) = PBB(rn, 0) = rn

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 = mr’ 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 ab.

·         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) ap º bp (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             
                                    Û ab = km
                                    Û (ab)c = ckm                   
                                    Û ac = bc + Km                    
                                    Û ac º bc (mod m)                                                         ¾                                                             
                       
      2(i)       a º b (mod m) Û        a = b + k1m
                  c º d (mod m) Û        c = d + k2m  +
                                                Û        (a + c) = (b + d) + (k1 + k2)m
                                                Û        (a + c) = (b + d) + km     ( k = k1 + k2)
Û                (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 m1, m2, …, mn adalah bilangan bulat positif sedemikian sehingga PBB(mi, mj) = 1 untuk i ¹ j. Maka sistem kongruen lanjar

                                    x º ak (mod mk)

mempunyai sebuah solusi unik modulo m = m1 × m2 ×× mn.





Contoh 15.
Tentukan solusi  dari pertanyaan Sun Tse di atas.
Penyelesaian:
Menurut persamaan (5.6), kongruen pertama, x º 3 (mod 5), memberikan x = 3 + 5k1 untuk beberapa nilai k. Sulihkan ini ke dalam kongruen kedua menjadi 3 + 5k1 º 5 (mod 7), dari sini kita peroleh k1 º 6 (mod 7), atau k1 = 6 + 7k2  untuk beberapa nilai k2. Jadi kita mendapatkan x = 3 + 5k1 = 3 + 5(6 + 7k2) = 33 + 35k2 yang mana memenuhi dua kongruen pertama.  Jika x memenuhi kongruen yang ketiga, kita harus mempunyai 33 + 35k2 º 7 (mod 11), yang mengakibatkan k2 º 9 (mod 11) atau k2 = 9 + 11k3. Sulihkan k2 ini ke dalam kongruen yang ketiga menghasilkan x = 33 + 35(9 + 11k3) º 348 + 385k3 (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 = m1 × m2 × m3 = 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)

Tidak ada komentar:

Poskan Komentar