Matematika Diskrit : Sistem Kekongruenan Linier

Kekongruenan Linier

Kekongruenan linier (linear congruence) berbentuk: ax ≡ b (mod m)

(m > 0, a dan b sembarang bilangan bulat, dan x adalah peubah bilangan bulat)

Pemecahan:

(Cobakan untuk k = 0, 1, 2, … dan k = –1, –2, … yang menghasilkan x sebagai bilangan bulat)

Contoh

Tentukan solusi: 4x ≡ 3 (mod 9) dan 2x ≡ 3 (mod 4)

Penyelesaian:

(i) 4x ≡ 3 (mod 9)

k = 0 → x = (3 + 0 · 9)/4 = 3/4 (bukan solusi)

k = 1 → x = (3 + 1 · 9)/4 = 3

k = 2 → x = (3 + 2 · 9)/4 = 21/4 (bukan solusi)

k = 3 dan k = 4 tidak menghasilkan solusi

k = 5 → x = (3 + 5 · 9)/4 = 12

⋮

k = –1 → x = (3 – 1 · 9)/4 = –6/4 (bukan solusi)

k = –2 → x = (3 – 2 · 9)/4 = –15/4 (bukan solusi)

k = –3 → x = (3 – 3 · 9)/4 = –6

⋮

k = –6 → x = (3 – 6 · 9)/4 = –15

⋮

dst.

Nilai-nilai x yang memenuhi: 3, 12, … dan –6, –15, …

Atau solusi cukup dinyatakan sebagai x ≡ 3 (mod 9) atau x = 3 + 9k, dengan k sembarang bilangan bulat.

(ii) 2x ≡ 3 (mod 4)

Karena 4k genap dan 3 ganjil, maka penjumlahannya menghasilkan ganjil, sehingga hasil penjumlahan tersebut jika dibagi dengan 2 tidak menghasilkan bilangan bulat. Dengan kata lain, tidak ada nilai-nilai x yang memenuhi 2x ≡ 3 (mod 5).

---

Cara Lain Menghitung Solusi ax ≡ b (mod m)

Seperti dalam persamaan aljabar biasa (tanpa modulo),

4x = 12 → kalikan setiap ruas dengan 1/4 (yaitu invers 4)

maka (1/4) · 4x = 12 · (1/4) → x = 12/4 = 3

4x ≡ 12 (mod 9) → kalikan setiap ruas dengan balikan dari 4 (mod 9) (dalam hal ini sudah kita hitung, yaitu –2)

(–2) · 4x ≡ (–2) · 12 (mod 9) ↔ –8x ≡ –24 (mod 9)

Karena –8 ≡ 1 (mod 9), maka x ≡ –24 (mod 9). Semua bilangan bulat yang kongruen dengan -24 (mod 9) adalah solusinya, yaitu …, –33, –15, –6, 3, 12, …

---

Sistem Kekongruenan Linier

Sistem kekongruenan linier terdiri dari lebih dari satu kekongruenan,
yaitu:

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

…

x ≡ a_n (mod m_n)

Contoh

Sebuah bilangan bulat jika dibagi dengan 3 bersisa 2 dan jika ia dibagi dengan 5 bersisa 3. Berapakah bilangan bulat tersebut?

Penyelesaian:

Misal bilangan bulat = x

x mod 3 = 2 → x ≡ 2 (mod 3)

x mod 5 = 3 → x ≡ 3 (mod 5)

Jadi, terdapat sistem kekongruenan:

x ≡ 2 (mod 3) (i)

x ≡ 3 (mod 5) (ii)

Untuk kekongruenan pertama:

x = 2 + 3k₁ (iii)

Substitusikan (iii) ke dalam (ii):

2 + 3k₁ ≡ 3 (mod 5) → 3k₁ ≡ 1 (mod 5)

diperoleh k₁ ≡ 2 (mod 5) atau k₁ = 2 + 5k₂

Substitusikan k₁ = 2 + 5k₂ ke dalam persamaan (iii):

x = 2 + 3k₁

= 2 + 3 (2 + 5k₂)

= 2 + 6 + 15k₂

= 8 + 15k₂

atau

x ≡ 8 (mod 15) (periksa bahwa 8 mod 3 = 2 dan 8 mod 5 = 3)

Semua nilai x yang kongruen dengan 8 (mod 15) juga adalah solusinya, yaitu x = 8, x = 23, x = 38, …, x = -7 dst.

---

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Teori Bilangan, daftar lengkapnya adalah sebagai berikut.

---

Tonton juga video pilihan dari kami berikut ini