Minggu, 28 Oktober 2012

ARITMATIKA MODULAR


Banyak konsep aritmatika jam dapat digunakan untuk mengerjakan masalah-masalah yang berkenaan dengan kalender. Misalkan, hari minggu pada bulan Juli 2006 jatuh pada
tanggal                          2,  9,  16,  23,  dan  30.  Selisih  dari  sebarang  dua  buah  tanggal-tanggal  tersebut
mempunyai kelipatan 7. Tanggal 1 dan tanggal 29 jatuh pada hari yang sama karena 29 - 1 =
28 dan 28 adalah juga kelipatan 7. Kita katakan bahwa 29 adalah kongruen 1 modulo 7 dan
kita tulis 29                              1 (mod 7). Hal yang sama, karena selisih 18 dan 6 adalah kelipatan 12, kita
tulis 18                             6 (mod 12). Hal ini membawa kita kepada definisi berikut.
Definisi
Misalkan n adalah suatu bilangan bulat positif, a dan b adalah suatu bilangan bulat. a dikatakan kongruen b modulo n, ditulis a    b (mod n) jika dan hanya jika a - b adalah kelipatan n.
Untuk memantapkan pemahaman kita tentang definisi di atas, perhatikan contoh di bawah ini:
Contoh 1.
Periksa kebenaran pernyataan berikut ini:
            (a) 3     24 (mod 7)
(b) -31 11 (mod 7)
(c) -15  -64 (mod 7)
(d) 13  -1 (mod 7)
(e) 23   3 (mod 7)
Jawab
(a) 3     24 (mod 7) benar karena 3 - 24 = -21 kelipatan dari 7
(b) -31 11 (mod 7) benar karena -31 - 11 = -42 kelipatan dari 7
(c) -15  -64 (mod 7) benar karena -15 + 64 = 49 kelipatan dari 7
(d)       13        -1 (mod 7) benar karena 13 + 1 = 14 kelipatan dari 7
(e) 23   3 (mod 7) salah karena 23 - 3 = 20 bukan kelipatan dari 7.
Jika a - b bukan kelipatan dari n, atau ditulis n           (a - b), maka kita katakan bahwa a tidak
kongruen b modulo n dan ditulis a    b (mod n). Sebagai contoh, 23                             3 (mod 7).
Contoh 2:
Tentukan semua bilangan bulat x sedemikian sehingga x       1 (mod 10).
Jawab.
x 1 (mod 10) jika dan hanya jika x - 1 = 10 k untuk setiap k bilangan bulat.
Jika k = 0, 1, 2, 3, … maka berturut-turut x = 1, 11, 21, 31,  
Begitu pula k = -1, -2, -3, … maka berturut-turut x = -9, -19, -29, …
Dua barisan tersebut digabungkan sehingga himpunan penyelesaian x  1 (mod 10) adalah…, -29, -19, -9, 1, 11, 21, 31, …
Pada  contoh  2  di  atas,  tampak bahwa stiap elemen pada  1,         11,       21,       31,      
mempunyai sisa  1 jika dibagi oleh  10. Secara umum dapat dikatakan bahwa dua buah bilangan cacah adalah kongruen modulo n jika dan hanya jika sisanya pada pembagian oleh m adalah sama.
Sifat1
Misalkan n suatu bilangan bulat positif dan a, b, c, dan d bilangan bulat sebarang berlaku:
1.  a    a (mod n)
2.  Jika a    b (mod n) maka b    a (mod n)
3.  Jika a    b (mod n) dan b    c (mod n) maka a    c (mod n)
4.  Jika a    b (mod n) dan c    d (mod n)  maka a + c    b + d (mod n)
5.  Jika a    b (mod n) dan c    d (mod n)  maka ac    bd (mod n)
6.  Jika a    b (mod n) maka a + c    b + c (mod n)
7.  Jika a    b (mod n) maka ac    bc (mod n)
8.  Jika a    b (mod n) maka ak    bk(mod n) untuk k bilangan bulat positif sebarang.
Bukti. 
1.  Untuk a bilangan bulat sebarang dan n suatu bilangan bulat positif berlaku a - a = 0.n.
Dengan demikian, a    a (mod n).
2.  a    b (mod n)
Ada k suatu bilangan bulat.
Akibatnya, b - a = -(a - b)
= -(kn)
= (-k)n
Karena -k juga suatu bilangan bulat, b    a (mod n)
3.    a    b (mod n) dan b    c (mod n)
Ada h dan k bilangan bulat sehingga
a - b = hn dan b - c = kn.
Akibatnya, a - c  = (a - b) + (b - c)
= hn + kn
= (h + k) n
Karena h + k juga bilabgab bulat, a    c (mod n) ‘4. a    b (mod n) dan c    d (mod n)

Ada h dan k bilangan bulat sehingga
a - b = hn dan b - c = kn
(a + c) - (b + d) = (a - b) + (c - d)
= hn + kn
= (h + k)n
Karena h + k juga bilangan bulat, a + c    b + d (mod n).
5. a    b (mod n) dan c    d (mod n)
Pandang ac = (b + hn)(d + kn)
=  bd + (bk + dh + hkn)n
Karena (bk + dh + hkn) bilangan bulat,

