与えられた連立合同式 $x \equiv 30 \pmod{113}$ $x \equiv 20 \pmod{41}$ を満たす整数 $x$ を求め、その解を $x = a + bn$ の形で表す問題です。ここで $n$ は整数であり、$a$ と $b$ を求める必要があります。

1. 問題の内容

与えられた連立合同式

$x \equiv 30 \pmod{113}$

$x \equiv 20 \pmod{41}$

を満たす整数 $x$ を求め、その解を $x = a + bn$ の形で表す問題です。ここで $n$ は整数であり、$a$ と $b$ を求める必要があります。

2. 解き方の手順

まず、拡張ユークリッドの互除法を用いて $113$ と $41$ の最大公約数を見つけ、さらに $113u + 41v = \gcd(113, 41)$ を満たす整数 $u$ と $v$ を求めます。

すると、$113$ と $41$ は互いに素なので、$\gcd(113, 41) = 1$ となり、$113u + 41v = 1$ を満たす整数 $u$ と $v$ が存在します。

拡張ユークリッド互除法を行うと、

$113 = 2 \cdot 41 + 31$

$41 = 1 \cdot 31 + 10$

$31 = 3 \cdot 10 + 1$

$1 = 31 - 3 \cdot 10 = 31 - 3 \cdot (41 - 31) = 4 \cdot 31 - 3 \cdot 41 = 4 \cdot (113 - 2 \cdot 41) - 3 \cdot 41 = 4 \cdot 113 - 8 \cdot 41 - 3 \cdot 41 = 4 \cdot 113 - 11 \cdot 41$

したがって、$113(4) + 41(-11) = 1$ となり、$u=4$、$v=-11$ です。

次に、$x \equiv 30 \pmod{113}$ と $x \equiv 20 \pmod{41}$ を満たす $x$ を求めます。

$x = 30 + 113k$ を満たす整数 $k$ が存在します。

この $x$ を $x \equiv 20 \pmod{41}$ に代入すると、

$30 + 113k \equiv 20 \pmod{41}$

$113k \equiv -10 \pmod{41}$

$(2 \cdot 41 + 31)k \equiv -10 \pmod{41}$

$31k \equiv -10 \pmod{41}$

$31k \equiv 31 \pmod{41}$

$31k \equiv 31 \pmod{41}$ であるから $k \equiv 1 \pmod{41}$

したがって $k = 1 + 41l$ （$l$ は整数）と表せます。

$x = 30 + 113(1 + 41l) = 30 + 113 + 113 \cdot 41l = 143 + 4633l$

よって、$x \equiv 143 \pmod{4633}$ となります。

したがって、 $x = 143 + 4633n$ と表せます。

3. 最終的な答え

143 + 4633n