【徹底解説】中国剰余定理とは

本記事は数学の徹底解説シリーズに含まれます。

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

中国剰余定理

証明

$x_0$の存在

$n_1,\dots ,n_k$がどの二つも互いに素であること，および$N_i=N/n_i$であることから，互いに素な整数の積とそれらで割り切れる整数の関係より$gcd(N_i,n_i)=1$となります。すると，一次合同式の解の存在より式($\text{3}$)を満たす$u_i$はただ一つ存在します。このとき，$x_0$は$n_i$を法として

となります。したがって，式($\text{1}$)の解の一つとして$x_0$が得られました。

$x_0$の一意性

式($\text{1}$)の解として$x_1$を取ると，

となるため，

が得られます。これは$x_1-x_0$が$n_1,\dots ,n_k$のいずれでも割り切れることを意味しており，互いに素な整数の積とそれらで割り切れる整数の関係より$x_1-x_0$は$N=n_1\cdots n_k$で割り切れます。したがって，$x_0$と$x_1$は$N$を法として合同となるため，式($\text{1}$)の解は$N$を法としてただ一つであることが示されました。

参考文献

本稿の執筆にあたり参考にした文献は，以下でリストアップしております。