BAB III KONGRUENSI

3.1 Pengertian Jika kita berbicara konsep kongruensi sebenarnya hal ini secara tidak langsung sudah didapatkan pada pelajaran matematika Sekolah Dasar, hanya saja istilah yang digunakan sedikit berbeda yaitu bilangan jam atau bilangan bersisa. Cara yang dilakukan biasanya diperagakan dengan menggunakan jam sebagi media dalam operasi yang berlaku, baik jumlah maupun pengurangan. Dalam bilangan jam enaman, jika

dioperasikan dengan menggunakan jam maka bilangan bulat yang digunakan adalah 0, 1, 2, 3, 4, dan 5. Sedangkan bilangan bulat lainnya dapat direduksi yaitu dengan cara membagi bilanmgan tersebut dengan 6 dan bilangan yang digunakan adalah sisa dari pembagian tersebut. Contoh: 14 dalam jam enaman dapat direduksi menjadi 2, karena 14 jika dibagi 6 bersisa 2. 21 dalam jam enaman dapat direduksi menjadi 3, karena 21 jika dibagi 6 bersisa 3. 61 dalam jam enaman dapat direduksi menjadi 1, karena 61 jika dibagi 6 bersisa 1. dan seterusnya. Berdasarkan proses reduksi dan operasi yang ada pada bilangan jam, selanjutnya dikembangkan konsep kongruensi sebagai berikut.

Teori Bilangan- 72

14 21 61

2 karena jika 14 dibagi 6 bersisa 2 3 karena jika 21 dibagi 6 bersisa 3 1 karena jika 61 dibagi 6 bersisa 1

Pernyataan di atas dapat pula dinyatakan dengan 14 21 61 2 karena 14 2 = 12 dan 12 habis dibagi 6 3 karena 21 3 = 18 dan 18 habis dibagi 6 1 karena 61 1 = 60 dan 60 habis dibagi 6. Berdasarkan contoh di atas terlihat bahwa sesungguhnya konsep kongruensi adalah pengkajian secara lebih mendalam tentang

keterbagian pada bilangan bulat dan sifat-sifatnya yang telah dipelajari pada bab II, atau dapat pula dikatakan bahwa kongruensi adalah cara lain untuk mengkaji keterbagian dalam bilangan bulat. Untuk jelasnya perhatikan definisi dan teorema di bawah ini.

Definisi 3.1 Misal a, b, m

Z dan m

0, maka a disebut kongruen dengan b modulo

m jika a-b habis dibagi oleh m, yaitu ma b. Pernyataan ini dinotasikan a

b (mod m).

Jika m (a-b) maka dinotasikan dengan a Contoh: 7

b (mod m).

2 ( mod 5), karena 5(7-2)

34 17 6

4 ( mod 10), karena 10(34-4) 1 ( mod 4), karena 4(17-1) 1 (mod 4), karena 4 (6-1)

Teori Bilangan- 73

11

4 (mod 9), karena 9 (11-4) Dengan demikian sebenarnya istilah kongruensi sering muncul

dalam kehidupan di sekitar kita. Misalnya kerja kalender yang kita gunakan dalam tahun Masehi menggunakan bilangan bulat modulo 7 karena dalam satu minggu terdapat 7 hari, kerja arloji menggunakan bilangan bulat modulo 12 karena waktu yang ada dalam jam yaitu jam 01.00 12.00. Banyaknya bulan dalam satu tahun menggunakan bilangan bulat modulo 12, pasaran hari dalam satu minggu menggunakan bilangan bulat modulo 5 karena terdapat pasaran hari pon, wage, kliwon, legi, pahing dan masih banyak lagi contoh-contoh penggunaan kongruensi yang secara tidak langsung ada disekitar kita.

Dalil 3.1 Misal a,b,c,

Z, dan m

N, maka berlaku sifat-sifat simetris, refleksif,

dan transitip. a. Refleksif a

a (mod m)

b. Simetris Jika a

b (mod m) maka b

a.(mod m)

c. Transitif Jika a Bukti a. Misal m b (mod m) maka b c (mod m)m, maka a

c (mod m)

0, maka m0.

m0 berarti m (a-a)

Teori Bilangan- 74

Karena m (a-a), hal ini menurut definisi a bilangan Cara lain a b. a bulat a dan m

a (mod m), untuk setiap

0.

a (mod m), sebab a-a = 0 dan m0. b (mod m), menurut definisi berarti ma-b, sedangkan menurut

definisi keterbagian ma-b, dapat dinyatakan sebagai (a-b) = tm, untuk t

Z.

(a-b) = tm -(a-b) = -tm

(b-a) = (-t)m, -t Z. m (b-a) atau bc. a b

a (mod m)

b (mod m) berarti m (b-a) c (mod m) berarti m (b-c)

Menurut dalil keterbagian m (b-a) dapat dinyatakan dengan a-b = t1m m (b-c) dapat dinyatakan dengan b-c = t2m ---------------- + (a-c) = (t1+t2)m, untuk t1,t2 Jadi m (a-c) atau a c(mod m)

