【数検1級対策】中国剰余の定理による連立一次合同式の解法

2024年7月27日

本記事では，数学検定1級で頻出のトピックについてまとめていきます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

中国剰余の定理による連立一次合同式の解法

次の連立一次方程式を解け。

$\begin{matrix} (1) & {\begin{cases} x \equiv 2 (\mod 3) \\ x \equiv 3 (\mod 5) \\ x \equiv 2 (\mod 7) \end{cases} \end{matrix}$

中国剰余定理に従って解きます。解は

\begin{aligned} (2) & x_{0} & = \sum_{i = 1}^{k} N_{i} u_{i} a_{i} \end{aligned}

で与えられるため， $i = 1, 2, 3$ に対して $N_{i}, u_{i}, a_{i}$ を求めればよいです。 $N_{i}$ については

\begin{array}{r} (3) & N_{1} = 5 \cdot 7 = 35, N_{2} = 3 \cdot 7 = 21, N_{3} = 3 \cdot 5 = 15 \end{array}

となり， $a_{i}$ については

\begin{array}{r} (4) & a_{1} = 2, a_{2} = 3, a_{3} = 2 \end{array}

となります。 $u_{1}$ については

\begin{array}{r} (5) & 35 u_{1} \equiv 1 (\mod 3) \end{array}

\begin{array}{r} (6) & 36 u_{1} \equiv 0 (\mod 3) \end{array}

に注目すると，式( $6$ )から式( $5$ )を引くことにより，

\begin{array}{r} (7) & u_{1} \equiv - 1 \equiv 2 (\mod 3) \end{array}

が得られます。同様に，

\begin{array}{r} (8) & u_{2} \equiv 1 (\mod 5) \\ (9) & u_{3} \equiv 1 (\mod 7) \end{array}

が得られるため，最も簡単な整数として

\begin{array}{r} (10) & u_{1} = 2, u_{2} = 1, u_{3} = 1 \end{array}

を選べばよいです。以上より，

\begin{aligned} (11) & x_{0} & = 35 \cdot 2 \cdot 2 + 21 \cdot 1 \cdot 3 + 15 \cdot 1 \cdot 2 = 233 \equiv 23 (\mod 105) \end{aligned}

が得られます。

シェアはこちらからお願いします！