$a = -256$, $N = 123$ について、以下の2つの問題を解く。 (1) $a$ の $\bmod 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$ の $\bmod 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$ の $\bmod N$ での逆数 $x$ を求める。

まず、$a \pmod{N}$ を計算する。

$a = -256 \equiv -256 + 3 \cdot 123 \equiv -256 + 369 \equiv 113 \pmod{123}$

したがって、$a \equiv 113 \pmod{123}$

$ax \equiv 1 \pmod{123}$ を満たす $x$ を求める。

拡張ユークリッドの互除法を用いて $113x + 123y = 1$ を満たす整数 $x, y$ を求める。

\begin{align*}

123 &= 1 \cdot 113 + 10 \\

113 &= 11 \cdot 10 + 3 \\

10 &= 3 \cdot 3 + 1

\end{align*}

これより、

\begin{align*}

1 &= 10 - 3 \cdot 3 \\

&= 10 - 3 (113 - 11 \cdot 10) \\

&= 10 - 3 \cdot 113 + 33 \cdot 10 \\

&= 34 \cdot 10 - 3 \cdot 113 \\

&= 34 (123 - 1 \cdot 113) - 3 \cdot 113 \\

&= 34 \cdot 123 - 34 \cdot 113 - 3 \cdot 113 \\

&= 34 \cdot 123 - 37 \cdot 113

\end{align*}

したがって、$-37 \cdot 113 \equiv 1 \pmod{123}$

$x \equiv -37 \equiv -37 + 123 \equiv 86 \pmod{123}$

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

(2) $ay \equiv 100 \pmod{N}$ を満たす $y$ を求める。

$ay \equiv 100 \pmod{123}$ より、$113y \equiv 100 \pmod{123}$

(1) で $113^{-1} \equiv 86 \pmod{123}$ を求めたので、

$y \equiv 113^{-1} \cdot 100 \equiv 86 \cdot 100 \pmod{123}$

$86 \cdot 100 = 8600 \equiv 8600 \pmod{123}$

$8600 = 69 \cdot 123 + 113$

$8600 \equiv 113 \pmod{123}$

したがって、$y \equiv 113 \pmod{123}$

$0 \le y \le 122$ より、$y = 113$

3. 最終的な答え

(1) $x = 86$

(2) $y = 113$