Z

Teorema 3.1 Misal a,b,c,d 1. Jika a Bukti a

Z dan m

N, maka

b (mod m) maka ac

bc (mod m)

b (mod m) berarti m (a-b)

Teori Bilangan- 75

Menurut definisi keterbagian bilangan bulat berlaku (a-b) = tm, t

Z.

(a-b)c = (tm)c. ac bc = (tc)m ac bc = xm, x Z.Karena ac-bc = xm, berarti m (ac-bc) atau ac = bc (mod m) 2. Jika a Bukti a

b (mod m) maka a+c

b+c (mod m)

b (mod m) berarti m (a-b)

Menurut definisi keterbagian bilangan bulat berlaku (a-b) = tm, t

Z.

(a-b) + 0 = (tm) (a-b) + (c-c) = (tm) (a+c) (b+c) = (tm)Karena (a+c) (b+c) = tm, berarti m (a+c) (b-c) atau a+c = b+c (mod m) 3. Jika a Bukti a c

b (mod m) dan c

d (mod m) maka a+c

b+d (mod m)

b (mod m) berarti m (b-a) d (mod m) berarti m (c-d)

Menurut dalil keterbagian m (b-a) dapat dinyatakan dengan a-b = t1m m (c-d) dapat dinyatakan dengan c-d = t2m ---------------- +

Teori Bilangan- 76

(a+c) - (b+d) = (t1+t2)m, untuk t1,t2 Jadi m (a+c) - (b+d) atau a+c b+d (mod m) 4. Jika a Bukti a c

Z

b (mod m) dan c

d (mod m) maka a-c

b-c (mod m)

b (mod m) berarti m (b-a) d (mod m) berarti m (c-d)

Menurut dalil keterbagian m (b-a) dapat dinyatakan dengan a-b = t1m m (c-d) dapat dinyatakan dengan c-d = t2m ---------------- (a-c) - (b-d) = (t1-t2)m, untuk t1,t2 Jadi m (a-c) - (b-d) atau a-c b-d (mod m) 5. Jika a Bukti Karena a

Z

b (mod m) dan d m, d > 0, maka a

b (mod d)

b (mod m) maka m m-b

Jika m a-b dan d m, berarti d a-b , d > 0. Karena d a-b berati a 6. Jika a

b (mod d)

b (mod m) dan c

d (mod m) maka

ax + by = bx + dy (mod m), untuk x,y Bukti a c

Z.

b (mod m) berarti m (a-b) d (mod m) berarti m (c-d)

Menurut dalil keterbagian m (b-a) dapat dinyatakan dengan a-b = t1m

Teori Bilangan- 77

m (c-d) dapat dinyatakan dengan c-d = t2m

(a-b)x = (t1m)x, x Z (c-d)y = (t2m)y, y Z---------------------------- + (a-b)x + (c-d)y = {(t1m)x+ (t2m)y}, x,y

Z Z

atau (ax +cy) (bx+dy) = {(t1x)+ (t2y)}m, {(t1x)+ (t2y)}

atau m (ax +cy) (bx+dy) = atau (ax +cy) (bx+dy) (mod m) 7. Jika a Bukti a c

b (mod m) dan c

d (mod m) maka ac = bd (mod m)

b (mod m) berarti m (a-b) d (mod m) berarti m (c-d)

Menurut dalil keterbagian m (b-a) dapat dinyatakan dengan a-b = t1m m (c-d) dapat dinyatakan dengan c-d = t2m

(a-b)c = (t1m)c, c Z atau (ac bc) = (t1m)c, c Z (c-d)b = (t2m)b, b Z atau (cb db) = (t2m)b, b Z----------------------------------------------------------------- + (ac-bd) = (t1m)c + (t2m)b, a,b

Z.

(ac-bd) = (t1c + t2b)m, (t1c + t2b) Z.atau m (ac bd ) atau (ac) (bd) (mod m) 8. Jika a Bukti a

b (mod m) maka an = bn (mod m)

b (mod m) berarti m (a-b)

Menurut dalil keterbagian

Teori Bilangan- 78

m (b-a) dapat dinyatakan dengan a-b = tm Selanjutnya kita mengetahui bahwa an bn = (a-b)(an-1 + an-2b + an-3b2 + ..... + bn-1) Karena a-b a-b , maka a-b an bn , atau a-b (a-b)(an-1 + an-2b + an-3b2 + ..... + bn-1) Menurut dalil keterbagian: Jika m a-b dan a-b an bn , maka a-b an bn Jadi a-b an bn atau an

bn (mod m)

Dalil 3.2 Andaikan f adalah suatu polinomial dengan koefisien-koefisien bilangan bulat, Jika Jika a Bukti Misal f(x) = tnxn + tn-1xn-1 + tn-2xn-2 + tn-3xn-3 + ..... + t1x + to Dengan tn, tn-1, tn-2, tn-3, t1x, to Z.

b (mod m), maka f(a)

f(b) (mod m).

