Kekongruenan Bilangan Bulat dan Sifat-Sifatnya

1. Kekongruenan Modulo m

• Jika m suatu bilangan bulat positif, maka a kongruen dengan b modulo m, ditulis a ≡ b (mod m) bila m membagi habis (a − b).

• Jika m tidak membagi habis (a − b) maka dikatakan bahwa a tidak kongruen dengan b modulo m, ditulis a ≢ b (mod m).

Dengan kata lain:

• Jika m > 0 maka m | (a − b) bila dan hanya bila a ≡ b (mod m).

• Jika m | (a − b) maka ada bilangan bulat k sehingga (a − b) = mk.

Sehingga a ≡ b (mod m) bila dan hanya bila (a − b) = mk, untuk suatu bilangan bulat k.

Tetapi oleh karena (a − b) = mk sama artinya dengan a = mk + b, maka: a ≡ b (mod m) bila dan hanya bila a = mk + b.

Contoh:

11 ≡ 5 (mod 3), karena 3 membagi habis 11 − 5 = 6.

77 ≢ 51 (mod 6), karena 6 tidak membagi habis 77 − 51 = 26.

2. Hubungan Kekongruenan dengan Algoritma Pembagian

Jika a dan m bilangan-bilangan bulat dan m > 0, maka menurut Algoritma Pembagian, a dapat dinyatakan sebagai:

a = m.q + r, dengan 0 ≤ r < m

Hal ini berarti bahwa: a – r = mq atau a ≡ r (mod m).

Karena 0 ≤ r < m, maka ada m pilihan untuk r yaitu {0, 1, 2, …, m – 1}.

Jadi, setiap bilangan bulat akan kongruen modulo m dengan tepat satu di antara {0, 1, 2, …, m – 1}

3. Sistem Residu Modulo m

A. Residu Terkecil

Jika a ≡ r (mod m) dengan 0 ≤ r < m maka r disebut residu terkecil dari a modulo m. Untuk kekongruenan modulo m ini, {0, 1, 2, 3, …, (m – 1)} disebut himpunan residu terkecil modulo m.

Ungkapan-ungkapan berikut memiliki arti yang sama:

(i) a ≡ b (mod m)

(ii) a = b + mk, untuk suatu bilangan bulat k

(iii) a dibagi m bersisa b jika dan hanya jika 0 ≤ b < m

Contoh:

Residu dari 36 modulo 8 adalah 4

7 bukan residu dari 43 modulo 6 meskipun 43 ≡ 7 (mod 6), karena 7 > 6.

Himpunan residu terkecil modulo 6 adalah {0, 1, 2, 3, 4, 5}

B. Kelas Residu

Bila himpunan bilangan bulat dibagi 5, sisanya 0, 1, 2, 3, atau 4 sehingga dapat dijadikan dalam 5 kelas yang berbeda dan disebut kelas-kelas residu modulo 5. 

Kelas yang kongruen dengan 0 (mod 5)

[0] = {…, -15, -10, -5, 0, 5, 10, 15, …}

Kelas yang kongruen dengan 1 (mod 5)

[1] = {…, -14, -9, -4, 1, 6, 11, 16, …}

Kelas yang kongruen dengan 2 (mod 5)

[2] = { …, -13, -8, -3, 2, 7, 12, 17, …}

Kelas yang kongruen dengan 3 (mod 5)

[3] = { …, -12, -7, -2, 3, 8, 13, 18, …}

Kelas yang kongruen dengan 4 (mod 5)

[4] = { …, -11, -6, -1, 4, 9, 14, 19, …}

C. Sistem Residu Lengkap

Himpunan bilangan bulat r₁, r₂, r₃,…, r_m disebut sistem residu lengkap modulo m bila dan hanya bila setiap bilangan bulat kongruen modulo m dengan satu dan hanya satu di antara r₁, r₂, r₃, …, atau r_m.

Contoh:

Apakah {42, -17, 14, -45, 58, -25} merupakan sistem residu lengkap modulo 6?

42 = 7.6+0 → 42 ≡ 0 (𝑚𝑜𝑑 6) 

−17 = −3.6+1 → −17 ≡ 1 (𝑚𝑜𝑑 6) 

14 = 2.6+2 → 14 ≡ 2 (𝑚𝑜𝑑 6) 

