Kekongruenan.docx

KEKONGRUENAN

Definisi 1 Jika terdapat m suatu bilangan bulat positif, maka a kongruen dengan b modulo m, bila m membagi (a-b). Jika m tidak membagi (a-b) maka diktakan bahwa a tidak kongruen dengan b modulo m. Teorema 1.1 a ≡ b (mod m) jika dan hanya jika ada bilangan bulat k sehingga a = mk + b Bukti: a ≡ b (mod m) akan ditunjukkan bahwa a = mk + b Dari defenisi 1 diatas didapat bahwa : a ≡ b (mod m), bila dan hanya bila m|(a-b). Karena m|(a-b), maka m > 0 karena m|(a-b), maka ada bilangan bulat k, sehingga (a-b) = mk Jadi a ≡ b (mod m), bila dan hanya bila a-b = mk, untuk setiap bilangan bulat k. Karena a-b = mk sama artinya dengan a = mk + b, Atau dengan kata lain: a ≡ b (mod m) bila dan hanya bila a = mk + b.

Teorema 1.2 Setiap bilangan bulat kongruen modulo m dengan tepat satu diantara 0,1,2,3,...,(m-1). Bukti : Kita telah mempelajari bahwa jika a dan m bilangan- bilangan bulat, dan m > 0, menurut algoritma pembagian, maka a dapat dinyatakan sebagai : a = mq + r, dengan 0 ≤ r < m Ini berarti bahwa a-r = mq, yaitu a ≡ r (mod m). Karena 0 ≤ r < m, maka ada m buah pilihan untuk r, yaitu : 0,1,2,3,...,(m-1). Jadi setiap bilangan bulat akan kongruen dengan m dengan tepat satu diantara 0,1,2,3,...,(m-1).

Definisi 2 Jika a ≡ r (mod m) dengan 0 ≤ r < m, maka r disebut residu terkecil dari a modulo m. Untuk kekongruenan residu terkecil ini, {0,1,2,3,...,(m-1)} disebut himpunan residu terkecil modulo m. Teorema 2.1 1

a ≡ b (mod m) bila dan hanya bila a dan b memiliki sisa yang sama jika dibagi m. Bukti : Akan dibuktikan dari dua sisi, Pertama, jika a ≡ b (mod m), maka akan ditunjukkan bahwa a dan b memiliki sisa yang sama jika dibagi m.

Karena a ≡ b (mod m), maka a ≡ r (mod m) dan b ≡ r (mod m), dengan r adalah residu terkecil modulo m atau 0 ≤ r < m. Selanjutnya, a ≡ r (mod m), berarti a = mq + r, dan b ≡ r (mod m), berarti b = mt + r, untuk suatu bilangan bulat q dan t. dapat disimpulkan bahwa a dan b memiliki sisa yang sama jika dibagi m. (Terbukti) Kedua, jika a dan b memiliki sisa yang sama, maka akan dirunjukkan a ≡ b (mod m). Misalkan: a memiliki sisa r jika dibagi m, berarti a ≡ mq + r, dan b memiliki sisa r jika dibagi m, berarti b ≡ mt + r, untuk suatu bilangan bulat q dan t, dari kedua persamaan ini diperoleh : (a-b) = (mq – mt) + (r-r) (a-b) = m(q – t) Karena q dan t adalah suatu bilangan bulat, maka (q-t) adalah suatu bilangan bulat, Maka m|(a-b) atau a ≡ b (mod m). (Terbukti!)

Definisi 3 Himpunan bilangan bulat {r1, r2, r3,..., rm} disebut sistim residu lengkap modulo m, bila setiap elemennya kongruen modulo m, dengan satu dan hanya satu dari 0,1,2,...,(m-1).

2

DAFTAR PUSTAKA

-http://dodyliza.blogspot.co.id/2011/10/makalah-teori-bilangan-defenisi-dan.html

3