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 \times 53$ 以下の正整数を答えよ．

　このように，数値がある程度大きくなっても解けるだろうか．当然だが，問題1のように $73$ で割って $3$ 余る数を $3, 76, 149, \dots$ と書きだすような方法は論外である．
　この問題を解く方法はいくつかある．例えばEuclidの互除法を用いる方法や，百五減算のような方法がよく知られているが，ここでは合同式を使う方法を紹介したい．少しコツはいるが，慣れてしまえば一番早い方法だろう．

問題2の解説

　 $N = 73 x + 3 = 53 y + 2$ とおける．ここで $53$ を法とする合同式を考えよう．
　まず与式は次のように書かれる．
　　 $73 x + 3 \equiv 53 y + 2 \mod 53$
　この式は $20 x \equiv - 1$ と変形される．
　ここから最終的には $x \equiv * \mod 53$ という式を得たい．そこで，左辺の $20 x$ の係数を割れるように，右辺に $53$ の倍数を足したり引いたりする．
　ここからの途中計算は人によって変わるだろう．単純な例として $20 x \equiv - 1 + 53$ とすれば両辺を $4$ で割ることができて， $5 x \equiv 13$ という式を得る．あるいは $20 x \equiv - 1 - 159$ だと気づけば，一気に $20$ で割ることもできる．
　いきなり答えが出ては解説としてはつまらないので $5 x \equiv 13$ から続けよう．次は右辺を $5$ で割り切れる数にしたいので $5 x \equiv 13 - 53$ とするのがよいだろう．こうすれば $x \equiv - 8 \equiv 45$ を得るので， $N = 73 \times 45 + 3 = 3288$ だとわかる．

（確認問題）最初に $\mod 73$ を取った場合，同じ結論になることを確かめよ．

確認問題の答え

　最初の式は

53 y \equiv 1 \mod 73

である．

y

の係数（の絶対値）は小さいほどよいので

- 20 y \equiv 1

とするのが良いだろう．
　このあとは

- 20 y \equiv - 72

→

5 y \equiv 18 \equiv - 55

→

y \equiv - 11 \equiv 62

とするのが自然だろう．
　あるいは最初から

- 20 y \equiv 220

→

y \equiv - 11 \equiv 62

とすればもっと早い．
　なお係数

20

は大きな素因数を持たないので非常に扱いやすいが，この値があまりよくない場合には

126 y \equiv 1

から始める方がよい場合もある．これから始めると，例えば次のような変形が考え得る．

126 y \equiv - 72

→

7 y \equiv - 4

→

7 y \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)の答え

29 x + 4 = 41 y + 11

に対して，

\mod 29

で合同式を考える．

\begin{aligned} 12 y & \equiv - 7 \\ 12 y & \equiv - 36 \\ y & \equiv - 3 \equiv 26 \end{aligned}

　よって

41 \times 26 + 11 = 1077

．
　

(2)の答え

\mod 47

で合同式を考える．

\begin{aligned} - 21 y & \equiv - 18 \\ 7 y & \equiv 6 \equiv 147 \\ y & \equiv 21 \end{aligned}

　よって

73 \times 21 + 40 = 1573

．
　

(3)の答え

\mod 37

で合同式を考える．（注：

\mod 30

を取ると，両辺を

2, 3, 5

で割ることができない．なるべく約数の少ないものを法とする方が無難である．）

\begin{aligned} - 7 x & \equiv 6 \equiv - 105 \\ x & \equiv 15 \end{aligned}

（もちろん

30 x \equiv 6

からスタートしてもよい．すぐに

5 x \equiv 1

となるので，これでも簡単である．）
　よって

30 \times 15 + 1 = 451

．
　

(4)の答え

　最初の式は

60 x + 12 = 63 y + 36

である．両辺を

3

で割って

20 x = 21 y + 8

としよう．
　

\mod 20

で合同式を考えると，すぐに

y \equiv - 8 \equiv 12

を得る．
　よって

63 \times 12 + 36 = 792

．
　

　次は，もう少し難しい（というか面倒な）連立合同式である．

練習問題

　次の条件を満たす最小の正整数を答えよ．
(1)　 $10$ で割ると $3$ 余り， $11$ で割ると $5$ 余り， $12$ で割ると $9$ 余る
(2)　 $5$ で割ると $3$ 余り， $7$ で割ると $5$ 余り， $11$ で割ると $7$ 余り， $13$ で割ると $11$ 余る．

　(2)は工夫するとそこまで面倒ではないので，考えてみてほしい．

(1)の答え

　まずは

10 x + 3 = 12 z + 9

を使おう．（

10, 12

が共通の約数

2

を持つので，先にこちらの条件を使ったほうが数が小さくなる．）
　

\mod 10

で考えて

z \equiv - 3

を得るので

10 x + 3 = 12 z + 7 = 60 t - 27

となる整数

t

が存在する．
　次に

60 t - 27 = 11 y + 5

を解いていけばよい．

\mod 11