−45 = −8.6+3 → −45 ≡ 3 (𝑚𝑜𝑑 6) 

58 = 9.6+4 → 58 ≡ 4 (𝑚𝑜𝑑 6) 

−25 = −5.6+5 → −25 ≡ 5 (𝑚𝑜𝑑 6) 

Himpunan diatas merupakan sistem residu lengkap modulo 6 karena setiap anggotanya kongruen modulo 6 dengan himpunan residu terkecil modulo 6.

4. Sifat-Sifat Kekongruenan

Kekongruenan modulo suatu bilangan bulat positif adalah suatu relasi antara bilangan-bilangan bulat. 

A. Sifat Refleksif

a ≡ a (mod m)

Bukti:

a − a = 0 = 0.m, berarti m | (a − a)

Dengan kata lain, a ≡ a (mod m) ∎

B. Sifat Simetris

Jika a ≡ b (mod m) maka b ≡ a (mod m)

Bukti:

a ≡ b (mod m), berati a − b = km, untuk suatu bilangan bulat k

kalikan masing-masing ruas dengan −1

b − a = −km = (−k)m, berarti m | (b − a)

Dengan kata lain, b ≡ a (mod m) ∎

C. Sifat Transitif

Jika a ≡ b (mod m) dan  b ≡ c (mod m) maka a ≡ c (mod m)

Bukti:

a ≡ b (mod m), berati a − b = km, untuk suatu bilangan bulat k (i)

b ≡ c (mod m), berati b − c = lm, untuk suatu bilangan bulat l (ii)

(i) + (ii) → a − c = km + lm = (k + l).m, berarti m | (a − c)

Dengan kata lain, a ≡ c (mod m) ∎

Dikarenakan kekongruenan bilangan bulat bersifat refleksif, simetris, dan transitif, kita dapat mengatakan bahwa relasi kekongruenan bersifat ekivalen.

5. Perlakuan yang Sama di Masing-Masing Ruas

A. Masing-masing ruas ditambah dengan bilangan yang sama

a ≡ b (mod m) jika dan hanya jika (a + c) ≡ (b + c) (mod m)

Bukti:

(i) Jika a ≡ b (mod m) maka (a + c) ≡ (b + c) (mod m)

a ≡ b (mod m) maka a − b = km, untuk suatu bilangan bulat k

Sedangkan, a − b = (a + c) – (b + c)

Berarti, (a + c) – (b + c) = k.m

Jadi, (a + c) ≡ (b + c) (mod m)

(ii) Jika (a + c) ≡ (b + c) (mod m) maka a ≡ b (mod m)

(a + c) ≡ (b + c) (mod m), maka (a + c) − (b + c) = k.m

Diperoleh, a − b = k.m sehingga (a − b) adalah kelipatan dari m.

Jadi, a ≡ b (mod m)

Dari (i) dan (ii), terbukti bahwa :

a ≡ b (mod m) jika dan hanya jika (a + c) ≡ (b + c) (mod m) ∎

B. Penjumlahan seruas

Jika a ≡ b (mod m) dan c ≡ d (mod m) maka (a + c) ≡ (b + d) (mod m)

Bukti :

a ≡ b (mod m),  berarti a = ms + b, untuk suatu bilangan bulat s.

c ≡ d (mod m),  berarti c = mt + d, untuk suatu bilangan bulat t.

Dari kedua persamaan di atas diperoleh:

a + c = (ms + b) + (mt + d)

a + c = m(s + t) + (b + d)

(a + c) – (b + d) = m(s + t)

Ini berarti a + c ≡ b + d (mod m) ∎

C. Masing-masing ruas dikalikan dengan bilangan yang sama

Jika a ≡ b (mod m) maka  ac ≡ bc (mod m)

Bukti :

a ≡ b (mod m), maka (a – b) = k.m, untuk suatu k bilangan bulat

(a – b).c = c.k.m

ac – bc = (ck).m

Jadi, (ac – bc) kelipatan dari m, maka ac ≡ bc (mod m) ∎

D. Melenyapkan Faktor

Jika ac ≡ bc (mod m) dan (c, m) = 1 maka a ≡ b (mod m)

Bukti :

ac ≡ bc (mod m) berarti m | (ac – bc) atau m | c(a – b)

