法 $n=18$ のもとで、$a=5$ の逆元 $a^{-1}$ を求めよ。ただし、$0 < a^{-1} < 18$ の範囲で答える。

1. 問題の内容

法 $n=18$ のもとで、$a=5$ の逆元 $a^{-1}$ を求めよ。ただし、$0 < a^{-1} < 18$ の範囲で答える。

2. 解き方の手順

逆元 $a^{-1}$ は、$a \cdot a^{-1} \equiv 1 \pmod{n}$ を満たす数です。つまり、$5 \cdot a^{-1} \equiv 1 \pmod{18}$ を満たす $a^{-1}$ を求めます。

$5 \cdot a^{-1} = 1 + 18k$ となる整数 $k$ を探します。

$a^{-1} = \frac{1 + 18k}{5}$ が整数となるような $k$ を見つけます。

$k = 0$ のとき、$a^{-1} = \frac{1}{5}$

$k = 1$ のとき、$a^{-1} = \frac{19}{5}$

$k = 2$ のとき、$a^{-1} = \frac{37}{5}$

$k = 3$ のとき、$a^{-1} = \frac{55}{5} = 11$

$a^{-1} = 11$ は整数であり、$0 < 11 < 18$ を満たします。

確認のために、$5 \cdot 11 = 55 = 3 \cdot 18 + 1 \equiv 1 \pmod{18}$ です。

3. 最終的な答え

11