Kongruensi Modulo (1)


Dalam matematika, operasi modulus adalah sebuah operasi yang menghasilkan sisa pembagian dari suatu bilangan terhadap bilangan lainnya. Misalkan diberikan dua bilangan a dan b, a modulo b (disingkat a mod b) adalah bilangan bulat sisa dari hasil pemabgian a oleh b (a dibagi oleh b). Sebagai contoh, 1 mod 3 sama dengan 1, karena 1 dibagi 3 sama dengan 1. Selanjutnya 7 mod 3 memiliki hasil 1 karena 7 bagi 3 sama dengan 2 sisa 1. Kemudian 9 mod 3 sama dengan 0, karena 9 bagi 3 sama dengan 3 sisa 0.

Secara umum, ditulis mod atau modulo. Diberikan a,b dan n merupakan bilangan bulat dengan n \neq 0, a disebut kongruen dengan b (mod n), ditulis a \equiv b (mod n) jika dan hanya jika n | (a – b). Dengan kata lain, n habis membagi (a – b) atau terdapat suatu bilangan bulat k sedemikian hingga a – b = kc atau a = kc + b.

Contoh :

1. 37 \equiv 2 (mod 5) [5 habis membagi (37 – 2)]

2. 53 \equiv 5 (mod 6) [6 habis membagi (53 – 5)]

3. 76 \equiv 4 (mod 9) [9 habis membagi (76 – 4)]

Operasi pada Kongruensi Modulo

Terdapat beberapa operasi pada kongruensi modulo, yaitu sebagai berikut.

1.  Penjumlahan

Jika a \equiv b (mod n) maka (a + c) \equiv (b + c) (mod n) untuk sebarang bilangan bulat c.

Bukti.

Ambil sebarang bilangan bulat c. Perhatikan

a \equiv b (mod n), artinya terdapat suatu bilangan bulat m sedemikian hingga (a – b) = mn. Selanjutnya tambahkan ruas kiri dengan bilangan bulat 0, diperoleh

(a – b) + 0 = mn

(a – b) + (c – c) = mn

(a + c) – (b + c) = mn

Dengan kata lain, (a + c) \equiv (b + c) (mod n).

Contoh :

Diberikan 13 \equiv 1 (mod 3), selanjutnya kedua ruas ditambah 3, berakibat 16 \equiv 4 (mod 3), artinya 16 = 3 \cdot 4 + 4. Karena ‘sisa’ lebih besar dari ‘pembagi’, maka dapat disederhakan 16 \equiv 1 (mod 3).

2.  Pengurangan

Jika a \equiv b (mod n) maka (a – c) \equiv (b – c) (mod n) untuk sebarang bilangan bulat c.

Bukti.

Ambil sebarang bilangan bulat c. Perhatikan

a \equiv b (mod n), artinya terdapat suatu bilangan bulat m sedemikian hingga (a – b) = mn. Selanjutnya tambahkan ruas kiri dengan bilangan bulat 0, diperoleh

(a – b) + 0 = mn

(a – b) + (c – c) = mn

(a – c) – (b – c) = mn

Dengan kata lain, (a – c) \equiv (b – c) (mod n).

Contoh :

16 \equiv 1 (mod 3), kedua ruas dikurangi 3, hasilnya 13 \equiv –2 (mod 3), artinya 12 = 3 \cdot 5 + (-2)4. Karena ‘pembagi’-nya negatif, dapat diubah menjadi 12 \equiv 1 (mod 3).

3.  Perkalian

Jika a \equiv b (mod n) maka ac \equiv bc (mod n) untuk sebarang bilangan bulat c.

Bukti.

Ambil sebarang bilangan bulat c. Perhatikan

a \equiv b (mod n), artinya terdapat suatu bilangan bulat m sedemikian hingga (a – b) = mn. Selanjutnya kalikan kedua ruas dengan bilangan bulat c, diperoleh

(a – b)c = mnc

ac – bc = mnc

ac – bc = (mc)n

Dengan kata lain, ac \equiv bc (mod n).

Contoh :

7 \equiv 4 (mod 3), kedua ruas dikali 2, diperoleh 14 \equiv 8 (mod 3) atau 14 \equiv 2 (mod 3).

4.  Pembagian

Jika ac \equiv bc (mod n) maka a \equiv b (mod n) untuk sebarang bilangan bulat c.

Bukti.

Ambil sebarang bilangan bulat c. Perhatikan

ac \equiv bc (mod n)

(ac – bc)  \equiv (bc – bc) (mod n)

(a – b)c  \equiv 0 (mod n)

Ekuivalen dengan mengatakan terdapat bilangan bulat k sedemikian hingga  (a – b)c = k \cdot n

Kedua ruas dibagi oleh gcd(c,n), diperoleh

\dfrac{c}{gcd(c,n)}(a – b) = k \dfrac{n}{gcd(c,n)}

Berakibat \dfrac{n}{gcd (c,n)} habis membagi \dfrac{c}{gcd(c,n)}(a-b). Karena \dfrac{n}{gcd (c,n)} dan \dfrac{c}{gcd (c,n)} saling prima, maka \dfrac{n}{gcd (c,n)} tidak membagi \dfrac{c}{gcd (c,n)}. Jadi, haruslah \dfrac{c}{gcd (c,n)} | (a-b). Dengan kata lain, (a – b) \equiv 0 (mod \dfrac{c}{gcd  (c,n)}). Jadi, a \equiv b (mod \dfrac{c}{gcd (c,n)}).

Contoh :

35 \equiv 5 (mod 30) (bagi kedua ruas dengan 5)

7 \equiv 1 (mod \dfrac{30}{gcd(30,5)})

7 \equiv 1 (mod 30/5)

7 \equiv 1 (mod 6)

 

 

 

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s