m | c(a – b) dengan (c, m) = 1 maka m | ( a – b), hal ini berarti:

a ≡ b (mod m) ∎

Jadi, kita dapat melenyapkan suatu faktor dalam kekongruenan, jika faktor tersebut dan bilangan modulonya saling prima. Jika faktor dan modulonya tidak saling prima, maka kita harus mengganti bilangan modulonya seperti dalam poin setelahnya.

E. Pembagian Modulo

Jika ac ≡ bc (mod m) dan (c, m) = d  maka a ≡ b (mod 𝑚/𝑑)

Bukti :

ac ≡ bc (mod m) berarti m | (ac – bc) atau m | c(a – b), maka:

(𝑚/𝑑) | (𝑐/𝑑)(a – b), karena d adalah FPB dari c dan m maka 𝑚/𝑑 dan 𝑐/𝑑 adalah bilangan-bilangan bulat.

Karena (c, m) = d maka (𝑐/𝑑, 𝑚/𝑑) = 1

Dan karena (𝑐/𝑑, 𝑚/𝑑) = 1 dan  (𝑚/𝑑) | (𝑐/𝑑)(a – b) maka (𝑚/𝑑) | (a – b). 

Hal ini berarti bahwa:

a ≡ b (mod 𝑚/𝑑) ∎

F. Perkalian Seruas

Jika a ≡ b (mod m) dan c ≡ d (mod m), maka ac ≡ bd (mod m).

Bukti:

a ≡ b (mod m) dan c ≡ d (mod m), maka:

a = b + mk dan c = d + mt, untuk suatu bilangan bulat k dan t.

Jika kedua ruas persamaan dikalikan, maka:

ac = (b + mk).(d + mt) = bd + (bt + kd + kmt).m

Karena (bt + kd + kmt) adalah suatu bilangan bulat, maka:

ac ≡ bd (mod m) ∎

G. Kombinasi Linear

Jika a ≡ b (mod m) dan c ≡ d (mod m) maka ax + cy ≡ bx + dy (mod m) untuk setiap bil bulat x dan y

Bukti:

a ≡ b (mod m) maka a = ms + b untuk suatu bil bulat s (i)

c ≡ d (mod m) maka c = mt + d untuk suatu bil bulat t (ii)

Kedua persamaan dijumlahkan menghasilkan:

Persamaan (i) kalikan dg x dan persamaan (ii) kalikan dg y

ax = msx + bx

cy = mty + dy

Jumlahkan kedua ruas:

ax + cy = m(sx + ty) + (bx + dy)

(ax + cy) – (bx + dy) = m(sx + ty)

Jadi, diperoleh ax + cy ≡ bx + dy (mod m)

Contoh Soal

1. Buktikan bahwa: Jika a ≡ b (mod m) dengan d | m dan d | a, maka d | b

Bukti :

Karena a ≡ b (mod m) maka a = b + mk, untuk suatu bilangan bulat k.

Selanjutnya, oleh karena d | m maka d | mk. 

Dan karena d | a, maka d | (a – mk).

Dengan kata lain, d | b ∎

2. Buktikan bahwa: Jika a ≡ b (mod m) dan n | m, maka a ≡ b (mod n)

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚), berarti 𝑎 − 𝑏 = 𝑘.𝑚, untuk suatu bilangan bulat k

𝑛 | 𝑚, berarti 𝑚 = 𝑙.𝑛, untuk suatu bilangan bulat l

𝑎 − 𝑏 = 𝑘.𝑚 

𝑎 − 𝑏 = 𝑘.𝑙.𝑛 

𝑎 − 𝑏 = (𝑘.𝑙).𝑛

D.k.l 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) ∎

3. Jika a ≡ b (mod m) dan a ≡ b (mod n) dengan (m, n) = 1, buktikanlah bahwa  a ≡ b (mod mn)

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) → 𝑚 | (𝑎 − 𝑏)

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) → 𝑛 | (𝑎 − 𝑏)

(𝑚, 𝑛) = 1 → [𝑚, 𝑛] = (𝑚.𝑛)/(𝑚, 𝑛) = 𝑚𝑛/1 = 𝑚𝑛 

𝑚 | (𝑎 − 𝑏) dan 𝑛 | (𝑎 − 𝑏) → (𝑎 − 𝑏) ∈ 𝐾(𝑚, 𝑛)

