本記事では，数学検定1級で頻出のトピックについてまとめていきます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
中国剰余の定理による連立一次合同式の解法
次の連立一次方程式を解け。
\begin{cases}
x\equiv 2\pmod{3}\\[0.7em]
x\equiv 3\pmod{5}\\[0.7em]
x\equiv 2\pmod{7}
\end{cases}
解説
中国剰余定理に従って解きます。解は
\begin{align}
x_{0} &= \sum_{i=1}^{k}N_{i}u_{i}a_{i}
\end{align}
x_{0} &= \sum_{i=1}^{k}N_{i}u_{i}a_{i}
\end{align}
で与えられるため，$i{=}1,2,3$に対して$N_{i},u_{i},a_{i}$を求めればよいです。$N_{i}$については
\begin{align}
N_{1} = 5\cdot 7 = 35,\quad
N_{2} = 3\cdot 7 = 21,\quad
N_{3} = 3\cdot 5 = 15
\end{align}
N_{1} = 5\cdot 7 = 35,\quad
N_{2} = 3\cdot 7 = 21,\quad
N_{3} = 3\cdot 5 = 15
\end{align}
となり，$a_{i}$については
\begin{align}
a_{1} = 2,\quad
a_{2} = 3,\quad
a_{3} = 2
\end{align}
a_{1} = 2,\quad
a_{2} = 3,\quad
a_{3} = 2
\end{align}
となります。$u_{1}$については
\begin{align}
35u_{1} \equiv 1\pmod{3}\label{引き算1}
\end{align}
35u_{1} \equiv 1\pmod{3}\label{引き算1}
\end{align}
を解けばよいです。ユークリッドの互助法を用いてもよいですが，
\begin{align}
36u_{1} \equiv 0\pmod{3}\label{引き算2}
\end{align}
36u_{1} \equiv 0\pmod{3}\label{引き算2}
\end{align}
に注目すると，式($\ref{引き算2}$)から式($\ref{引き算1}$)を引くことにより，
\begin{align}
u_{1} \equiv -1 \equiv 2\pmod{3}
\end{align}
u_{1} \equiv -1 \equiv 2\pmod{3}
\end{align}
が得られます。同様に，
\begin{align}
u_{2} \equiv 1 \pmod{5}\\[0.7em]
u_{3} \equiv 1 \pmod{7}
\end{align}
u_{2} \equiv 1 \pmod{5}\\[0.7em]
u_{3} \equiv 1 \pmod{7}
\end{align}
が得られるため，最も簡単な整数として
\begin{align}
u_{1} = 2,\quad
u_{2} = 1,\quad
u_{3} = 1
\end{align}
u_{1} = 2,\quad
u_{2} = 1,\quad
u_{3} = 1
\end{align}
を選べばよいです。以上より，
\begin{align}
x_{0} &= 35\cdot 2\cdot 2 + 21\cdot 1\cdot 3 + 15\cdot 1\cdot 2 = 233 \equiv 23\pmod{105}
\end{align}
x_{0} &= 35\cdot 2\cdot 2 + 21\cdot 1\cdot 3 + 15\cdot 1\cdot 2 = 233 \equiv 23\pmod{105}
\end{align}
が得られます。
コメント