Matematika Diskrit : Balikan Modulo (Modulo Invers)

📋 Daftar Isi

Modulo Invers

Di dalam aritmetika bilangan riil, balikan sebuah bilangan yang tidak-nol adalah bentuk pecahannya sedemikian sehingga hasil perkalian keduanya sama dengan 1.

Jika a adalah sebuah bilangan tidak-nol, maka balikannya adalah 1/a sedemikian sehingga a ×1/a = 1. Contoh: Balikan 4 adalah 1/4, sebab 4 × 1/4 = 1.

Balikan a dilambangkan dengan a^–1.

Di dalam aritmetika modulo, balikan modulo sebuah bilangan bulat lebih sukar dihitung.

Diberikan sebuah bilangan bulat a (mod m). Bagaimana menghitung balikan a (mod m)?

Syarat: Jika a dan m relatif prima dan m > 1, maka balikan (invers) dari a(mod m) ada.

Balikan dari a(mod m) adalah bilangan bulat x sedemikian sehingga:

xa ≡ 1 (mod m)

Dalam notasi lainnya, a^–1(mod m) = x

Bukti: a dan m relatif prima, jadi PBB(a, m) = 1, dan terdapat bilangan bulat x dan y sedemikian sehingga:

xa + ym = 1

yang mengimplikasikan bahwa xa + ym ≡ 1 (mod m)

Karena ym ≡ 0 (mod m), maka xa ≡ 1 (mod m)

Kekongruenan yang terakhir ini berarti bahwa x adalah balikan dari a (mod m).

Pembuktian di atas juga menceritakan bahwa untuk mencari balikan dari a (mod m), kita harus membuat kombinasi linier dari a dan m sama dengan 1.

Koefisien a dari kombinasi linier tersebut merupakan balikan dari a (mod m).

Contoh

Tentukan balikan dari 4 (mod 9), 17 (mod 7), dan 18 (mod 10).

Penyelesaian :

Balikan 4 (mod 9)

Karena PBB(4, 9) = 1, maka balikan dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa

9 = 2 · 4 + 1 (i)

4 = 4 · 1 + 0 (ii)

Susun persamaan (i) menjadi

–2 · 4 + 1 · 9 = 1 atau –2 · 4 + 1 · 9 ≡ 1 (mod 9)

Karena 1 · 9 ≡ 0 (mod 9), maka

–2 · 4 ≡ 1 (mod 9)

Dari kekongruenan terakhir ini kita peroleh –2 adalah balikan dari 4 (mod 9)

Atau dapat juga ditulis 4^–1(mod 9) = –2 (mod 9)

Catatan: setiap bilangan yang kongruen dengan –2 (mod 9) juga merupakan balikan dari 4 (mod 9), misalnya (…, –20, –11, 7, 16, …)

(…, –20, –11, –2, 7, 16, …) diperoleh dengan menambahkan 9 ke kiri atau ke kanan dari –2

–20 ≡ –2 (mod 9) karena 9 habis membagi –20 – (–2) = –18

–11 ≡ –2 (mod 9) karena 9 habis membagi –11 – (–2) = –9

7 ≡ –2 (mod 9) karena 9 habis membagi 7 – (–2) = 9

16 ≡ –2 (mod 9) karena 9 habis membagi 16 – (–2) = 18

Balikan 17 (mod 7)

Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada. Dari algoritma Euclidean diperoleh rangkaian pembagian berikut:

17 = 2 · 7 + 3 (i)

7 = 2 · 3 + 1 (ii)

3 = 3 · 1 + 0 (iii) (yang berarti: PBB(17, 7) = 1) )

Susun (ii) menjadi:

1 = 7 – 2 · 3 (iv)

Susun (i) menjadi

3 = 17 – 2 · 7 (v)

Sulihkan (v) ke dalam (iv):

1 = 7 – 2 · (17 – 2 · 7) = 1 · 7 – 2 · 17 + 4 · 7 = 5 · 7 – 2 · 17

atau

–2 · 17 + 5 · 7 = 1 ( 5 · 7 ≡ 0 (mod 7) )

–2 · 17 ≡ 1 (mod 7) (7 habis membagi –2 · 17 – 1 = –35)

Jadi, –2 adalah balikan dari 17 (mod 7) atau dapat ditulis 17^–1(mod 7) = –2 (mod 7).

Balikan 18 (mod 10)

Karena PBB(18, 10) = 2 ≠ 1, maka balikan dari 18 (mod 10) tidak ada.

Cara Lain Menghitung Balikan Modulo

Ditanya: balikan dari a (mod m)

Misalkan x adalah balikan dari a (mod m), maka

ax ≡ 1 (mod m) → definisi balikan modulo

atau dalam notasi ‘sama dengan’: ax = 1 + km

atau x = (1 + km)/a

Cobakan untuk k = 0, 1, 2, … dan k = -1, -2, …

Solusinya adalah semua bilangan bulat yang memenuhi.

Contoh

Balikan dari 4 (mod 9) adalah x sedemikian sehingga 4x ≡ 1 (mod 9)

4x ≡ 1 (mod 9) → 4x = 1 + 9k → x = (1 + 9k)/4

Untuk k = 0 → x = (1 + 9 · 0)/4 = 1/4 → tidak bulat

k = 1 → x = (1 + 9 · 1)/4 = 10/4 → tidak bulat

k = 2 → x = (1 + 9 · 2)/4 = 19/4 → tidak bulat

k = 3 → x = (1 + 9 · 3)/4 = 7

k = -1 → x = (1 + 9 · -1)/4 = -2

Balikan dari 4 (mod 9) adalah 7 (mod 9), -2 (mod 9), dst.

Catatan: cukup menemukan satu saja balikan dari 4 (mod 9), maka semua bilangan lainnya dapat dicari dengan menambahkan 9 pada bilangan tersebut. Pada contoh di atas, 7 adalah balikan 4 (mod 9), maka dengan menambahkan 9 ke kiri dan ke kanan diperoleh (…, -11, -2, 7, 16, …)