BALIKAN MODULO (INVERS)

Balikan Modulo (Invers)
Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan
(invers) dari a modulo m. Balikan dari a modulo m adalah bilangan bulat a
sedemikian sehingga

Bukti:
Dari definisi relatif prima diketahui bahwa GCD (a,m) = 1, dan menurut
persamaan (2) terdapat bilangan bulat p dan q sedemikian sehingga
pa + qm = 1
yang mengimplikasikan bahwa
pa + qm = 1
Karena qm ≡ 0 (mod m) , maka
pa ≡ 1 (mod m)
Kekongruenan yang terakhir ini berarti bahwa p adalah balikan dari a modulo m.
Pembuktian di atas juga menceritakan bahwa untuk mencari balikan dari a
modulo m, kita harus membuat kombinasi lanjar dari a dan m sama dengan 1.
Koefisien a dari kombinasi lanjar tersebut merupakan balikan dari a modulo m.
Contoh :
Tentukan balikan modulo dari 4 (mod 9), dan 17 (mod 7)
1) 4 (mod 9)
o GCD (4, 9) => 9 = 1 . 4 + 5
4 = 1 . 4 + 1
4 = 4 . 1 + 0
GCD = 1
o p . 4 + q . 9 = 1
(-2) . 4 + 1 . 9 = 1
-2 . 4 ≡ 1 (mod 9)
-8 ≡ 1 (mod 9)
o -2 adalah balikan 4 modulo 9
2) 17 (mod 7)
o GCD (17, 7) => 17 = 2 . 7 + 3
7 = 2 . 3 + 1
3 = 3 . 1 + 0
GCD = 1
o p . 17 + q . 7 = 1
(-2) . 17 + 5 . 7 = 1
-2 . 7 1 (mod 7)
-14 1 (mod 7)
o -2 adalah balikan 17 modulo 7

SUMBER : BU WINDIA HADI 

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA 

MATAKULIAH : TEORI BILANGAN