Berdasarkan teorema KPK:

𝑐 ∈ 𝐾(𝑎, 𝑏) → [𝑎, 𝑏] | 𝑐

(𝑎 − 𝑏) ∈ 𝐾(𝑚, 𝑛) → [𝑚, 𝑛] | (𝑎 − 𝑏)

𝑚𝑛 | (𝑎 − 𝑏)

D.k.l 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚𝑛) ∎

4. Diberikan bilangan bulat positif c, buktikanlah bahwa:

a ≡ b (mod m) jika dan hanya jika ac ≡ bc (mod mc)

(i) 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) → 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚𝑐)

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) → 𝑎 − 𝑏 = 𝑘.𝑚, untuk suatu bilangan bulat k

(𝑎 − 𝑏).𝑐 = 𝑘.𝑚.𝑐

𝑎𝑐 − 𝑏𝑐 = 𝑘.(𝑚𝑐)

D.k.l 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚𝑐)

(ii) 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚𝑐) → 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚)

𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚𝑐) → 𝑎𝑐 − 𝑏𝑐 = 𝑘.(𝑚𝑐), untuk suatu bilangan bulat k

c(a − b) = c(km), bagi masing-masing ruas dengan c (hal ini boleh karena masing-masing ruas habis dibagi oleh c)

a − b = km

D.k.l 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) ∎

5. Buktikan bahwa: Jika a ≡ b (mod m), maka (a, m) = (b, m)

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) → a = b + km, untuk suatu bilangan bulat k

Berdasarkan teorema FPB:

(𝑏, 𝑚) = (𝑏 + 𝑚, 𝑚)

Untuk k positif:

(𝑏, 𝑚) = (𝑏 + 𝑚, 𝑚) = (𝑏 + 2𝑚, 𝑚) = … = (𝑏 + 𝑘𝑚, 𝑚)

Untuk k negatif:

(𝑏, 𝑚) = (𝑏 − 𝑚, 𝑚) = (𝑏 − 2𝑚, 𝑚) = … = (𝑏 + 𝑘𝑚, 𝑚)

Dimana a = b + km

D.k.l (a, m) = (b, m) ∎

6. Buktikan bahwa: Jika a ≡ b (mod m) dengan 0 ≤ |𝑏 − 𝑎| < 𝑚, maka a = b

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) → 𝑎 − 𝑏 = 𝑘.𝑚, untuk suatu bilangan bulat k

|𝑎 − 𝑏| = |𝑏 − 𝑎| = |𝑘.𝑚|

0 ≤ |𝑏 − 𝑎| < 𝑚 → 0 ≤ |𝑘𝑚| < 𝑚

Karena k bilangan bulat, maka pada interval 0 ≤ |𝑘𝑚| < 𝑚 nilai k yang memenuhi hanya k = 0

|𝑘𝑚| = |0| → |𝑏 − 𝑎| = |𝑎 − 𝑏| = 0 sehingga diperoleh:

a – b = 0

D.k.l a = b ∎

7. Buktikan bahwa jika a ≡  b (mod m), maka a ≡ b (mod 2m) atau  a ≡ b + m (mod 2m)

Diket a ≡ b (mod m), berarti a = b + m.k, atau a – b = m.k, dengan k bilangan bulat

Ada 2 kemungkinan untuk nilai k, yaitu bil ganjil atau bil genap

(i) Untuk k bil genap, misalkan k = 2t

𝑎 − 𝑏 = 𝑚𝑘 

𝑎 − 𝑏 = 𝑚(2𝑡) 

𝑎 − 𝑏 = 2(𝑚𝑡) 

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 2𝑚) 

(ii) Untuk k bil ganjil, misalkan k = 2t + 1

𝑎 − 𝑏 = 𝑚𝑘 

𝑎 − 𝑏 = 𝑚(2𝑡 + 1) 

𝑎 − 𝑏 = 2𝑚𝑡 + 𝑚 

𝑎 = 𝑏 + 𝑚 + 2(𝑚𝑡) 

𝑎 = 𝑏 + 𝑚 + 2𝑚.𝑡 

𝑎 ≡ 𝑏 + 𝑚 (𝑚𝑜𝑑 2𝑚) ∎