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:

\[ ax \space = \space b \space + \space km \space \to \space x \space = \space \frac{b \space + \space km}{a} \]

(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)

\[ x \space = \space \frac{3 \space + \space kยท9}{4} \]


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)

\[ x \space = \space \frac{3 \space + \space kยท4}{2} \]

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 โ‰ก a1 (mod m1)

x โ‰ก a2 (mod m2)

โ€ฆ

x โ‰ก an (mod mn)

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 + 3k1 (iii)

Substitusikan (iii) ke dalam (ii):

2 + 3k1 โ‰ก 3 (mod 5) โ†’ 3k1 โ‰ก 1 (mod 5)

diperoleh k1 โ‰ก 2 (mod 5) atau k1 = 2 + 5k2

Substitusikan k1 = 2 + 5k2 ke dalam persamaan (iii):

x = 2 + 3k1

= 2 + 3 (2 + 5k2)

= 2 + 6 + 15k2

= 8 + 15k2

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

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up