Di dalam aritmetika bilangan riil, invers dari perkalian adalah pembagian. Misalnya invers dari 4 adalah ¼, karena 4 x ¼ = 1. Di dalam aritmetika modulo, masalah menghitung invers modulo lebih rumit.
Jika a dan m relatif prima dan m > 1, maka dapat ditemukan invers dari a modulo m. Invers dari a modulo m adalah bilangan bulat a-1 sedemikian sehingga :
a . a-1 º 1 (mod m)
Pembuktian invers modulo ini sangat mudah, seperti terlihat pada penjabaran berikut ini :
GCD(a, m) = 1.
pa + qm = 1, yang mengimplikasikan bahwa pa + qm º 1 (mod m).
Karena qm º 1 (mod m), maka :
pa º 1 (mod m)
Kekongruenan ini berarti bahwa p adalah invers dari a modulo m. [MUN05]
Metode yang sering digunakan untuk mencari invers modulo adalah algoritma Euclidean yang diperluas (extended Euclidean algorithm). Langkah-langkah dari algoritma ini dalam mencari nilai x yang memenuhi persamaan a-1 ≡ x (mod n) adalah seperti berikut : [SCH96]
1. Bentuk Array A[3x2] dimana A[1,1] = n dan A[1,2] = a
2. Isikan A[2,1] .. A[3,2] dengan matriks Identitas.
3. Hitung bilangan bulat m dengan kondisi m * A[1,2] £ A[1,1]; usahakan m maksimum.
4. Hitung Xt = A[1,1] - m * A[1,2].
5. Ubah nilai A[1,1] = A[1,2] dan A[1,2] = Xt.
6. Lakukan langkah 4 dan 5 untuk baris kedua dan ketiga dari array A.
7. Ulang langkah 3 sampai 5 hingga elemen terakhir dari baris 1 = 0.
8. Jika A[3,1] ³ 0 maka x = A[3,1] sebaliknya x = A[3,1] + n.
0 Komentar