で考えて

t \equiv 2

を得る．
　

60 \times 2 - 27 = 93

(2)の答え

5 x + 3 = 7 y + 5 = 13 w + 11

を変形して

5 x^{'} - 2 = 7 y^{'} - 2 = 13 w^{'} - 2

である．つまり

5 \times 7 \times 13 t - 2

と置くことで，

3

つの条件を使い切ったことになる．
　あとは，

455 t - 2 = 11 z + 7

を解けばよい．

\mod 11

で考えて

t \equiv 5

を得る．
　

455 \times 5 - 2 = 2273

OMCの例題

OMC095(D)
　

中国剰余定理

　 $k$ 個の整数 $m_{1}, \dots, m_{k}$ が，どの $2$ つも互いに素であるとき，連立合同式
${\begin{cases} x & \equiv a_{1} \mod m_{1} \\ x & \equiv a_{2} \mod m_{2} \\ ⋮ \\ x & \equiv a_{k} \mod m_{k} \end{cases}$
を満たす整数 $x$ が， $m_{1} m_{2} \dots m_{k}$ を法として一意に存在する．

　証明は省略する．
　この定理は，要するに $2$ つのことを言っている．第一に $\mod m_{i}$ の部分が全て互いに素なら必ず解を持つこと．第二に，そのような解は $\mod \prod m_{i}$ を法として唯一であること（もう少しわかりやすい表現にすれば， $\prod m_{i}$ 以下の正整数の中でただ一つである）．
　 $\mod m_{i}$ の部分が全て互いに素でない場合はどうなるのか？を疑問に持った方は，高校数学の美しい物語を参照してほしい．

　次に，この定理に関する注意点を書いておく．
　中国剰余定理は，解の「存在」を保証してくれるものである．その値を「求める」ことについては，何も言及していない．連立合同式を解いて「中国剰余定理より $x \equiv *$ が解である」などと書いている答案などをたまに見るが，これは正確ではない．
　また，面倒なことを書くが，インターネット上のいくつかのホームページを見ても，あるいは数学の参考書等を見ても，中国剰余定理の練習問題として連立合同式を挙げていることがあるが，これも（厳密には）正確ではない．もちろんそれらの筆者が混同しているわけではなく，中国剰余定理の具体例を練習問題という名称で出題しているに過ぎないのだろう．しかしそれらの読者の中には，それが中国剰余定理を「用いた」例題であると誤解して，先に挙げたような答案を書くのだと思われる．
　さらに混乱させかねないことを書くが，「中国剰余定理より $x \equiv *$ が解である」という表現は必ず誤りかと言うと，そういうわけでもない．例えば次の答案を見よ．

問： $2$ で割ると $1$ 余り， $3$ で割ると $1$ 余り， $5$ で割ると $1$ 余り， $7$ で割ると $1$ 余る， $500$ 以下の正整数を全て答えよ．

答： $1$ は明らかに条件を満たす．中国剰余定理より $x \equiv 1 \mod 210$ のみが解である．すなわち，条件を満たす数は $210 n + 1$ の形で表され，答えは $1, 211, 421$ ．

　この例のように，解の唯一性を保証する意味で「中国剰余定理」を使うのは正しい表記である．なお，この例で「のみ」の部分を省略しても解答として悪くはない．つまり，「中国剰余定理より $x \equiv *$ が解である」という表現が直ちに誤りであるというわけでもない．
　以上，面倒な注であるとは思うが，中国剰余定理の意味を正確に覚えておいてほしいと思う．

　もう一つ，この定理に関する注意点である．中国剰余定理は，英語で Chinese remainder theorem と書かれるため，CRT と省略されることがしばしばある（日本語の文献でもしばしばこのように省略される）．この表記を自分で使える必要はないが，整数論の分野でCRTと見かけたら Chinese ナントカ theorem だったな→中国剰余定理だな，と思い出せるようにしておこう．

　最後に，中国剰余定理を用いる例題である．

　整数 $n$ を正整数 $k$ で割った余りを $n % k$ で表す．例えば $10 % 3 = 1, 35 % 5 = 0$ である．このとき，次の値を求めよ．
　 $\sum_{n = 1}^{1000} (n % 7) \times (n % 11) \times (n % 13)$

解答

7 \times 11 \times 13 = 1001

であり，

\sum_{n = 1}^{1000} (n % 7) (n % 11) (n % 13) = \sum_{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_{n = 1}^{1001} (n % 7) (n % 11) (n % 13) = (0 + 1 + 2 + \dots + 6) (0 + 1 + \dots + 10) (0 + \dots + 12) = 21 \times 55 \times 78 = 90090

オイラーの

ϕ

関数

（やや難）
　 $n$ 以下で $n$ と互いに素な正整数の個数を $ϕ (n)$ で表す（これは一般的な記法である）．
　 $n$ を素因数分解すると $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ と表されるとき（ただし $e_{k} \neq 0$ ），
　　 $ϕ (n) = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}})$