defenisi dan sifat kekongruenan teobil

Defenisi dan Sifat Kekongruenan

8

A. DEFENISI DAN SIFAT KEKONGRUENAN

Konsep Kekongruenan suatu cara untuk menelaah keterbagian dalam himpunan bilangan

bulat. konsep dan sifat-sifat keterbagian dapat kita pelajari lebih mendalam dengan konsep

kekongruenan.

Defenisi : 5.1.

Jika m suatu bilangan bulat positif, maka a kongruen b modulo m (ditulis )(modmba )

bila m membagi (a-b). Jika tidak membagi (a-b) maka dikatakan bahwa a tidak kongruen

dengan b modulo m (ditulis )(modmba ).

Contoh : )5(mod429 karena (29 – 4) = 25 terbagi oleh 5

)6(mod847 karena (47 – 8) = 39 tidak terbagi oleh 6

Terema 5.1.

)(modmba bila dan hanya bila ada bilangan bulat k sehingga bkma .

Bukti :

Jika m > 0 bilangan bulat positif, menurut Defenisi 5.1. m │(a-b) bila dan hanya bila

)(modmba .

Jika m │(a-b) menurut defenisi 2.1 ada k bilangan bulat positif sedemikian hingga (a-b)

= km

(a-b) = km sama artinya a = km + b

Contoh:

)7(mod972 sama artinya dengan 72 = 7.9 + 9

)5(mod449 sama artinya dengan 49 = 5.9 + 4

Teorema 5.2.

Setiap bilangan bulat kongruen modulo m dengan tepat satu diantara 0,1.2.3, …. (m-1).

Bukti :

Bila a dan m bilangan bilangan bulat dan m > 0 , menurut algoritma pembagian dapat dinyatakan dengan :

a = qm + r dengan 0 ≤ r < m sehingga menurut teorema 2.7

a – r = qm , maka dengan demikian )(modmra

karena 0 ≤ r < m, maka ada m buah pilihan bilangan untuk r yaitu : 0,1.2.3, …. (m-1).

Jadi setiap bilangan bulat akan kongruen modulo m dengan tepat satu diantara 0,1.2.3, ….

(m-1).


9

Contoh :

)8(mod638 sama juga dengan 38 = 4.8 + 6

{0, 1, 2, 3, 4, 5, 6, 7}

Defenisi 5.2.

Jika )(modmba dengan 0 ≤ r < m, maka r disebut residu (sisa) terkecil dari a modulo m

ini {0,1.2.3, …. (m-1)} disebut himpunan residu terkecil modulo m

Contoh

Residu terkecil dari 71 modulo 2 adalah 1, karena sisa 71 : 2 adalah 1

Residu terkecil dari 71 modulo 3 adalah 2, karena sisa 71 : 3 adalah 2

Residu terkecil dari -53 modulo 10 adalah 7, karena sisa -53 : 10 adalah 7 (residu terkecil

dari suatu bilangan diambil bilangan bulat positif).

Residu terkecil dari dari 34 modulo 5 adalah 4, sebab sisa 34 : 5 adalah 4

Walaupun )5(mod934 tetapi 9 bukan residu terkecil dari )5(mod34 sebab 9 bukan sisa

dari 34 : 5 adalah 4.

Contoh :

Modulo 5 mempunyai himpunan residu terkecil adalah {0,1,2,3,4,}

Modulo 9 mempunyai himpunana residu terkecil adalah {0,1,2,3,4,5,6,7,8}

Modulo 20 mempunyai himpunan residu terkecil adalah {0,1,2,3, ….…,19}

Teorema 5.3.

)(modmba bila dan hanya bila a dan b memiliki sisa yang sama jika dibagi m

Bukti

Jika )(modmba maka a dan b memiliki sisa yang sama jika dibagi m

)(modmba dan )(modmra maka r adalah residu terkecil modulo m atau 0 ≤ r < m

)(modmra maka a = mq + r ; r adalah sisa dari a bila dibagi m

)(modmrb maka b = mt + r ; r adalah sisa dari b bila dibagi m

(a-b) = m (q – t ) maka m │(a – b) menurut Defenisi 5.1 atau )( m odmba

Berdasaran teorema-teorema terdahulu, ungkapan berikut mempunyai arti yang sama yaitu:

“ )8(mod7n ” “ n = 7 + 8k untuk setip bilangan bulat k, dan

“ n dibagi 8 bersisa 7 ”


10

Defenisi 5.3

Himpunan bilangan-bilangan bulat {mrrrr .,.........,, 321

} disebut sistem residu lengkap

modulo m, bila setiap elemennya kongruen modulo m dengan satu dan hanya satu dari 0, 1,

2, 3,…………,(m-1)

Contoh.

(i) Himpunan {45, -9, 12, -22, 24} adalah suatu sistem residu lengkap modulo 5 .

dapat diperiksa bahwa :

)5(mod045

)5(mod19

)5(mod212

)5(mod322

)5(mod424

(ii) Himpunan {0,1,2,3,4} juga merupakan suatu system residu lengkap modulo 5,

sekaligus himpunan residu terkecil modulo 5.

(iii) Himpunan {0,1,2,3,4} adalah merupakan suatu sistem residu lengkap modulo 5.

(iv) Himpunan {5, 11, 6, 1, 8, 15} bukan merupakan system residu lengkap modulo

6, sebab )6(mod115 yang dua-duanya berada dalam himpunan tersebut .

Kekongruenan modulo suatu bilangan bulat positif adalah suatu relasi antara bilangan-

bilangan bulat . Dapat ditunjukan bahwa relasi kongruen itu merupakan relasi ekivalensi.

Sutu relasidi sebut relasi ekivalensi jika relasi itu memiliki memiliki sifat reflektif.

Jika m, a, b, dan c adalah bilangan-bilangan bulat dengan m positif, maka:

(i) )(modmaa , sifat reflektif.

Bukti :

Karena a – a = 0 ditulis juga a = 0 + a atau a = m0 + a, dapat ditulis juga )(modmaa

(ii) Jika )(modmba maka )(modmab

, sifat simetris

Bukti :

Karena )(modmba maka a – b = km untuk setiap bilangan bulat k sehingga b – a = -

km atau b = - km + a dapat ditulis juga )(modmab


11

(iii) Jika )(modmba dan )(modmcb , dan )(modmca sifat transitif.

Bukti

)(modmba ini berarti a – b = km untuk setiap bilangan bulat k

)(modmcb ini berarti b – c = hm untuk setiap bilangan bulat h

a – b = km

b – c = hm +

a – c = (k + h)m

dari a – c = (k + h)m ini menunjukan bahwa )(modmca

………………………… terbukti

Relasi ekivalen dari relasi kekongruenan pada himpunan bilangn bulat harus memenuhi

ketiga sifat diatas. Hal ini berakibat himpunan bilangan-bilangan bulat terpartisi dalam

himpunan-himpunan bagian yang setiap himpunan bagian kelas.

Perrhatikan himpunan bilangan bulat dengan relasi kongruen modulo 5, maka relasi ini

himpunan bilangan bulat terpartisi ( terbagi menjadi himpunan bagian-himpunan bagian

yang saling asing dan gabungannya sama dengan himpunan bilangan bulat) menjadi 5

kelas, yaitu :

,...}10,5,0,5,10{...]0[0

,...}11,6,1,4,9{...]1[1

,...}12,7,2,3,8{...]2[2

,...}13,8,3,2,7{...]3[3

,...}14,9,4,1,6{...]4[4

pemberian nama untuka suatu kelas menggunakan nama salah satu kelas tersebut yang

dibubuhi nama tanda garis diatasnya atau dikurung persegi. Misalnya:

823]8[]2[]3[ atau

Relasi kongruenan mepunyai kemiripan sifat dengan sifat persamaan, sebab relasi

kekongruenan dapat dinyatakan sebagai persamaan, yaitu : )(modmba sama artinya

dengan a= km + b , untuk suatu bilangan bulat k.

Misalnya :

1. Jika )(modmba maka a + c = b + c (mod m) untuk setiap bilangan bulat c.

2. Jika )(modmba maka Jika )(modmbcac

untuk setiap bilangan bulat c.


12

Teorema 5.4.

Jika )(modmba dan )(modmdc maka a + c = b + d (mod m)

Bukti :

Jika )(modmba ini berarti a = km + b, untuk suatu bilangan bulat k

Jika )(modmdc ini berarti c = tm + d, untuk suatu bilangan bulat t.

a = km + b

c = tm + d +

a + c = km + tm + b + d

a + c = m (k + t) + (b + d)

(a + c) – (b + d) = m h

(a + c) – (b + d) = mod m dapat ditulis )(modmdbca ……… terbukti

Teorema 5.5

Jika )(modmba dan )(modmdc maka a x+ c y= bx + d y(mod m) untuk setiap

blangan bulat x dan y.

Bukti :

Jika )(modmba ini berarti a = km + b, untuk suatu bilangan bulat k

Jika )(modmdc ini berarti c = tm + d, untuk suatu bilangan bulat t.

a = km + b jika dikalikan dengan x maka ax = kmx + bx

c = tm + d jika dikalikan dengan y maka cy = tmy + dy

ax = kmx + bx

cy = tmy + dy +

ax + cy = (kmx + tmy) + (bx + dy)

ax + c y= m (k x+ ty) + (bx + dy)

(ax + cy) – (bx+ dy) = m (kx + ty) dari persamaan ini berarti bahwa:

m│[(ax + cy) – (bx+ dy)]

dapat ditulis a x+ c y bx + d y(mod m) ……………..terbukti

pada persamaan/kesamaan bilangan-bilangan bulat berlaku sifat kanselasi (penghapusan) sebagai berikut:


13

Jika ab = ac dengan a ≠ 0 maka b = c . apakah dalam kongruenan berlaku sifat yang mirip dengan sifat kanselasi tersebut.

Misalkan , jika )(modmacab dengan a Ξ 0 (mod m), apakah )(modmcb ?.

Contoh : )4(mod1224 adalah sutu pernyataan yang benar

)4(mod6.212.2 ini berarti )4(mod02

apakah )4(mod612 4 tidak habis membagi 12 – 6

Teorema 5.6

Jika )(modmbcac dengan (c,m) = 1, maka )(modmba

Bukti :

)(modmbcac ini berarti m │(ac – bc) atau m│c(a – b)

m│c(a - b) dengan (c,m) = 1, maka m │(a – b), ini berarti )(modmba

contoh: Tentukanlah bilangan-bilangan bulat y yang memenuhi perkongruenan

)7(mod13 y

Jawab:

Jika )7(mod13 y maka kita menggantika 1pada pengruenan tersebut dengan 15,

sehingga diperoleh )7(mod153 y dengan

Karena )7(mod5.33 y dengan (3,7) = 1 dan )7(mod5y

Sehingga diperoleh y = 7 k + 5 untuk setiap bilangan bulat k

Himpunana peyelesaan dari pengruenan tersebut adalah { y = 7 k + 5 │ k bilangan bulat }

Teorema 5.7

Jika )(modmbcac dengan (c,m) = d, maka )(mod

d

mba

Bukti : Jika )(modmbcac berarti m │(ac – bc) atau m│c(a – b)

Maka d

m│

d

c(a – b)

Karena d adalah FPB dari c dan m, maka d

m dan

d

c adlah bilangan-bilangan bulat .

Karena (c,m) = d maka 1,

d

m

d

c

Karena 1,

d

m

d

c dan

d

m│

d

c(a – b) maka

d

m│

d

c dan(

d

m│(a – b)


14

Dapat ditulis maka )(modd

mba .

defenisi dan sifat kekongruenan teobil

Design