Modulo dan Kongruensi

Modulo

Misalkan a adalah bilangan bulat dan m adalah bilangan bulat lebih besar nol. Operasi a mod m (dibaca a modulo m) memberikan sisa jika a dibagi dengan m. biasanya a mod m dengan m = 1 tidak ditulis. Artinya, mod 1 jarang dijumpai atau tak pernah dijumpai. Karena a mod 1 nilainya pasti sama dengan nol. Semua bilangan bulat pasti habis dibagi 1. Sehingga tidak ada gunanya mempertanyakan mod 1.

Notasi: a mod m = r sedemikian sehingga a = mq + r, dengan 0  r < m. Bilangan m disebut modulus atau modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}. Kenapa hanya sampai pada m – 1? Perhatikan syarat 0 ≤ r < m. karena semesta pembicaraan ada di bilangan bulat, maka himpunan hasil aritmetika modulo hanya akan sampai pada m – 1. Karena sama saja untuk m dengan nol.

Contoh : Beberapa hasil operasi dengan operator modulo:

1. 23 mod 5 = 3 sama halnya dengan (23 = 5  4 + 3)
2. 0 mod 17 = 0 sama halnya dengan (0 = 12  0 + 0)

Kongruen

Misalnya 28 mod 5 = 3 dan 18 mod 5 = 3, maka kita katakan 28  18 (mod 5) (baca: 28 kongruen dengan 18 dalam modulo 5). Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0, maka a  b (mod m) jika m habis membagi a – b. Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a ≢ b (mod m).

Definisi : ditentukan p, q, m adalah bilangan-bilangan bulat dan m ≠ 0. Pp disebut kongruen dengan q modulo m, ditulis p ≡ q (mod m), jika dan hanya jika m ∣ p – q

Contoh :

22  2 (mod 5) ( 5 habis membagi 22 – 2 = 20)

–6  14 (mod 10) (10 habis membagi –6 – 14 = –20)

Kekongruenan a  b (mod m) dapat pula dituliskan dalam hubungan a = b + km dengan k adalah bilangan bulat.

Contoh :

17  2 (mod 3) dapat ditulis sebagai 17 = 2 + 5  3

–7  15 (mod 11) dapat ditulis sebagai –7 = 15 + (–2)11

Berdasarkan definisi aritmetika modulo, kita dapat menuliskan a mod m = r sebagai a  r (mod m)

Contoh : Beberapa hasil operasi dengan operator modulo berikut:

1) 23 mod 5 = 3 dapat ditulis sebagai 23  3 (mod 5)

2) 27 mod 3 = 0 dapat ditulis sebagai 27  0 (mod 3)

Sifat-sifat pada kongruensi

m adalah bilangan bulat positif. Kongruensi modulo m memenuhi sifat-sifat berikut.

Sifat refleksif

Jika p adalah suatu bilangan bulat, maka p ≡ p (mod m)

Sifat simetris

Jika p dan q adalah bilangan-bilangan bulat sehingga p ≡ q (mod m), maka q ≡ p (mod m)

Sifat transitif

Jika p, q dan r adalah bilangan-bilangan bulat sehingga p ≡ q (mod m) dan q ≡ r (mod m) maka p ≡ r (mod m)

Teorema. Misalkan m adalah bilangan bulat positif.

1. Jika a  b (mod m) dan c adalah sembarang bilangan bulat maka

1) (a + c)  (b + c) (mod m)

2) ac  bc (mod m)

2. Jika a  b (mod m) dan c  d (mod m), maka

1) (a + c)  (b + d) (mod m)

2) ac  bd (mod m)

Bukti untuk 1.2 dan 2.1

a  b (mod m) berarti:

a = b + km

a – b = km

(a – b)c = ckm

ac = bc + Km

ac  bc (mod m) , terbukti.

Bukti selanjutnya :

a  b (mod m)  a = b + k₁m

c  d (mod m)  c = d + k₂m

(a + c) = (b + d) + (k₁ + k₂)m

(a + c) = (b + d) + km dengan (k = k₁ + k₂)

Jadi, (a + c) = (b + d) (mod m)

Contoh : Misalkan 17  2 (mod 3) dan 10  4 (mod 3), maka menurut Teorema 2,

17 + 5 = 2 + 5 (mod 3)  22 = 7 (mod 3)

17 . 5 = 2 . 5 (mod 3)  85 = 10 (mod 3)

Teorema.

1. p ≡ q (mod m), maka pr ≡ pr (mod mr)
2. p ≡ q (mod m) dan d ∣ m, maka p ≡ q (mod d)
3. ap ≡ aq (mod m), maka p ≡ q (mod m/(a, m))

Bukti untuk 1.1

p ≡ q (mod m), maka sesuai definisi m ∣ p – q. kemudian dapat ditentukan bahwa rm ∣ r(p – q) atau rm ∣ rp – rq. Maka berdasarkan definisi dapat ditentukan bahwa pr ≡ pr (mod mr)