中国剰余定理の証明と例題(二元の場合)

更新日時 2021/03/07
中国剰余定理(二元の場合)

n1n_1n2n_2 が互いに素なとき,

xa1(modn1),x\equiv a_1 \pmod{n_1},

xa2(modn2)x\equiv a_2 \pmod{n_2}

を満たす xx00 以上 n1n2n_1n_2 未満の範囲にただ1つ存在する。

連立合同式・中国剰余定理の本質的な部分を理解するために,このページでは二元の場合で n1,n2n_1, n_2 が互いに素な場合のみを考えます。より一般の場合は→中国剰余定理と法が互いに素でない場合への拡張

目次
  • 連立合同式の簡単な例題

  • 中国剰余定理の証明(解の唯一性)

  • 中国剰余定理の証明(解の存在性)

  • さっきの例題を実際に解いてみる

連立合同式の簡単な例題

合同式の形で書くと一見いかめしいですが,ここで考えるのは以下のような単純な問題です:

例題

33 で割って 22 余り,55 で割って 44 余る 15(=3×5)15(=3\times 5) 未満の非負整数 nn を求めよ。

これくらいの大きさなら全部調べられます,解は n=14n=14 のみです。解が存在して,しかもただ1つです。

上記の例題と解答を一般化したのが中国剰余定理(Chinese Remainder Theorem)です。以下では,二元の場合の中国剰余定理を証明するとともに実際に連立合同式の解の求め方を解説します。

中国剰余定理の証明(解の唯一性)

まずは簡単な「唯一性」つまり「解が 22 つ以上存在することはない」ことを背理法で証明します。

中国剰余定理の証明:前半

与えられた連立合同式の解が2つ以上あると仮定する。そのうちの2つを x,yx,y とおくと,

xa1y(modn1)xa2y(modn2)x\equiv a_1\equiv y \pmod{n_1}\\ x\equiv a_2\equiv y\pmod{n_2}

より xyx-yn1n_1 の倍数であり n2n_2 の倍数でもある。n1n_1n2n_2 が互いに素なので xyx-yn1n2n_1n_2 の倍数。

ところが x,yx,y はともに n1n2n_1n_2 未満の非負整数なので x=yx=y となり矛盾。よって解が存在するとしたら 11 つ。

中国剰余定理の証明(解の存在性)

次に連立合同式に解が存在することを証明します。

中国剰余定理の証明:後半

n1,n2n_1, n_2 は互いに素なので,

n1X+n2Y=1n_1X+n_2Y=1 を満たす整数 X,YX,Y が存在する(→注)。

よって,

n2Y1(modn1)n1X1(modn2)n_2Y\equiv 1\pmod{n_1}\\n_1X\equiv 1\pmod{n_2}

よって,x=a1n2Y+a2n1Xx'=a_1n_2Y+a_2n_1X とおくと

xa1(modn1)xa2(modn2)x'\equiv a_1\pmod{n_1}\\ x'\equiv a_2\pmod{n_2}

となり xx' は与えられた連立合同式を満たす。

n1n2n_1n_2 未満の非負整数の解 xx を得るためには xx を「 xx'n1n2n_1n_2 で割った余り」とすればよい。

注:有名な定理(ベズーの定理)です。一次不定方程式ax+by=cの整数解で詳しく説明しています。ユークリッドの互除法を用いることで X,YX, Y を求めることができるので,解 xx を実際に計算できます!

さっきの例題を実際に解いてみる

例題(再掲)

以下の連立合同式を解け。

x2(mod3),x4(mod5)x\equiv 2\pmod{3},\\x\equiv 4\pmod{5}

3X+5Y=13X+5Y=1 を満たす X,YX, Y を直感またはユークリッドの互除法で求めると,例えば X=2,Y=1X=2, Y=-1

よって x=25(1)+432=14x'=2\cdot 5\cdot (-1)+4\cdot 3\cdot 2=14

となり解が得られます!

「中国剰余定理」という名前がかっこいいですね。