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) a^p ≡ b^p (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 + k₁m

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

maka

↔ ac = (b + k₁m)(d + k₂m)

↔ ac = bd + bk₂m + dk₁m + k₁k₂m²

↔ ac = bd + Km dengan K = bk₂ + dk₁ + k₁k₂m

↔ 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