Matematika Diskrit : Kongruen

Kongruen

Misalkan a dan b bilangan bulat dan m adalah bilangan > 0, maka a โ‰ก b (mod m) jika dan hanya jika m | (a โ€“ b).

Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a โ‰ข b (mod m) .

Contoh:

  • 17 โ‰ก 2 (mod 3) โ†’ ( 3 habis membagi 17 โ€“ 2 = 15)
  • 21 โ‰ก 9 (mod 12) โ†’ ( 12 habis membagi 21 โ€“ 9 = 12)
  • โ€“7 โ‰ก 15 (mod 11) โ†’ ( 11 habis membagi โ€“7 โ€“ 15 = โ€“22)
  • 12 โ‰ก 2 (mod 7) โ†’ (7 tidak habis membagi 12 โ€“ 2 = 10 )
  • โ€“7 โ‰ก 15 (mod 3) โ†’ (3 tidak habis membagi โ€“7 โ€“ 15 = โ€“22)

a โ‰ก b (mod m) dalam bentuk โ€œsama denganโ€ dapat dituliskan sebagai a = b + km

(k adalah bilangan bulat)

Contoh:

  • 17 โ‰ก 2 (mod 3) โ†’ 17 = 2 + 5 ยท 3 (k = 5)
  • โ€“7 โ‰ก 15 (mod 11) โ†’ โ€“7 = 15 + (โ€“2)11 (k = โ€“2)

a mod m = r dapat juga ditulis a โ‰ก r (mod m)

Contoh:

  • 23 mod 5 = 3 โ†’ 23 โ‰ก 3 (mod 5)
  • 27 mod 3 = 0 โ†’ 27 โ‰ก 0 (mod 3)
  • 6 mod 8 = 6 โ†’ 6 โ‰ก 6 (mod 8)
  • 0 mod 12 = 0 โ†’ 0 โ‰ก 0 (mod 12)
  • โ€“ 41 mod 9 = 4 โ†’ โ€“41 โ‰ก 4 (mod 9)
  • โ€“ 39 mod 13 = 0 โ†’ โ€“ 39 โ‰ก 0 (mod 13)

Teorema 4

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) ap โ‰ก bp (mod m) , p bilangan bulat tak-negatif

2) Jika a โ‰ก b (mod m) dan c โ‰ก d (mod m), maka

(i) (a + c) โ‰ก (b + d) (mod m)

(ii) ac โ‰ก bd (mod m)

Contoh

Misalkan 17 โ‰ก 2 (mod 3) dan 10 โ‰ก4 (mod 3), maka menurut Teorema 4,

  • 17 + 5 โ‰ก 2 + 5 (mod 3) โ†” 22 โ‰ก 7 (mod 3) periksa 3 | (22 โ€“ 7)
  • 17 ยท 5 โ‰ก 2 ยท 5 (mod 3) โ†” 85 โ‰ก 10 (mod 3) periksa 3 | (85 โ€“ 10)
  • 17 + 10 โ‰ก 2 + 4 (mod 3) โ†” 27 โ‰ก 6 (mod 3) periksa 3 | (27 โ€“ 6)
  • 17 ยท 10 โ‰ก 2 ยท 4 (mod 3) โ†” 170 โ‰ก 8 (mod 3) periksa 3 | (170 โ€“ 8)

Teorema 4 tidak memasukkan operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi.

Contoh:

10 โ‰ก 4 (mod 3) dapat dibagi dengan 2

karena 10/2 = 5 dan 4/2 = 2, dan 5 โ‰ก 2 (mod 3)


Latihan

Latihan 1

Tentukan semua bilangan yang kongruen dengan 5 (mod 11).

Penyelesaian:

Misalkan bilangan yang kongruen dengan 5 (mod 11) adalah x.

x โ‰ก 5 (mod 11)

Jadi, 11 | (x โ€“ 5). Nilai x yang memenuhi adalah 16, 27, 38, โ€ฆ, lalu -6, -17, โ€ฆ

Nilai-nilai yang kongruen dengan 5 (mod 11) adalah โ€ฆ, -17, โ€“6, 16, 27, 38, โ€ฆ


Latihan 2

Buktikan Teorema 4.2(ii), jika a โ‰กb (mod m) dan c โ‰ก d (mod m) maka buktikan bahwa ac โ‰ก bd (mod m)

Penyelesaian:

a โ‰ก b (mod m) โ†’ a = b + k1m

c โ‰ก d (mod m) โ†’ c = d + k2m

maka

โ†” ac = (b + k1m)(d + k2m)

โ†” ac = bd + bk2m + dk1m + k1k2m2

โ†” ac = bd + Km dengan K = bk2 + dk1 + k1k2m

โ†” ac โ‰ก bd (mod m) terbukti


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