OMC対策（N分野：連立合同式・中国剰余定理）
本記事の前提知識
基本的な合同式が使えたら十分である．より具体的には， この記事 の問題1,2がある程度解ければ十分である．
連立合同式を解く
簡単な問題から始めよう．
$7$で割ると$3$余り，$5$で割ると$2$余る，$35$以下の正整数を答えよ．
この程度の問題であれば，小学$3$年生のレベルかもしれない．$7$で割ると$3$余る数を書きだしていけば$3,10,17,24,31$であり，このうち$5$で割ると$2$余る数は$17$のみである．よって答えは$17$だ．
しかし，これが解けたからといって，次の問題が解けるとは限らない．
$73$で割ると$3$余り，$53$で割ると$2$余る，$73×53$以下の正整数を答えよ．
このように，数値がある程度大きくなっても解けるだろうか．当然だが，問題1のように$73$で割って$3$余る数を$3,76,149,\cdots$と書きだすような方法は論外である．
この問題を解く方法はいくつかある．例えばEuclidの互除法を用いる方法や，百五減算のような方法がよく知られているが，ここでは合同式を使う方法を紹介したい．少しコツはいるが，慣れてしまえば一番早い方法だろう．
$N=73x+3=53y+2$とおける．ここで$53$を法とする合同式を考えよう．
まず与式は次のように書かれる．
$73x+3 \equiv 53y+2 \mod 53$
この式は$20x \equiv -1$と変形される．
ここから最終的には$x \equiv * \mod 53$という式を得たい．そこで，左辺の$20x$の係数を割れるように，右辺に$53$の倍数を足したり引いたりする．
ここからの途中計算は人によって変わるだろう．単純な例として$20x \equiv -1+53$とすれば両辺を$4$で割ることができて，$5x \equiv 13 $という式を得る．あるいは$20x \equiv -1-159$だと気づけば，一気に$20$で割ることもできる．
いきなり答えが出ては解説としてはつまらないので$5x \equiv 13$から続けよう．次は右辺を$5$で割り切れる数にしたいので$5x \equiv 13-53$とするのがよいだろう．こうすれば$x \equiv -8 \equiv 45$を得るので，$N=73×45+3=3288$だとわかる．
（確認問題）最初に$\mathrm{mod}\ 73$を取った場合，同じ結論になることを確かめよ．
確認問題の答え
最初の式は$53y \equiv 1 \mod 73$である．$y$の係数（の絶対値）は小さいほどよいので$-20y \equiv 1$とするのが良いだろう．
このあとは$-20y \equiv -72$→$5y \equiv 18 \equiv -55$→$y \equiv -11 \equiv 62$とするのが自然だろう．
あるいは最初から$-20y \equiv 220$→$y \equiv -11 \equiv 62$とすればもっと早い．
なお係数$20$は大きな素因数を持たないので非常に扱いやすいが，この値があまりよくない場合には$126y \equiv 1$から始める方がよい場合もある．これから始めると，例えば次のような変形が考え得る．
$126y \equiv -72$→$7y \equiv -4$→$7y \equiv -77$→$y \equiv -11 \equiv 62$
次の条件を満たす最小の正整数を答えよ．
(1) $29$で割ると$4$余り，$41$で割ると$11$余る
(2) $47$で割ると$22$余り，$73$で割ると$40$余る
(3) $30$で割ると$1$余り，$37$で割ると$7$余る
(4) $60$で割ると$12$余り，$63$で割ると$36$余る
(1)の答え
$29x+4=41y+11$に対して，$\mathrm{mod}\ 29$で合同式を考える．
$\begin{aligned} 12y &\equiv -7\\ 12y &\equiv -36\\ y &\equiv -3 \equiv 26 \end{aligned}$
よって$41×26+11=1077$．
(2)の答え
$\mathrm{mod}\ 47$で合同式を考える．
$\begin{aligned} -21y &\equiv -18\\ 7y &\equiv 6 \equiv 147\\ y &\equiv 21 \end{aligned}$
よって$73×21+40=1573$．
(3)の答え
$\mathrm{mod}\ 37$で合同式を考える．（注：$\mathrm{mod}\ 30$を取ると，両辺を$2,3,5$で割ることができない．なるべく約数の少ないものを法とする方が無難である．）
$\begin{aligned} -7x &\equiv 6 \equiv -105\\ x &\equiv 15 \end{aligned}$
（もちろん$30x \equiv 6$からスタートしてもよい．すぐに$5x \equiv 1$となるので，これでも簡単である．）
よって$30×15+1=451$．
(4)の答え
最初の式は$60x+12=63y+36$である．両辺を$3$で割って$20x=21y+8$としよう．
$\mathrm{mod}\ 20$で合同式を考えると，すぐに$y \equiv -8 \equiv 12$を得る．
よって$63×12+36=792$．
次は，もう少し難しい（というか面倒な）連立合同式である．
次の条件を満たす最小の正整数を答えよ．
(1) $10$で割ると$3$余り，$11$で割ると$5$余り，$12$で割ると$9$余る
(2) $5$で割ると$3$余り，$7$で割ると$5$余り，$11$で割ると$7$余り，$13$で割ると$11$余る．
(2)は工夫するとそこまで面倒ではないので，考えてみてほしい．
(1)の答え
まずは$10x+3=12z+9$を使おう．（$10,12$が共通の約数$2$を持つので，先にこちらの条件を使ったほうが数が小さくなる．）
$\mathrm{mod}\ 10$で考えて$z \equiv -3$を得るので$10x+3=12z+7=60t-27$となる整数$t$が存在する．
次に$60t-27=11y+5$を解いていけばよい．$\mathrm{mod}\ 11$で考えて$t \equiv 2$を得る．
$60×2-27=93$
(2)の答え
$5x+3=7y+5=13w+11$を変形して$5x'-2=7y'-2=13w'-2$である．つまり$5×7×13t-2$と置くことで，$3$つの条件を使い切ったことになる．
あとは，$455t-2=11z+7$を解けばよい．$\mathrm{mod}\ 11$で考えて$t \equiv 5$を得る．
$455×5-2=2273$
中国剰余定理
$k$個の整数$m_1, \cdots, m_k$が，どの$2$つも互いに素であるとき，連立合同式
$\begin{cases}
x &\equiv a_1 \mod m_1 \\
x &\equiv a_2 \mod m_2 \\
&\vdots \\
x &\equiv a_k \mod m_k
\end{cases}$
を満たす整数$x$が，$m_1m_2\cdots m_k$を法として一意に存在する．
証明は省略する．
この定理は，要するに$2$つのことを言っている．第一に$\mathrm{mod}\ m_i$の部分が全て互いに素なら必ず解を持つこと．第二に，そのような解は$\mathrm{mod}\ \prod m_i$を法として唯一であること（もう少しわかりやすい表現にすれば，$\prod m_i$ 以下の正整数の中でただ一つである）．
$\mathrm{mod}\ m_i$の部分が全て互いに素でない場合はどうなるのか？を疑問に持った方は，
高校数学の美しい物語
を参照してほしい．
次に，この定理に関する注意点を書いておく．
中国剰余定理は，解の「存在」を保証してくれるものである．その値を「求める」ことについては，何も言及していない．連立合同式を解いて「中国剰余定理より$x \equiv *$が解である」などと書いている答案などをたまに見るが，これは正確ではない．
また，面倒なことを書くが，インターネット上のいくつかのホームページを見ても，あるいは数学の参考書等を見ても，中国剰余定理の練習問題として連立合同式を挙げていることがあるが，これも（厳密には）正確ではない．もちろんそれらの筆者が混同しているわけではなく，中国剰余定理の具体例を練習問題という名称で出題しているに過ぎないのだろう．しかしそれらの読者の中には，それが中国剰余定理を「用いた」例題であると誤解して，先に挙げたような答案を書くのだと思われる．
さらに混乱させかねないことを書くが，「中国剰余定理より$x \equiv *$が解である」という表現は必ず誤りかと言うと，そういうわけでもない．例えば次の答案を見よ．
問：$2$で割ると$1$余り，$3$で割ると$1$余り，$5$で割ると$1$余り，$7$で割ると$1$余る，$500$以下の正整数を全て答えよ．
答：$1$は明らかに条件を満たす．中国剰余定理より$x \equiv 1 \mod 210$のみが解である．すなわち，条件を満たす数は$210n+1$の形で表され，答えは$1,211,421$．
この例のように，解の唯一性を保証する意味で「中国剰余定理」を使うのは正しい表記である．なお，この例で「のみ」の部分を省略しても解答として悪くはない．つまり，「中国剰余定理より$x \equiv *$が解である」という表現が直ちに誤りであるというわけでもない．
以上，面倒な注であるとは思うが，中国剰余定理の意味を正確に覚えておいてほしいと思う．
もう一つ，この定理に関する注意点である．中国剰余定理は，英語で Chinese remainder theorem と書かれるため，CRT と省略されることがしばしばある（日本語の文献でもしばしばこのように省略される）．この表記を自分で使える必要はないが，整数論の分野でCRTと見かけたら Chinese ナントカ theorem だったな→中国剰余定理だな，と思い出せるようにしておこう．
最後に，中国剰余定理を用いる例題である．
整数$n$を正整数$k$で割った余りを$n\%k$で表す．例えば$10\%3=1, 35\%5=0$である．このとき，次の値を求めよ．
$\sum\limits_{n=1}^{1000} (n\%7)×(n\%11)×(n\%13)$
解答
$7×11×13=1001$であり，$\sum\limits_{n=1}^{1000} (n\%7)(n\%11)(n\%13)=\sum\limits_{n=1}^{1001} (n\%7)(n\%11)(n\%13)$である．
中国剰余定理より，$0≦a≦6, 0≦b≦10, 0≦c≦12$を満たす任意の$(a,b,c)$に対して，$(n\%7, n\%11, n\%13)=(a,b,c)$の解が$1≦n≦1001$の中にただ一つ存在する．よって，
$\sum\limits_{n=1}^{1001} (n\%7)(n\%11)(n\%13)=(0+1+2+\cdots+6)(0+1+\cdots+10)(0+\cdots+12)=21×55×78=90090$
（やや難）
$n$以下で$n$と互いに素な正整数の個数を$\phi(n)$で表す（これは一般的な記法である）．
$n$を素因数分解すると$n=p_1^{e_1} \cdots p_k^{e_k}$と表されるとき（ただし$e_k \neq 0$），
$\phi(n)=n\left( 1-\dfrac{1}{p_1} \right)\cdots \left( 1-\dfrac{1}{p_k} \right)$
解答
次の連立合同式の解が$n$を法としていくつあるかという問いである．
$\begin{cases} x &\not\equiv 0 \mod p_1 \\ &\vdots \\ x &\not\equiv 0 \mod p_k \end{cases}$
中国剰余定理から，この連立合同式の解は$p_1p_2 \cdots p_k$を法として$(p_1-1)(p_2-1)\cdots(p_k-1)$個存在する．よって$n=p_1 \cdots p_k×p_1^{e_1-1}\cdots p_k^{e_k-1}$を法とすると
$(p_1-1)(p_2-1)\cdots(p_k-1)×p_1^{e_1-1}\cdots p_k^{e_k-1}=p_1^{e_1}\cdots p_k^{e_k}×\left( 1-\dfrac{1}{p_1} \right)\cdots \left( 1-\dfrac{1}{p_k} \right)$個である．
この記事を高評価した人
この記事に送られたバッジ
投稿者
