本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
中国剰余定理
自然数$n_{1},\ldots,n_{k}$がどの二つも互いに素であるとする。任意の整数$a_{1},\ldots,a_{k}$に対して，連立一次合同式
\begin{cases}
x \equiv a_{1}\pmod{n_{1}}\\[0.7em]
x \equiv a_{2}\pmod{n_{2}}\\[0.7em]
\quad\vdots\\[0.7em]
x \equiv a_{k}\pmod{n_{k}}\label{連立方程式}
\end{cases}
を満たす解$x_{0}$は，$N{=}n_{1}\cdots n_{k}$を法としてただ一つ存在し，
x_{0} &= \sum_{i=1}^{k}N_{i}u_{i}a_{i}\label{x_0の定義}
\end{align}
と表される。ただし，各$i$について$N_{i}{=}N/n_{i}$および
N_{i}u_{i}\equiv 1\pmod{n_{i}}\label{uの定義}
\end{align}
である。
証明
$x_{0}$の存在
$n_{1},\ldots,n_{k}$がどの二つも互いに素であること，および$N_{i}{=}N/n_{i}$であることから，互いに素な整数の積とそれらで割り切れる整数の関係より$\gcd(N_{i},n_{i}){=}1$となります。すると，一次合同式の解の存在より式($\ref{uの定義}$)を満たす$u_{i}$はただ一つ存在します。このとき，$x_{0}$は$n_{i}$を法として
x_{0}
&= (N_{1}u_{1})\cdot a_{1} + \cdot + (N_{i}u_{i})\cdot a_{i} + \cdots + (N_{k}u_{k})\cdot a_{k}\\[0.7em]
&\equiv 0\cdot a_{1} + \cdots + 1\cdot a_{i} + \cdots + 0\cdot a_{k} \equiv a_{i}\pmod{n_{i}}
\end{align}
となります。したがって，式($\ref{連立方程式}$)の解の一つとして$x_{0}$が得られました。
$x_{0}$の一意性
式($\ref{連立方程式}$)の解として$x_{1}$を取ると，
x_{1} \equiv a_{i} \equiv x_{0}\pmod{n_{i}}
\end{align}
となるため，
x_{1}-x_{0} &\equiv 0\pmod{n_{i}}
\end{align}
が得られます。これは$x_{1}-x_{0}$が$n_{1},\ldots,n_{k}$のいずれでも割り切れることを意味しており，互いに素な整数の積とそれらで割り切れる整数の関係より$x_{1}-x_{0}$は$N{=}n_{1}\cdots n_{k}$で割り切れます。したがって，$x_{0}$と$x_{1}$は$N$を法として合同となるため，式($\ref{連立方程式}$)の解は$N$を法としてただ一つであることが示されました。
参考文献
本稿の執筆にあたり参考にした文献は，以下でリストアップしております。
コメント