Matematika Diskrit : Balikan Modulo (Modulo Invers)

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, โ€ฆ)


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Teori Bilangan, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up