暗号理論の問題

方針 拡張ユークリッドの互除法で $23x+100y=1$ を満たす整数 $x,y$ を 1 組求めます。すると $23x\equiv 1(\mathrm{mod}100)$ となるので、その $x$ を $0$ 以上 $99$ 以下に直せば答えです。

手順 1：互除法で $\gcd (23,100)$ を求める
$$100=4\cdot 23+8$$
$$23=2\cdot 8+7$$
$$8=1\cdot 7+1$$
最後の 0 でない余りが $1$ なので、$\gcd (23,100)=1$ です。したがって $23$ の法 $100$ での逆元は存在します。

手順 2：互除法を逆にたどる
各式を余りについて解くと
$$8=100-4\cdot 23,7=23-2\cdot 8,1=8-7$$
です。下の式から順に代入していきます。
$$1=8-7=8-(23-2\cdot 8)=3\cdot 8-23$$
$$=3\cdot (100-4\cdot 23)-23=3\cdot 100-13\cdot 23$$
よって
$$23\cdot (-13)+100\cdot 3=1$$
となり、$x=-13,y=3$ が 1 組の解です。

手順 3：法 $100$ で考える
この式を法 $100$ で見ると $100\cdot 3\equiv 0$ なので
$$23\cdot (-13)\equiv 1(\mathrm{mod}100)$$
です。$-13\equiv -13+100=87(\mathrm{mod}100)$ なので、$0\le x\le 99$ の範囲の解は $x=87$ です。

検算 $23\cdot 87=2001=20\cdot 100+1$ なので、確かに $23\cdot 87\equiv 1(\mathrm{mod}100)$ です。

したがって答えは $87$ です。

$23x\equiv 1(\mathrm{mod}100)$ を拡張ユークリッドの互除法で解く。
$100=4\cdot 23+8$、$23=2\cdot 8+7$、$8=1\cdot 7+1$ より、
$1=8-7=8-(23-2\cdot 8)=3\cdot 8-23=3(100-4\cdot 23)-23=3\cdot 100-13\cdot 23$。
よって $23\cdot (-13)\equiv 1(\mathrm{mod}100)$ で、$-13\equiv 87(\mathrm{mod}100)$。
検算: $23\cdot 87=2001=20\cdot 100+1$ なので $23\cdot 87\equiv 1(\mathrm{mod}100)$ が成り立つ。
$\gcd (23,100)=1$ なので解は法 100 で一意であり、$0\le x\le 99$ の範囲では $x=87$ のみ。