中国剰余定理と法が互いに素でない場合への拡張

中国剰余定理(一般の場合)

ni(i=1,,k)n_i\: (i=1,\cdots, k) たちがどの2つも互いに素なとき,kk 本の連立合同式 xai(modni)x\equiv a_i \pmod{n_i} を満たす xx0x<n1n2nk0\leqq x <n_1n_2\cdots n_k の範囲にただ1つ存在する。

中国剰余定理の基本は二元の場合で説明しました。→中国剰余定理の証明と例題(二元の場合)

この記事はその発展です。以下では,二元の場合の結果と考え方を用いるので先に二元の場合をしっかり理解しておいてください!

このページでは,

  • 合同式が3本以上ある場合
  • nin_i たちが互いに素でない場合

を考えます。

中国剰余定理(一般の場合)の証明

解の唯一性の証明は二元の場合と全く同じなので省略します。解の存在性は合同式の本数 kk に関する帰納法と二元の場合の結果から証明できます。

中国剰余定理の証明

k=1k=1 のときに成立するのは自明

k=tk=t のときに中国剰余定理が成立すると仮定すると,tt 本の合同式 xai(modni)(i=1,,t)x\equiv a_i \pmod{n_i}\:(i=1,\cdots, t) を満たす xx の集合は,(うまく x0x_0 が取ってこれて) 11 本の合同式 xx0(modn1n2nt)x\equiv x_0\pmod{n_1n_2\cdots n_t} を満たす xx の集合と同じ。

よって,今考えたい t+1t+1 本の連立合同式 xai(modni)(i=1,,t+1)x\equiv a_i \pmod{n_i}\:(i=1,\cdots, t+1)22 本の連立合同式 xx0(modn1n2nt)x\equiv x_0\pmod{n_1n_2\cdots n_t} xat+1(modnt+1)x\equiv a_{t+1}\pmod{n_{t+1}} と同値である。ここで,n1n2ntn_1n_2\cdots n_tnt+1n_{t+1} は互いに素なので二元の場合の結果より,この連立合同式には解 xx0x<n1n2ntnt+10\leqq x <n_1n_2\cdots n_t\cdot n_{t+1} の範囲に存在する。

よって k=t+1k=t+1 のときも中国剰余定理が成立するので,帰納法により証明完了。

互いに素でないときの連立合同式

次に,二元の場合においてn1n_1n2n_2 が互いに素でない場合に拡張します。

一般の二元合同式

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

を満たす xx0x<lcm(n1,n2)0\leqq x <\mathrm{lcm}(n_1,n_2) の範囲にただ1つ存在する。

a1a2(modgcd(n1,n2))a_1\equiv a_2\:\pmod{\mathrm{gcd}(n_1, n_2)}

  • lcm(n1,n2)\mathrm{lcm}(n_1, n_2)n1n_1n2n_2 の最小公倍数,gcd(n1,n2)\mathrm{gcd}(n_1, n_2)n1n_1n2n_2 の最大公約数を表します。
  • n1n_1n2n_2 が互いに素なときは,gcd(n1,n2)=1\mathrm{gcd}(n_1,n_2)=1 となり常に右側の条件が満たされるので二元の場合の中国剰余定理と一致します。
←の証明

解の唯一性は互いに素な場合と同様。以下,解の存在性を示す。右側の条件と一次不定方程式ax+by=cの整数解(ベズーの定理)より,

n1X+n2Y=a2a1n_1X+n_2Y=a_2-a_1 を満たす整数 X,YX, Y が存在する(注)。

よって,x=n1X+a1=a2n2Yx'=n_1X+a_1=a_2-n_2Y とおくと xx' は連立合同式を満たす。最後に xx'lcm(n1,n2)\mathrm{lcm}(n_1,n_2) で割った余りを xx とすれば左側の条件を満たす。

注:互いに素でない場合と同様,ユークリッドの互除法を用いて X,YX,Y を求めることができます。

→の証明

連立合同式に解 xx が存在するとき,

xa1(modn1)x\equiv a_1\pmod{n_1} であり,n1n_1gcd(n1,n2)\mathrm{gcd}(n_1,n_2) の倍数なので

xa1(modgcd(n1,n2))x\equiv a_1\pmod{\mathrm{gcd}(n_1,n_2)}

同様に xa2(modgcd(n1,n2))x\equiv a_2\pmod{\mathrm{gcd}(n_1,n_2)}

となり右側の条件が満たされる。

一般の連立合同式

最後に nin_i たちが互いに素とは限らない,かつ式の本数が kk の場合(上記2つの融合)の結果を述べておきます。

最も一般的な定理

kk 本の連立合同式

xai(modni)(i=1,2,,k)x\equiv a_i \pmod{n_i}\:(i=1,2,\cdots, k)

を満たす xx0x<lcm(n1,n2,,nk)0\leqq x <\mathrm{lcm}(n_1,n_2,\cdots, n_k) の範囲にただ1つ存在する。

⇔任意の iijj に対して aiaj(modgcd(ni,nj))a_i\equiv a_j\pmod{\mathrm{gcd}(n_i, n_j)}

証明は今までとほとんど同様です。

参考にしたサイト:Chinese Remainder Theorem(英語です)

数オリの問題への応用

1989年国際数学オリンピックドイツ大会第5問です。中国剰余定理を使えば一発です。

問題

任意の自然数 nn に対して,「いずれもが素数のべき乗の形でないような連続する nn 個の自然数」が存在することを証明せよ。

解答

2n2n 個の素数 p1,p2,,,p2np_1,\:p_2,\:,\cdots,\:p_{2n} を持ってくる。

中国剰余定理より,以下の nn 本の連立合同式を満たす xx が存在する。

x1(modp1p2)x\equiv -1\pmod{p_1p_2}

x2(modp3p4)x\equiv -2\pmod{p_3p_4}

\cdots

xn(modp2n1p2n)x\equiv -n\pmod{p_{2n-1}p_{2n}}

よって,x+1,x+2,,x+nx+1,\:x+2,\:\cdots,x+n はいずれも2つ以上の素因数を持つので目標の主張は示された。

かなり複雑になってしまいましたが,「xiaix_i\equiv a_i 型の連立合同式は(原理的には)ユークリッドの互除法を使って解が求まる」と覚えておくとよいでしょう。

Tag:国際数学オリンピックの過去問