Jika x = a maka f(a) = tnan + tn-1an-1 + tn-2an-2 + tn-3an-3 + ..... + t1a + to Jika x = b maka f(b) = tnbn + tn-1bn-1 + tn-2bn-2 + tn-3bn-3 + ..... + t1b + to--------------------------------------------------------------------------------------------------- -

f(a) f(b) = tn(an - bn ) + tn-1(an-1 - bn-1 ) + tn-2(an-3 bn-3) + ..... + t1(a-b) Dengan menggunakan sifat sebelumnya diperoleh a a2

b (mod m) atau m a-b sehingga m t1(a-b) b2 (mod m) atau m a2-b2 sehingga m t2(a2-b2)

Teori Bilangan- 79

a3 a4

b3 (mod m) atau m a3-b3 sehingga m t3(a2-b2) b4 (mod m) atau m a4-b4 sehingga m t4(a4-b4)

............................................................................. an bn (mod m) atau m an-bn sehingga m tn(an-bn)

Dengan menggunakan definisi keterbagian pada bilangan bulat maka: m tn(an-bn) + tn-1(an-1-bn-1) + tn-2(an-2-bn-2) + tn-3(an-3-bn-3) + ..... + t1(a1-b1), hal ini berarti m f(a) f(b) atau f(a)

f(b) (mod m)

Perhatikan beberapa contoh berikut ini! Perhatikan beberapa contoh berikut ini! 1. 41

1 (mod 8) hal ini berarti 8 (41-1) atau 8 40. Dengan kasus

yang sama maka 8 (1- 41) atau 8 - 40, sehingga 1

41 (mod 8).

2. Karena 0 habis dibagi oleh sebarang bilangan bulat m, dan 0 dapat diperoleh dari hasil pengurangan sebarang dua bilangan yang sama, maka dapat ditentukan 3. 25 99 4. 26 30 70

3 5-5 5 7 9-9 7

5 (mod 3) 7 (mod 9)

110

11 20 20

20 (mod 9)

11 (mod 7), karena 7 25-11 atau 7 14. 1 (mod 44), karena 44 99-1 atau 44 98 1 (mod 5), karena 5 26-1 atau 525

5 25

5 3.25 5 10.25 5 11.25 5 100.25

Apakah 7 2(30-2) Apakah 7 10(30-2)

Teori Bilangan- 80

Apakah 2.30

2.2 (mod 7)

Apakah 10.30 5. 26 36

10.2 (mod 7)

1 (mod 5), karena 5 26-1 atau 525 1 (mod 5), karena 5 36-1 atau 535

Apakah 5 26+36 atau 51+1 Apakah 5 (26+36) (1+1) atau apakah 5 62 2 6. 13 7

3 (mod 5), karena 5 13 3 2 (mod 5), karena 5 72, Apakah 91

6 (mod 5)

Jika kita perhatikan contoh di atas nampak bahwa dalam kongruensi berlaku sifat-sifat yang sama dalam pembagian bilangan bulat

3.2 Sistem Residu Untuk membahas pengertian sistem residu, perlu diingat kembali tentang algoritma pembagian. Menurut teorema algoritma pembagian

terdapat bilangan bulat q dan r sehingga untuk setiap bilangan bulat a dan m berlaku hubungan a = qm +r, dengan 0 0 < r. Selanjutnya

persamaan a = qm + r dapat dinyatakan dalm bentuk kongruensi a

q

(mod m) Akibatnya, setiap bilangan bulat a kongruen modulo m dengan salah satu bilangan bulat berikut: 0, 1, 2, 3, ..... , m-1. Dengan demikian jelaslah bahwa tidak ada sepasangpun dari bilangan-bilangan 0, 1, 2, 3, ..... , m-1 yang kongruen satu sama lain. Maka m buah bilangan tersebut dapat membentuk suatu sistem residu lengkap modulo m. Definisi 3.3 1. Jika x

y (mod m) maka y disebut residu dari x modulo m.

Teori Bilangan- 81

2. Misal A = { x1, x2, x3, ..... , xm }, disebut suatu sistem residu modulo m yanglengkap jika dan hanya jika untuk setiap y (0 y 0.

Teorema 3 Kongruensi linear ax

b (mod m), dengan a,b,m

Z,a

0, dan m > 0.

dapat diselesaikan jika d = (a,m) membagi b. Pada kasus ini memiliki selesaian. Jika (a,m) = 1, maka kongruensi linear ax mempunyai satu selesaian. Bukti. Kongruensi linear ax b. Andaikan d b. d = (a,b) d a d ax. d ax. dan d b d ax b. d= (a,m) d m. d m dan d b m ax b. m ax b bertentangan dengan m ax b, Jadi d b. Diketahui d b dan d = (a,m) d a d m. d a , d m, dan d b axa m b , , dan d d d

b (mod m) hanya

b (mod m) mempunyai selesaian, berarti m ax

Z.

b (mod m) m ax b.a m b m ax b , , d d d d d d

m ax b dan

Teori Bilangan- 92

m ax b a x d d d d

b m (mod ). d d a x d

Misal selesaian kongruensi

b m (mod ) adalah x d d

x o ; xo