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 + k1m
c d (mod m) c = d + k2m
(a + c) = (b + d) + (k1 + k2)m
(a + c) = (b + d) + km dengan (k = k1 + k2)
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)
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)