Ada h dan k bilangan bulat, ac    bd (mod n).
1.  a    b (mod n)
Ada h bilangan bulat sehingga a - b = hn
Karena (a + c) - (b + c) = a - b = hn, a + c    b + c (mod n).
2.  a    b (mod n)
Ada h bilangan bulat sehingga a - b = hn
ac - bc = (a - b)c = hnc = (hc)n
Karena hc bilangan bulat, ac    bc (mod n).
3.  Untuk buti ini kita gunakan induksi matematik.
Untuk k = 1, berlaku a    b (mod n).
Asumsikan ak    bk (mod n) berlaku,
harus ditunjukkan ak+1    bk+1(mod n) juga berlaku.
Dari (5), jika a    b (mod n) dan c    d (mod n) maka ac    bd (mod n). Kita ganti c oleh ak dan d oleh bk diperoleh
aak    bbk (mod n) atau
ak+1    bk+1 (mod n)
Contoh 3
Tentukan sisanya jika 3100 dibagi oleh 5.
Jawab.
Tampaknya  kalkulator  tidak  dapat  digunakan  untuk  menemukan  jawaban  atas masalah yang diajukan. Untuk itu kita gunakan cara lain untuk menyelesaikan masalah ini. Kita tahu bahwa suatu bilangan bulat positif dibagi oleh 5 mempunyai sisa 0, 1, 2, 3, atau 4. Penggunaan aritmatika modular akan membantu kita jika kita dapat menemukan bilangan bulat terkecil yang ekuvalen dengan pangkat dari 3, dan penggunaan sifat (7) dan (8) untuk membangun 3100 dan menemukan ekuivalensi mod 5. Kita tahu bahwa 32       4 (mod 5)
Dengan demikian,
33            3 . 4     2 (mod 5)
34       3 . 2       1 (mod 5)
Dengan menggunakan sifat (8) kita peroleh,
(34)25    125 (mod 5), atau
3100     1 (mod 5).
Jadi,    3100 dibagi oleh 5 mempunayi sisa 1.

Sifat 2
Jika ca    cb (mod n) maka a    b (mod n/d) di mana d = FPB(c,n).
Bukti.
Karena ca    cb (mod n),
c(a - b) = ca - cb = kn untuk suatu bilangan bulat k.
Kita tahu bahwa d = FPB(c , n), dengan demikian, ada bilangan bulat saling prima (relative prime)   r dan s yang memenuhi c = dr, n = ds. Jika hasil ini kita substitusikan ke persamaan c(a - b) = ca - cb = kn maka kita peroleh r(a - b) = ks.
Hasil ini menunjukkan s    r(a - b), dan karena FPB (r , s) = 1, diperoleh s                                  (a - b). Dengan
kata lain,
a    b (mod s), atau  a    b (mod n/d)

Sifat 3
Jika ca    cb (mod n) dan FPB(c , n) = 1 maka a    b (mod n).
Sifat (3) ini hanya merupakan kasus khusus dari sifat (2).

Sifat 4
Jika ca    cb (mod p) dan p      c, di mana p adalah bilangan prima maka a    b (mod p). Bukti
Kondisi p      c dan p adalah bilangan prima ini mengakibatkan FPB(c , p) = 1.
Contoh 4
a.  Perhatikan 33  15 (mod 9), atau 3.11     3.5 (mod 9).
Karena FPB(3 , 9) = 1 mengakibatkan 11   5 (mod 9).
b.    Perhatikan -35   45 (mod 8), atau 5.(-7)   5.9 (mod 8).
Karena 5 dan 8 bilangan bulat saling prima mengakibatkan -7   9 (mod 8).

Rangkuman

1. Misalkan n adalah suatu bilangan bulat positif, a dan b adalah suatu bilangan bulat. a
dikatakan kongruen b modulo n, ditulis a    b (mod n)
jika dan hanya jika (a - b) adalah kelipatan n.
2. Misalkan n suatu bilangan bulat positif dan a, b, c, dan d bilangan bulat sebarang berlaku:
a.  a    a (mod n)
b.  Jika a    b (mod n) maka b    a (mod n)
c.  Jika a    b (mod n) dan b    c (mod n) maka a    c (mod n)
d.  Jika a    b (mod n) dan c    d (mod n)  maka a + c    b + d (mod n)
e.  Jika a    b (mod n) dan c    d (mod n)  maka ac    bd (mod n)
f.  Jika a    b (mod n) maka a + c    b + c (mod n)
g.  Jika a    b (mod n) maka ac    bc (mod n)
h.  Jika a    b (mod n) maka ak    bk(mod n) untuk k bilangan bulat positif sebarang.
3.  Jika ca    cb (mod n) maka a    b (mod n/d) di mana d = FPB(c , n).
4.  Jika ca    cb (mod n) dan FPB(c , n) = 1 maka a    b (mod n).
5.  Jika ca    cb (mod p) dan p      c, di mana p adalah bilangan prima maka a    b (mod p).

Tidak ada komentar:

Poskan Komentar

Komentar Saudara sangat berarti untuk Blog ini...