KEKONGRUENAN
Konsep kekongruenan bilangan dikembangkan berdasarkan konsep bahwa setiap bilangan bulat positif
dapat dinyatakan ke dalam bentuk N = pq + r atau N - r = pq dengan p, q, r adalah bilangan bulat dan r
berada pada 0 = r < p. Persamaan N = pq + r dengan p menyatakan pembagi, q menyatakan hasil bagi dan
r menyatakan sisa.
Persamaan di atas sering pula ditulis N = r (mod p)
Dari hal tersebut didapat definisi bahwa a = b (mod m) jika m.(a - b) untuk bilangan bulat a, b dan m.
Contoh :
(1) 25 = 1 (mod 4) sebab 4.24
(2) 1 = -3 (mod 4) sebab 4.4
Beberapa sifat berkaitan dengan modulu adalah sebagai berikut. Misalkan a, b, c, d dan m adalah
bilangan-bilangan bulat dengan d > 0 dan m > 0, berlaku :
(i) a = a (mod m)
(ii) Jika a = b (mod m), maka b = a (mod m)
(iii) Jika a = b (mod m) dan b = c (mod m) maka a = c (mod m)
(iv) Jika a = b (mod m) dan d.m maka a = b (mod d)
(v) Jika a = b (mod m) maka ak = bk (mod m) untuk semua k bilangan asli
(vi) Jika a = b (mod m) dan f(x) = anxn + an-1xn-1 + ··· + ao maka f(a) = f(b) (mod m)
(vii) Jika a = b (mod m) dan c = d (mod m) maka a + c = b + d (mod m)
(viii) Jika a = b (mod m) dan c = d (mod m) maka ac = bd (mod m)
(ix) (am + b)k = bk (mod m) untuk semua k bilangan asli
(x) Dari sifat (viii) didapat (am + b)k · (cm + d)n = bk · dn (mod m) untuk semua k dan n bilangan asli
(xi) Jika ca = cb (mod m) dan FPB(c, m) = 1 maka a = b (mod m)
(xii) Misalkan n . N dan S(n) adalah penjumlahan digit-digit dari n maka berlaku n = S(n) (mod 9).
(xiii) n5 = n (mod 10) untuk setiap n . N.
Contoh 14 :
(OSP 2004 SMP/MTs) Untuk bilangan bulat a dan b, <a, b> artinya bilangan bulat tak negatif yang
merupakan sisa a x b jika dibagi oleh 5. Bilangan yang ditunjukkan oleh <-3, 4> adalah ······
Solusi :
Karena -3 x 4 = - 12 = 5 x (-3) + 3 maka <-3, 4> = 3
Jadi, <-3, 4> = 3.
Contoh 15 :
(OSN 2003 SMP/MTs) Untuk menarik minat pelanggan, suatu restoran penjual makanan cepat saji
memberikan kupon berhadiah kepada setiap orang yang membeli makanan di restoran tersebut dengan
nilai lebih dari Rp. 25.000,-. Di balik setiap kupon tersebut tertera salah satu dari bilangan-bilangan
berikut : 9, 12, 42, 57, 69, 21, 15, 75, 24 dan 81. Pembeli yang berhasil mengumpulkan kupon dengan
jumlah bilangan di balik kupon tersebut sama dengan 100 akan diberi hadiah berupa TV 21”. Kalau
pemilik restoran tersebut menyediakan sebanyak 10 buah TV 21”, berapa banyak yang harus diserahkan
kepada para pelanggannya ?
Solusi :
Bilangan-bilangan 9, 12, 42, 57, 69, 21, 15, 75, 24 dan 81 semuanya habis dibagi 3.
Maka penjumlahan bilangan-bilangan mana pun di antara 9, 12, 42, 57, 69, 21, 15, 75, 24 dan 81 akan
menghasilkan suatu bilangan yang habis dibagi 3.
Tetapi 100 jika dibagi 3 akan bersisa 1.
Maka tidak ada TV yang diserahkan.
Contoh 16 :
Tentukan angka satuan dari .
777
Solusi :
Dalam persoalan bentuk perpangkatan dengan modulu m selalu diusahakan agar didapat suatu bilangan
yang bersisa 1 atau -1 jika dibagi dengan m agar memudahkan dalam perhitungan sebab 1k = 1 sedangkan
(-1)k sama dengan 1 atau -1 bergantung dari paritas k untuk k suatu bilangan bulat.
Angka satuan merupakan sisa jika suatu bilangan dibagi 10.
Alternatif 1 :
Perlu diingat bahwa 74 = 2401 yang bersisa 1 jika dibagi 10.
Maka akan dibuat pangkat dari bilangan pokok 7 dinyatakan dalam modulu 4.
72 = 1 (mod 4)
77 = (72)3 · 7 = 13 · 7 (mod 4) = 3 (mod 4)
Sehingga 77 = 4k + 3 untuk suatu bilangan asli k.
()3434777777·==+kk = (240 · 10 + 1)k · (34 · 10 + 3) = 1k · 3 (mod 10)
777 = 3 (mod 10)
Jadi, angka satuan dari adalah 3.
777
Alternatif 2 :
72 = 49 yang bersisa -1 jika dibagi 10.
Mngingat bahwa (-1)k bernilai positif hanya jika k genap maka akan dibuat pangkat dari bilangan pokok 7
dinyatakan dalam modulu 4.
72 = 1 (mod 4)
77 = (72)3 · 7 = 13 · 7 (mod 4) = 3 (mod 4)
Sehingga 77 = 4k + 3 untuk suatu bilangan asli k.
777 = 74k+3 = (72)2k · 73 = (5 · 10 - 1)2k · (343) (mod 10) = (-1)2k · (3) (mod 10) = 3 (mod 10)
Jadi, angka satuan dari adalah 3.
777
Cara lain penyelesaian soal tersebut adalah dengan melihat pola dari angka satuan yang selalu berulang.
Cara ini tidak dibahas dalam contoh ini dan dipersilakan kepada Pembaca untuk menyelesaikannya.
Contoh 17 :
Tentukan angka satuan dari 20072009.
Solusi :
Mencari angka satuan dari suatu bilangan sama dengan mencari sisa jika bilangan tersebut dibagi 10.
20072009 = (200 · 10 + 7)2009
20072009 = 72009 (mod 10) (menggunakan sifat (ix)
Alternatif 1 :
20072009 = (74)502 · 71 (mod 10)
20072009 = (240 · 10 + 1)502 · 71 (mod 10)
20072009 = 1502 · 7 (mod 10) (menggunakan sifat (x)
20072009 = 7 (mod 10)
Jadi, angka satuan 20072009 adalah 7.
Alternatif 2 :
20072009 = (72)1004 · 71 (mod 10)
20072009 = (5 · 10 - 1)1004 · 71 (mod 10)
20072009 = (-1)1004 · 7 (mod 10) (menggunakan sifat (x)
20072009 = 7 (mod 10)
Jadi, angka satuan 20072009 adalah 7.
Contoh 18 :
(OSK 2004 SMP/MTs) Jika 213 dibagi dengan 13, maka akan memberikan sisa sama dengan ·····
Solusi :
Alternatif 1 :
213 = 8192 = 13 · 630 + 2
Maka sisa jika 213 dibagi dengan 13 adalah 2.
Alternatif 2 :
Alternatif 1 bisa digunakan untuk suatu bilangan-bilangan kecil. Tetapi jika pangkat dari 2 merupakan
bilangan yang besar maka cara tersebut tidak efektif. Alternatif berikut bisa dipertimbangkan.
213 =(26)2 · 2 = (13 · 5 - 1)2 · 2 = (-1)2 · 2 (mod 13) = 2 (mod 13)
Maka sisa jika 213 dibagi dengan 13 adalah 2.
Contoh 19 :
Tentukan sisa pembagian 3 · 53 + 272010 oleh 7.
Solusi :
53 = (8 · 7 - 3) = -3 (mod 7)
3 · 53 = 3 (-3) (mod 7) = -9 (mod 7) = -2 (mod 7)
27 = -1 (mod 7) sehingga 272010 = (-1)2010 (mod 7) = 1 (mod 7)
3 · 53 + 272010 = -2 + 1 (mod 7) = -1 (mod 7) = 6 (mod 7)
Jadi, sisa pembagian 3 · 53 + 272010 oleh 7 adalah 6.
Contoh 20 :
(MATNC 2001) N adalah bilangan asli yang memenuhi N = 2 (mod 3) dan N = 1 (mod 2). Tentukan sisanya
jika N dibagi 6.
Solusi :
Alternatif 1 :
Karena N jika dibagi 3 bersisa 2 maka N jika dibagi 6 akan bersisa 2 atau 5.
Karena N bersisa 1 jika dibagi 2 maka tidak mungkin N akan berbentuk N = 6k + 2.
Maka N = 6k + 5.
Jadi, jika N dibagi 6 maka akan bersisa 5.
Alternatif 2 :
Karena N = 1 (mod 2) maka N = 2p - 1 untuk suatu bilangan bulat p.
2p - 1 = 2 (mod 3) sehingga 2p = 0 (mod 3)
Karena 2 dan 3 relatif prima maka p = 0 (mod 3)
Maka didapat p = 3q untuk suatu bilangan bulat q.
N = 6q - 1 = -1 (mod 6) = 5 (mod 6)
Jadi, sisanya jika N dibagi 6 adalah 5.
Alternatif 3 :
Karena N = 1 (mod 2) maka N = 2p + 1 untuk suatu bilangan bulat p.
2p + 1 = 2 (mod 3) sehingga 2p = 1 (mod 3)
Karena 2 dan 3 relatif prima maka p = 2 (mod 3)
Maka didapat p = 3q + 2 untuk suatu bilangan bulat q.
N = 2(3q + 2) + 1 = 5 (mod 6)
Jadi, sisanya jika N dibagi 6 adalah 5.
Alternatif 4 :
Karena N = 2 (mod 3) maka N = 3p + 2 untuk suatu bilangan bulat p.
3p + 2 = 1 (mod 2) sehingga 3p = 1 (mod 2)
Karena 2 dan 3 relatif prima maka p = 1 (mod 2)
Maka didapat p = 2q + 1 untuk suatu bilangan bulat q.
N = 3(2q + 1) + 2 = 5 (mod 6)
Jadi, sisanya jika N dibagi 6 adalah 5.
Contoh 21 :
Tentukan dua angka terakhir dari 32009.
Solusi :
32009 = (35)400 · 39 = (243)400 · 39
32009 = (43)400 · 39 (mod 100)
32009 = (1849)200 · 39 (mod 100)
32009 = (49)200 · 19683 (mod 100)
32009 = (2401)100 · 83 (mod 100)
32009 = (1)100 · 83 (mod 100)
32009 = 83 (mod 100)
Jadi, dua angka terakhir dari 32009 adalah 83.
Tidak ada komentar:
Posting Komentar