$a = 256$、$N = 123$ が与えられたとき、以下の2つの問題を解く。 (1) $a$ の $\mod N$ での逆数 $x \equiv a^{-1} \pmod{N}$ を求める。ただし、$0 \le x \le N-1$ とする。 (2) $ay \equiv 100 \pmod{N}$ となる $y$ を求める。ただし、$0 \le y \le N-1$ とする。

1. 問題の内容

$a = 256$、$N = 123$ が与えられたとき、以下の2つの問題を解く。

(1) $a$ の $\mod N$ での逆数 $x \equiv a^{-1} \pmod{N}$ を求める。ただし、$0 \le x \le N-1$ とする。

(2) $ay \equiv 100 \pmod{N}$ となる $y$ を求める。ただし、$0 \le y \le N-1$ とする。

2. 解き方の手順

(1) $a = 256$、$N = 123$ なので、$a \equiv 256 \pmod{123}$ を計算する。

$256 = 2 \times 123 + 10$ なので、$a \equiv 10 \pmod{123}$ である。

したがって、求める逆数は $10x \equiv 1 \pmod{123}$ を満たす $x$ である。

拡張ユークリッドの互除法を用いて、$10x + 123y = 1$ となる $x, y$ を求める。

$123 = 10 \times 12 + 3$

$10 = 3 \times 3 + 1$

$1 = 10 - 3 \times 3 = 10 - 3 \times (123 - 10 \times 12) = 10 - 3 \times 123 + 36 \times 10 = 37 \times 10 - 3 \times 123$

したがって、$37 \times 10 - 3 \times 123 = 1$ より、$37 \times 10 \equiv 1 \pmod{123}$ となるので、$x \equiv 37 \pmod{123}$ である。

(2) $ay \equiv 100 \pmod{N}$ は、$10y \equiv 100 \pmod{123}$ となる。

(1) より、$10^{-1} \equiv 37 \pmod{123}$ なので、両辺に 37 をかけると、

$37 \times 10y \equiv 37 \times 100 \pmod{123}$

$y \equiv 3700 \pmod{123}$

$3700 = 30 \times 123 + 10$

$y \equiv 10 \pmod{123}$

3. 最終的な答え

(1) $x = 37$

(2) $y = 10$