Kekongruenan

KEKONGRUENAN

   Kadang-kadang dua bilangan bulat, a dan b, mempunyai sisa yang sama jika dibagi dengan bilangan bulat positif m. Kita katakana bahwa a dan b kongruen dalam modulo m, dan yang dilambangkan sebagai

               a ≡ b (mod m)

(notasi “≡” dibaca “ kongruen “)

Jika a tidak kongruen dengan b dalam modulus m, maka ditulis

               a ≡/ b (mod m)

Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka 38 ≡ 13 (mod 5). Defenisi formal dari kekongruenan dinyatakan sebagai berikut :

“Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m habis membagi a – b. “

Contoh :

   Bilangan 38 kongruen dengan 13 modulo 5 karna 5 membagi 38 – 13 = 25, sehingga dapat kita tulis bahwa 38 ≡ 13 (mod 5 ). Tetapi, 41 tidak kongruen dengan 30 modulo 5 karna 5 tidak habis membagi 41 – 30 = 11, sehingga dapat kita tulis 41  ≡/ 30 (mod 5).

   17 ≡ 2 (mod 3)                        (3 habis membagi 17 – 2 = 15  → 15 ÷ 3 = 5)

   -7  ≡ 15 (mod 11)                    (11 habis membagi -7 -15 = -22)  → -22 ÷ 11 = 2)

   12 ≡/ 2 (mod 7)                       (7 tidak habis membagi 12 – 2 = 10)

   -7 ≡/ 15 (mod 3)                      ( 3 tidak habis membagi -7 – 15 = -22)

Kekongruenan a ≡ b (mod m) dapat pula dituliskan dalam hubungan

               a = b + km

Yang dalam hal ini sembarang k adalah bilangan bulat . pembuktiannya adalah sebagai berikut : menurut defenisi formal,  a ≡ b (mod m) jika m | (a – b).

A.    Teorema Kekongruenan

1.      Teorema 1

               “ misalkan m adalah bilangan bulat positif.

1.      Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat maka

(i)                 (a + c) ≡ (b + c) (mod m)

(ii)               ac ≡ bc (mod m)

(iii)             a^p ≡ b^p (mod m) untuk suatu bilangan bulat tak negatip p.

2.      Jika a ≡ b (mod m) dan c ≡ d (mod m), maka

(i)                 (a + c) ≡ (b + d) (mod m)

(ii)               ac ≡ bd (mod m)

Bukti :

Hanya diperlihatka untuk 1(ii) dan 2(i) saja. Bukti untuk 1(i), 1(iii), 2(ii) diserahkan sebagai latihan bagi pembaca.

   1(ii)      a ≡ b (mod m) berarti :

                      a = b + km

 a – b = km

 (a – b) c = ckm                     (kedua ruas dikalikan dengan c)

  ac = bc + Km                       (dalam hal ini K = kc)

  ac ≡ bc (mod m)

2(i)      a ≡ b (mod m)     a = b + k₁m

c ≡ d (mod m)     c = d + k₂m +

  (a + b) = (b + d) + (k₁ +k₂)m

  (a + c) = (b + d) + km (dalam hal ini, k = k₁ +k₂₎

  (a + c) = (b + d) (mod m)  

Contoh :

    Misalkan 17 ≡ 2 (mod 3) dan 10 ≡ 4 (mod 3), maka menurut teorema 1,

17 + 5 = 2 + 5 (mod 3)          22 = 7 (mod 3)            (Teorema 1. 1(i))

17 . 5 = 5 . 2 (mod 3)                       85 = 10 (mod 3)          (Teorema 1. 1(ii))

17 + 10 = 2 + 4 (mod 3)                    27 = 6  (mod 3)           (Teorema 1. 2(i))

17     10 = 2 . 4 (mod 3)                170 = 8 (mod 3)          (Teorema 1. 2(ii))

   Perhatikan bahwa teorema 1 tidak memasukkan operasi pembagian pada aritmatika modulo karna jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi. Misalnya :

(i)                 10 ≡ 4 (mod 3) dapat dibagi menjadi 2 karena 10/2 = 5 dan 4/2 = 2, dan 5 ≡ 2

14 ≡ 8 (mod 6) tidak dapat dibagi menjadi 2, karena 14/2 = 7 dan 8/2 = 4, tetapi 7 ≡/4 (mod 6).