整数問題

連立合同式

次の連立合同式の解のうち、もっとも小さい正の整数\(x\)を求めよ。
\[\begin{align}
x &\equiv 3 \mbox{ (mod 4)} \\
x &\equiv 5 \mbox{ (mod 7)} \\
x &\equiv 7 \mbox{ (mod 11)}
\end{align}\]

\[
x \equiv 3 \mbox{ (mod 4)}
\]
より、\(n_1\)を整数として
\[
x = 4 n_1 + 3
\]
と書ける。これを第2式に代入して
\[\begin{align}
4 n_1 + 3 &\equiv 5 \mbox{ (mod 7)} \\
4 n_1 &\equiv 2 \mbox{ (mod 7)}
\end{align}\]
ここで、\(2 \times 4 = 8 \equiv 1 \mbox{ (mod 7)}\)に注意して、両辺に\(2\)をかけると
\[
n_1 \equiv 4 \mbox{ (mod 7)}
\]
が得られる。従って\(n_2\)を整数として
\[\begin{align}
n_1 &= 7 n_2 + 4 \\
x &= 4 n_1 + 3 \\
&= 4 (7 n_2 + 4) + 3 \\
&= 28 n_2 + 19
\end{align}\]
が得られる。これを第3式に代入して
\[\begin{align}
28 n_2 + 19 &\equiv 7 \mbox{ (mod 11)}\\
28 n_2 &\equiv -12 \equiv -1 \equiv 10 \mbox{ (mod 11)}
\end{align}\]
が得られる。\(2 \times 28 = 56 \equiv 1 \mbox{ (mod 11)}\)に注意して、両辺に\(2\)をかけると
\[
n_2 \equiv 20 \equiv 9 \mbox{ (mod 11)}
\]
が得られるので、\(n_3\)を整数として
\[
n_2 = 11 n_3 + 9
\]
と表すことが出来る。従って
\[\begin{align}
n_1 &= 7 n_2 + 4 \\
&= 7 (11 n_3 + 9) + 4 \\
&= 77 n_3 + 67 \\
x &= 4 n_1 + 3 \\
&= 4 (77 n_3 + 67) + 3 \\
&= 308 n_3 + 271
\end{align}\]
となり、\(x > 0\)で最小のものは
\[
x = 271
\]
と求まる。