Keamanan Sistem Data

Selasa, 20 November 2012

Relatif Prima

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

Contoh 9.

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

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

  (iii) 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 10. Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis

   2 . 20 + (–13) . 3 = 1  (m = 2, 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. 

Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga
             ma + nb = 1

Contoh 10. Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis
         2 . 20 + (–13) . 3 = 1  (m = 2, 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 dan m bilangan bulat (m > 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.

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

Contoh 11. 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 dikatakan 38  13 (mod 5)
    (baca: 38 kongruen dengan 13 dalam modulo 5).

Misalkan a dan b 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 12.
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)

a  b (mod m) dalam bentuk “sama dengan” dapat dituliskan sebagai   
       a = b + km       (k adalah bilangan bulat)

Contoh 13.
    17  2 (mod 3)        17 = 2 + 5  3
   –7  15 (mod 11)    –7 = 15 + (–2)11     
a mod m = r  dapat juga ditulis sebagai
        a  r (mod m)

Contoh 14.
       (i)   23 mod 5 = 3      23  3 (mod 5)
    (ii)  27 mod 3 = 0      27  0 (mod 3)
    (iii) 6 mod 8 = 6      6  6 (mod 8)   
    (iv)  0 mod 12 = 0       0  0 (mod 12)
    (v) – 41 mod 9 = 4      –41  4 (mod 9)
    (vi) – 39 mod 13 = 0   – 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)  , p bilangan bulat tak-negatif

2) Jika a  b (mod m) dan c  d (mod m), maka
    (i)  (a + c)  (b + d) (mod m)
    (ii) ac  bd (mod m)
Teorema 4 tidak memasukkan operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi.

Contoh 16:
    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).  
 

     

 

komentar | | Read More...