KONGRUENSI

Kongruensi
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). Misalnya 38 mod 5 = 3 dan 13 mod 5 =
3, maka kita katakan 38 ≡ 13 (mod 5) (baca: 38 kongruen dengan 13 dalam
modulo 5). Contoh :
1) 17 ≡ 2 (mod 3) ( 3 habis membagi 17 – 2 = 15)
2) –7 ≡ 15 (mod 11) (11 habis membagi –7 – 15 = –22)
3) 12 2 (mod 7) (7 tidak habis membagi 12 – 2 = 10 )
4) –7 15 (mod 3) (3 tidak habis membagi –7 – 15 = –22)
 Teorema 4
Misalkan a, b, c, d, x dan y melambangkan bilangan bulat, maka
1) a ≡ b (mod m), b ≡ a (mod m), dan a-b ≡ 0 (mod m) adalah pernyataan
yang setara
2) Jika a ≡ b (mod m) dan b ≡ c (mod m) maka a ≡ c (mod m)
3) Jika a ≡ b (mod m) dan d membagi habis m maka a ≡ b (mod d)
4) Jika a ≡ b (mod m) dan c ≡ d (mod m) maka ax + cy = bx + dy (mod
m)
 Teorema 2
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) untuk suatu bilangan bulat tak negatif p.
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 :
1) 27 mod 3 = 3 . 9 + 0 = 0
2) 6 mod 8 = 8 . 0 + 6 = 6
3) 0 mod 12 = 12 .1 + 0 = 0
4) -41 mod 9 = 9 . (-5) + 4 = 4
5) 17 mod 3 = 3 . 5 + 2 = 2
6) 10 mod 3 = 3 . 3 + 1 = 1
7) 14 mod 6 = 6 . 2 + 2 = 2
8) 32 mod 3 = 3 . 10 + 3 = 3
17 mod 3 kongruensi dengan 14 mod 6 maka 17 ≡ 32 (mod 3). Misalkan c =
2, maka
i. (a + c) ≡ (b + c)
o 29 mod 3 = 3 . 9 + 2 = 2
o 2 mod 12 = 12 . 0 + 2 = 2
ii. a x c = b x c
o 27 . 2 mod 3 = 54 mod 3 = 3 . 18 + 0 = 0
o 0 . 2 mod 12 = 0 mod 12 = 12 . 1 + 0 = 0
iii. ac ≡ bc
o 27² mod 3 = 729 mod 3 = 3 . 243 + 0 = 0
o 0² mod 12 = 0 mod 12 = 12 . 1 + 0 = 0

*Aritmetika Modulo
Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m (dibaca “a modulo m”) memberikan sisa jika a dibagi dengan m.
Notasi: a mod m = r sedemikian sehingga.
a = mq + r dengan 0 < r < m.
Bilangan m disebut modulus atau modulo.
Proposisi 5.2 :
a ≡ b (mod m) jika dan hanya jika a = b + km untuk bilangan bulat k .
Bukti :
a ≡ b (mod m) jika hanya jika a -  b adalah kelipatan dari m. ini berarti a -  b = km untuk bilangan bulat k, atau setara dengan a = b + km.
Proposisi 5. 2
Jika a adalah bilangan bulat dan m adalah bilangan bulat positif. Ketika ada
bilangan bulat unik r dengan 0 < r < m - 1 maka jadi a ≡ r (mod m). Bilangan bulat ini disebut residu paling tidak negatif dari mod m.
Proposisi 5.4 :
Jika a, b, c dan m adalah bilangan bulat dengan m > 0 maka :
a. a ≡ a (mod m)
b. Jika a = b (mod m) maka b = a (mod m)
c. Jika a = b (mod m) dan b = c (mod m), maka a = c (mod m).
Bukti :
a. Karena a = a + 0 x m, proposisi 5.2 mengatakan bahwa a ≡ a (mod m)
b. Jika a ≡ b (mod m), maka a = b + km, untuk berapa k. Untuk itu b = a + (-k)m, jadi b ≡ a (mod m)

SUMBER : BU WINDIA HADI M. Pd

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA 

MATAKULIAH : TEORI BILANGAN