与えられた問題は以下の4つです。 (1) ユークリッドの互除法を用いて、$m = 663$ と $n = 2371$ の最大公約数 $\gcd(m, n)$ を求める。 (2) (1) で求めた $\gcd(m, n)$ に対して、$ms + nt = \gcd(m, n)$ を満たす整数 $s, t$ を求める。ただし、$m = 663$、$n = 2371$ とする。 (3) $\mathbb{Z}/n\mathbb{Z}$ において、$23 \div m$ の値を求める。ただし、$m = 663$、$n = 2371$ とする。 (4) 連立合同方程式 $\begin{cases} x \equiv 29 \pmod{m} \\ x \equiv 44 \pmod{n} \end{cases}$ を満たす整数 $x$ を求める。ただし、$m = 663$、$n = 2371$ とする。

1. 問題の内容

与えられた問題は以下の4つです。

(1) ユークリッドの互除法を用いて、$m = 663$ と $n = 2371$ の最大公約数 $\gcd(m, n)$ を求める。

(2) (1) で求めた $\gcd(m, n)$ に対して、$ms + nt = \gcd(m, n)$ を満たす整数 $s, t$ を求める。ただし、$m = 663$、$n = 2371$ とする。

(3) $\mathbb{Z}/n\mathbb{Z}$ において、$23 \div m$ の値を求める。ただし、$m = 663$、$n = 2371$ とする。

(4) 連立合同方程式

$\begin{cases}

x \equiv 29 \pmod{m} \\

x \equiv 44 \pmod{n}

\end{cases}$

を満たす整数 $x$ を求める。ただし、$m = 663$、$n = 2371$ とする。

2. 解き方の手順

(1) ユークリッドの互除法を用いて、$\gcd(663, 2371)$ を計算します。

$2371 = 663 \cdot 3 + 382$

$663 = 382 \cdot 1 + 281$

$382 = 281 \cdot 1 + 101$

$281 = 101 \cdot 2 + 79$

$101 = 79 \cdot 1 + 22$

$79 = 22 \cdot 3 + 13$

$22 = 13 \cdot 1 + 9$

$13 = 9 \cdot 1 + 4$

$9 = 4 \cdot 2 + 1$

$4 = 1 \cdot 4 + 0$

したがって、$\gcd(663, 2371) = 1$ です。

(2) 拡張ユークリッドの互除法を用いて、$663s + 2371t = 1$ を満たす整数 $s, t$ を求めます。

以下のように計算します。

$1 = 9 - 4 \cdot 2$

$1 = 9 - (13 - 9 \cdot 1) \cdot 2 = 9 \cdot 3 - 13 \cdot 2$

$1 = (22 - 13 \cdot 1) \cdot 3 - 13 \cdot 2 = 22 \cdot 3 - 13 \cdot 5$

$1 = 22 \cdot 3 - (79 - 22 \cdot 3) \cdot 5 = 22 \cdot 18 - 79 \cdot 5$

$1 = (101 - 79 \cdot 1) \cdot 18 - 79 \cdot 5 = 101 \cdot 18 - 79 \cdot 23$

$1 = 101 \cdot 18 - (281 - 101 \cdot 2) \cdot 23 = 101 \cdot 64 - 281 \cdot 23$

$1 = (382 - 281 \cdot 1) \cdot 64 - 281 \cdot 23 = 382 \cdot 64 - 281 \cdot 87$

$1 = 382 \cdot 64 - (663 - 382 \cdot 1) \cdot 87 = 382 \cdot 151 - 663 \cdot 87$

$1 = (2371 - 663 \cdot 3) \cdot 151 - 663 \cdot 87 = 2371 \cdot 151 - 663 \cdot 453 - 663 \cdot 87$

$1 = 2371 \cdot 151 - 663 \cdot 540$

したがって、$s = -540$、$t = 151$ が得られます。

(3) $\mathbb{Z}/2371\mathbb{Z}$ において、$23 \div 663$ の値を求める。これは、$23 \cdot 663^{-1} \pmod{2371}$ を求めることと同義です。

(2) より、$663 \cdot (-540) + 2371 \cdot 151 = 1$ なので、$663 \cdot (-540) \equiv 1 \pmod{2371}$。

したがって、$663^{-1} \equiv -540 \pmod{2371}$ です。 $-540 + 2371 = 1831$ なので、$663^{-1} \equiv 1831 \pmod{2371}$ です。

よって、$23 \div 663 \equiv 23 \cdot 1831 \pmod{2371}$。

$23 \cdot 1831 = 42113 = 2371 \cdot 17 + 1836$.

よって、$23 \div 663 \equiv 1836 \pmod{2371}$.

(4) 連立合同方程式を解きます。

$x \equiv 29 \pmod{663}$ より、$x = 663k + 29$ （$k$ は整数）。

これを $x \equiv 44 \pmod{2371}$ に代入すると、$663k + 29 \equiv 44 \pmod{2371}$。

$663k \equiv 15 \pmod{2371}$。

$663k \equiv 15 \pmod{2371}$ の両辺に $663^{-1} \equiv 1831 \pmod{2371}$ を掛けると、

$k \equiv 15 \cdot 1831 \pmod{2371}$。

$15 \cdot 1831 = 27465 = 2371 \cdot 11 + 1384$。

よって、$k \equiv 1384 \pmod{2371}$。

$k = 2371l + 1384$ ($l$ は整数) とおけるので、$x = 663(2371l + 1384) + 29 = 1577853l + 917712 + 29 = 1577853l + 917741$.

したがって、$x \equiv 917741 \pmod{1577853}$.

3. 最終的な答え

(1) $\gcd(663, 2371) = 1$

(2) $s = -540$, $t = 151$

(3) $23 \div 663 \equiv 1836 \pmod{2371}$

(4) $x \equiv 917741 \pmod{1577853}$