暗号理論の問題

方針　$23x+100y=1$ を満たす整数 $x,y$ を 1 組見つければ、両辺を法 $100$ で考えて $23x\equiv 1(\mathrm{mod}100)$ となる。この $x,y$ は、互除法を逆にたどって求める。

手順 1：互除法を行う
$$100=4\cdot 23+8$$
$$23=2\cdot 8+7$$
$$8=1\cdot 7+1$$
余りが $1$ になったので $\gcd (23,100)=1$ であり、逆元が存在することも確かめられる。

手順 2：余りを「割られる数 − 商 × 割る数」の形で書く
$$8=100-4\cdot 23(1)$$
$$7=23-2\cdot 8(2)$$
$$1=8-1\cdot 7(3)$$

手順 3：下から順に代入する
$(3)$ に $(2)$ を代入すると
$$1=8-(23-2\cdot 8)=3\cdot 8-23.$$
これに $(1)$ を代入すると
$$1=3(100-4\cdot 23)-23=3\cdot 100-13\cdot 23.$$
よって
$$23\cdot (-13)+100\cdot 3=1$$
であり、$x=-13,y=3$ が $23x+100y=1$ の解の 1 つである。

手順 4：法 $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 87\le 99$ を満たす。

検算　$23\times 87=2001=20\times 100+1$ より $23\cdot 87\equiv 1(\mathrm{mod}100)$。

したがって $x=87$ である。

拡張ユークリッドの互除法を用いる。
$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)$ なので $x=87$。

検算：$23\cdot 87=2001=20\cdot 100+1$ なので $23\cdot 87\equiv 1(\mathrm{mod}100)$。また、$0\le x\le 99$ の範囲では法 $100$ で解は一意である。