a. 222 (mod 131)
b. 721 (mod 135)
makasiii
Soal a
Invers modulo dari 222 (mod 131) adalah 36, atau dapat pula dinyatakan dengan:
[tex]\large\text{$\begin{aligned}{\bf36}\ \equiv\ 222^{-1}\ (\!\!\!\!\mod131)\end{aligned}$}[/tex]
______________________
Soal b
Invers modulo dari 721 (mod 135) adalah 91, atau dapat pula dinyatakan dengan:
[tex]\large\text{$\begin{aligned}{\bf91}\ \equiv\ 721^{-1}\ (\!\!\!\!\mod135)\end{aligned}$}[/tex]
______________________
Pembahasan
Invers Modulo
Untuk menentukan invers modulo, kita dapat menggunakan algoritma pembagian Euclidean, dan kemudian menentukan kombinasi linear dengan menelurusi arah sebaliknya dari algoritma tersebut.
Soal a: 222 (mod 131)
222 = 131×1 + 91
131 = 91×1 + 40
91 = 40×2 + 11
40 = 11×3 + 7
11 = 7×1 + 4
7 = 4×1 + 3
4 = 3×1 + 1
Lalu, kita telusuri arah sebaliknya.
1 = 4×1 – 3×1
1 = 4×1 – (7 – 4×1)
1 = 4×2 – 7×1
1 = (11 – 7×1)×2 – 7×1
1 = 11×2 – 7×3
1 = 11×2 – (40 – 11×3)×3
1 = 11×11 – 40×3
1 = (91 – 40×2)×11 – 40×3
1 = 91×11 – 40×25
1 = 91×11 – (131 – 91×1)×25
1 = 91×36 – 131×25
1 = (222 – 131×1)×36 – 131×25
1 = 222×36 + 131×(–61)
Kita telah mendapatkan kombinasi linear dalam bentuk 222x + 131y. Invers modulo dari 222 (mod 131) adalah x, atau bilangan pengali 222 pada kombinasi linear tersebut, yaitu 36.
KESIMPULAN
∴ Invers modulo dari 222 (mod 131) adalah 36, atau dapat pula dinyatakan dengan:
[tex]\large\text{$\begin{aligned}{\bf36}\ \equiv\ 222^{-1}\ (\!\!\!\!\mod131)\end{aligned}$}[/tex]
[tex]\blacksquare[/tex]
Soal b: 721 (mod 135)
721 = 135×5 + 46
135 = 46×2 + 43
46 = 43×1 + 3
43 = 3×14 + 1
Lalu, kita telusuri arah sebaliknya.
1 = 43×1 – 3×14
1 = (135 – 46×2)×1 – (46 – 43×1)×14
1 = 135 – 46×16 + 43×14
1 = 135 – 46×16 + (135 – 46×2)×14
1 = 135×15 – 46×44
1 = 135×15 – (721 – 135×5)×44
1 = 135×(15+220) – 721×44
1 = 135×235 – 721×44
1 = 721(–44) + 135×235
Kita telah mendapatkan kombinasi linear dalam bentuk 721x + 135y. Invers modulo dari 721 (mod 131) adalah x, atau bilangan pengali 721 pada kombinasi linear tersebut, yaitu –44. Karena kita memperoleh nilai negatif, kita cari bilangan positif yang kongruen.
–44 (mod 135) = (135 – 44) (mod 135) = 91 (mod 135)
KESIMPULAN
Invers modulo dari 721 (mod 135) adalah 91, atau dapat pula dinyatakan dengan:
[tex]\large\text{$\begin{aligned}{\bf91}\ \equiv\ 721^{-1}\ (\!\!\!\!\mod135)\end{aligned}$}[/tex]
[tex]\blacksquare[/tex]
