Teori Bilangan #7

Kekongruenan

Definisi Andaikan a, b, dan m bilangan bulat dengan m > 0. Dikatakan bahwa a º b (mod m) jika dan hanya jika m\(a – b) atau $k bulat demikian sehingga a – b = km.

Contoh:
11 º 5 (mod 3) karena 3\(11 – 5) = 6.

Teorema 1

Kekongruenan adalah suatu relasi ekuivalen.

Bukti:

(i)      a º a (mod m) karena m\(a – a) = 0

(ii)    Misalkan a º b (mod m) maka m\(a – b) demikian sehingga m\–(a – b) = b – a.

        Jadi b º a (mod m).

(iii)   Misalkan a º b (mod m) dan b º c (mod m) maka m\(a – b) dan m\(b – c) demikian sehingga

      m\(a – b) + (b – c) = a – c.
        Jadi a º c (mod m).

Teorema 2

a º b (mod m) jika dan hanya jika a dan b mempunyai sisa yang sama pada pembagian dengan m.

Bukti:
(i)      Misalkan a º b (mod m) maka $k bulat demikian sehingga a = b + km.
        Misalkan pula b = qm + r dengan 0 £ r < m, maka a = b + km = (qm + r) + km = m(k + q) + r.
        Jadi a dan b mempunyai sisa yang sama (sebesar r) pada pembagian dengan m.
(ii)    Misalkan a = q₁m + r dan b = q₂m + r maka a – b = (q₁ - q₂)m sehingga m\(a – b).
        Jadi a º b (mod m).

Teorema 3

Jika a º b (mod m) maka untuk setiap bilangan bulat x berlaku: (i)         a + x º b + x (mod m) (ii)       ax º bx (mod m) (iii)     -a º -b (mod m)

Bukti:
a º b (mod m)             ®        m\(a – b)

(i)       Karena m\(a – b) maka m\(a + x) – (b + x), sehingga a + x º b + x (mod m).

(ii)      Karena m\(a – b) maka m\x(a – b) ® m\(ax – bx), sehingga ax º bx (mod m).

(iii)     Karena m\(a – b) maka m\–(a – b) ® m\(–a – (–b)), sehingga -a º -b (mod m).

Teorema 4 – Hukum Pembatalan (Cancellation)

Jika c dan m koprima sedangkan ca º cb (mod m) maka a º b (mod m).

Bukti:
ca º cb (mod m)          ®        m\(ca – cb) sehingga m\c(a – b)
Karena c dan m koprima atau (c, m) = 1, maka berdasarkan Teorema 2 Dalil dasar Ilmu Hitung, haruslah m\(a – b). 
Jadi a º b (mod m).

Teorema 5

Jika (c, m) = 1 maka persamaan cx º b (mod m) selalu mempunyai solusi dan solusi ini tunggal mod m.

Bukti:

(i)         (c, m) = 1 maka $s, t bulat demikian sehingga 

          1 = sc + tm              kalikan dengan b

 b = bsc + btm             

 b - bsc = (bt)m

        m\(b – bsc)
        b º bsc (mod m)
        c(bs) º b (mod m)       karena kongruensi adalah relasi ekuivalen
         \ x = bs adalah suatu solusi dari cx º b (mod m).

(ii)       Misalkan x₁ dan x₂ masing-masing adalah solusi dari cx º b (mod m) maka

        cx₁ º b (mod m)                                                          ……………………. (*)
        cx₂ º b (mod m)             ®     b º cx₂ (mod m)         ……………………. (**)
         Berdasarkan Teorema 1, dari (*) dan (**) diperoleh cx₁ º cx₂ (mod m).
         Karena (c, m) = 1 maka x₁ º x₂ (mod m).
         Jadi cx º b (mod m) mempunyai solusi tunggal mod m.

Akibat

Jika m = p (bilangan prima) dan (c, p) = 1, maka cx º b (mod p) mempunyai suatu solusi dan solusi itu tunggal mod p.

Teorema 6

Jika (m1, m2) = 1 maka kedua persamaan x º b1 (mod m1) dan x º b2 (mod m2) mempunyai solusi persekutuan (solusi bersama). Setiap dua solusi adalah kongruen mod m1m2.

Bukti:

Jelas b₁ adalah suatu solusi dari persamaan x º b₁ (mod m₁), karena b₁ º b₁ (mod m₁).

Solusi umumnya adalah b₁ + ym₁ dengan y bulat.

b₁ + ym₁ º b₁ (mod m₁), karena m₁\(b₁ + ym₁ – b₁) = ym₁.

Substitusi solusi tersebut ke persamaan kedua menghasilkan

b₁ + ym₁ º b₂ (mod m₂)

ym₁ º b₂ – b₁ (mod m₂)

m₁y º  b₂ – b₁ (mod m₂)           ini adalah suatu persamaan dalam variabel y

Karena (m₁, m₂) = 1 maka, menurut Teorema 5, persamaan tersebut selalu mempunyai solusi (dapat dipenuhi oleh suatu nilai y).

Misalkan x₁ dan x₂ adalah solusi persekutuan, maka

x₁ º b₁ (mod m₁) dan x₂ º b₁ (mod m₁), sehingga x₁ º x₂ (mod m₁)    ®      m₁\(x₁ – x₂)

x₁ º b₂ (mod m₂) dan x₂ º b₂ (mod m₂), sehingga x₁ º x₂ (mod m₂)    ®   m₂\(x₁ – x₂)

Karena (m₁, m₂) = 1 maka, menurut Teorema 3 Dalil Dasar Ilmu Hitung, m₁m₂\(x₁ – x₂).

Jadi x₁ º  x₂ (mod m₁m₂).

______________________________________________________________________________________________________

Kuliah 6 Teori bilangan oleh Drs. Bachtiar Sjarif, Institut Teknologi Bandung, 21 Desember 1988

-->