暗号理論の問題

$23x\equiv 1(\mathrm{mod}100)$ を満たす $x$ を求めることは、不定方程式 $23x+100y=1$ の整数解 $(x,y)$ を 1 組見つけることと同じである。

手順 1：互除法を行う。 $100$ と $23$ に互除法を用いると
$$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$ であり、
$$23\cdot (-13)\equiv 1(\mathrm{mod}100)$$
が成り立つ。

手順 4：$0\le x\le 99$ の範囲に直す。 $-13\equiv -13+100=87(\mathrm{mod}100)$ なので $x=87$ である。

検算： $23\cdot 87=2001=20\cdot 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$ にも合う。