中国剰余定理

更新日：2021-12-13

この記事では，数学オリンピックにおける中国剰余定理の応用について解説します．この記事は，Evan Chen氏による教材 The Chinese Remainder Theorem の翻訳です（翻訳・掲載に関して，本人より許可を得ています）.

はじめに

まずは準備として形式的な中国剰余定理のステートメントを述べましょう. これは誰でも知っています.

定理. (中国剰余定理).

m_{1}, m_{2}, \dots, m_{k}

をどの二つも互いに素な正の整数とし, それらの総積を

M

とする. このとき, 任意の整数の組

(x_{1}, x_{2}, \dots, x_{k})

に対し,

x \equiv x_{i} (\mod m_{i}) (i = 1, \dots, k)

をみたす整数

x

が

m o d M

で一意に存在する.

しかし, この「定理」自体に大した意味はありません. あくまで, 十分な経験を積めば容易に得られるような「直感」をただ定式化したに過ぎないのです. とはいえ, それはこの「定理」が役立たずという意味ではありません. 背後の「直感」が有用だからこの「定理」は有用なのです. その「直感」の汎用性を理解するため, 「定理」の異なる表現を見ていきましょう.

どんな「中身の無い」定理にも言えることですが, その発想をしっかりと吸収することが大切です. 中国剰余定理が最も効果的に適用されるのは, 明示的でないときです. 以下で扱う問題においても, 共通して鍵となるのは, 中国剰余定理が重要なステップではないということです. むしろ, 何をすべきかを明らかにするために使われるものなのです.

1. Construction (構成)

表現 1. 各

i

で

x \equiv x_{i} (\mod m_{i})

をすべて成立させる

x

が, 実際何なのかはわからないが, 何かしら存在はする.

こうして得られる $x$ は恐ろしく巨大になるかもしれません. また, $x$ の具体的な値を明示的に表示するステップが存在するわけではありません. しかし真に大切なのは, とにかく何かしら存在することが保証されることなのです.

判定中

USAMO 2008 問1

任意の正の整数 $n$ に対し, いずれも $1$ より大きく, かつどの二つも互いに素であるような正の整数 $k_{0}, k_{1}, \dots, k_{n}$ であって, $k_{0} k_{1} \dots k_{n} - 1$ が二つの連続する整数の積として表せるものが存在することを示せ.

考え方

問題を言い換えれば, $f (t) = t (t + 1) + 1$ が相異なる $n + 1$ 個の素因数をもつ $t$ の存在を言えばよいということです. ではこの「たくさんの素因数をもつ」という条件をどう処理すればよいでしょうか？ $n + 1$ 個の素数 $p_{1}, \dots, p_{n}$ に対して, $P (t) \equiv 0 (\mod p_{i})$ をみたす $t$ の存在を言えばよいのですが, ここで中国剰余定理を思い出しましょう. 各 $i$ について, $P (t_{i}) \equiv 0 (\mod p_{i})$ をみたす $t_{i}$ の存在さえ言えてしまえばよいのです. したがって, 問題はただ単に $t^{2} + t + 1$ という形式の倍数をもつ素数が無数に存在することを示すのみとなりました. これは素数の無限性の有名な証明と同じです. すなわち, 有限と仮定すれば, それらの総積 $N$ について $N^{2} + N + 1$ を見れば矛盾します.

解答

工事中

判定中

TSTST 2012 問3

正の整数に対して定義され正の整数値をとる関数 $f$ が以下の条件をみたす：

$m$ と $n$ が互いに素ならば, $f (m)$ と $f (n)$ も互いに素である.
任意の正の整数 $n$ に対し, $n ≦ f (n) ≦ n + 2012$ である.

このとき, 正の整数 $n$ および素数 $p$ について, $f (n)$ が $p$ の倍数ならば $n$ も $p$ の倍数であることを示せ.

考え方

ある $n, p$ について $p ∣ f (n)$ かつ $p ∤ n$ として矛盾を導きます. アイディアは, $f (N) = N$ なる十分大きい $N$ を構成することです. $n + p + 2013$ より大きい相異なる $2012 \times 2013$ 個の素数 $q_{i, j}$ をとります. 以下の表を考えましょう.

$\begin{array}{ccccc} N + 1 & N + 2 & \dots & N + 2012 \\ M & q_{0, 1} & q_{0, 2} & \dots & q_{0, 2012} \\ M + 1 & q_{1, 1} & q_{1, 2} & \dots & q_{1, 2012} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ M + 2012 & q_{2012, 1} & q_{2012, 2} & \dots & q_{2012, 2012} \end{array}$

例えば, $N + j$ は $q_{0, j}, \dots, q_{2012, j}$ ですべて割りきれるといった塩梅です. 中国剰余定理よりそのような $N, M$ をとることができます. さらに $N \equiv 0 (\mod p), N \equiv 1 (\mod n), M \equiv 1 (\mod N)$ を課しましょう.

このとき $f (N) = N$ です！どうすればわかるでしょうか？ $N$ と $M$ は互いに素なので, $f (N)$ と $f (M)$ も互いに素です. ここで $f (M)$ は $N + 1, \dots, N + 2012$ のいずれとも互いに素ではないので, $f (N) = N$ となるほかありません.

ここまで来ればもう終わりです. あとは $f (N) = N$ と $f (n)$ が互いに素なことを利用すればよいです.

解答

工事中

2. Lifting (持ち上げ)

表現 2. 各

i

で

x \equiv k (\mod m_{i})

がすべて成立するとき,

x \equiv k (\mod M)

でもある.

判定中

USAMO 2014 問6 (改)

以下の条件をみたす定数 $c > 0$ が存在することを示せ：

正の整数 $a, b, n$ について, 任意の $0 ≦ i, j ≦ n$ で $gcd (a + i, b + j) > 1$ のとき, $min {a, b} > (c n)^{n}$ が成立する.

この問題の興味深い点はどこでしょうか？仮定は整除のみに関連するのに対し, 結論は大小関係のみに関連しています. これらはどのように関係するでしょうか？一般に乗法の構造というのは扱いが難しいものです. そこで, この形式の中国剰余定理を思い起こしてみましょう. 例えば $a + i \equiv 0 (\mod something really big)$ が示せるとしたら, どうでしょうか？

考え方

条件より任意の $0 ≦ i, j ≦ n$ について, ある素数が $a + i$ と $b + j$ をともに割りきります. この情報を, 例えば以下のような $(n + 1) \times (n + 1)$ の表に落とし込んでみましょう. 実際にはすべての位置になんらかの素数が入ります.

$\begin{array}{ccccccccccc} . & 2 & . & 2 & . & 2 & . & 2 & . & 2 & . \\ . & . & 5 & 7 & . & . & . & 5 & . & . & 7 \\ . & 2 & 3 & 2 & . & 2 & . & 2 & 3 & 2 & . \\ . & . & . & . & . & . & . & . & . & . & . \\ . & 2 & . & 2 & . & 2 & . & 2 & . & 2 & . \\ . & . & 3 & . & . & 3 & . & . & 3 & . & . \\ . & 2 & 5 & 2 & . & 2 & . & 2 & . & 2 & . \\ . & . & . & . & . & . & . & . & . & . & . \\ . & 2 & 3 & 2 & . & 2 & . & 2 & 3 & 2 & 7 \\ . & . & . & . & . & . & . & . & . & . & . \\ . & 2 & . & 2 & . & 2 & . & 2 & . & 2 & . \end{array}$

それぞれの素数は, 一定の間隔の “subgrid” として表れていることに留意しましょう. これより, 素数 $p$ は “密度” として表全体の高々 $p^{- 2}$ ほどを占めます. しかし, $\sum_{p} p^{- 2}$ はそこまで大きくありません. 実際これは $1 / 2$ 未満です. すなわち, この表には “十分大きい” 素数がたくさん入り込むことになります. 総和 $\sum {⌈ \frac{n + 1}{p} ⌉}^{2}$ をちゃんと評価してあげることで, 表の半分以上は $0.001 n^{2}$ より大きい素数になることがわかります. すなわち, ある行について半分以上が $0.001 n^{2}$ より大きく, $a + i$ は $(0.001 n^{2})^{n / 2} = (c n)^{n}$ より大きいそれらの積で割りきれます.

解答

工事中

3. Destruction (分解)

表現 3.

m o d M

での振る舞いを調べたければ, 各

i

について

m o d m_{i}

で, 特に素べきを法として振る舞いを調べればよい.

この表現には, あまり面白い例を与えることができません. なぜならば, 多くの場合において, この表現を噛ませたところで問題自体はあまり変わらないからです. 次の例はかなり馬鹿げたものですが, 演習問題にはより面白いものがあります.

表現 2. 各

i

で

x \equiv k (\mod m_{i})

がすべて成立するとき,

x \equiv k (\mod M)

でもある.

判定中

Math Prize 2010 問2

任意の正の整数 $n$ に対し, $4 a^{2} + 9 b^{2} - 1$ が $n$ で割りきれるような整数 $a, b$ が存在することを示せ.

解答

$n$ が素べきの場合に示せば十分である. $n$ が $2$ べきのとき, $3 b \equiv 1 (\mod n)$ なる $b$ が存在するから, これをとり $a$ を $0$ にすればよい. それ以外のとき, $2 a \equiv 1 (\mod n)$ なる $a$ が存在するから, これをとり $b$ を $0$ にすればよい.

演習問題

判定中

IMO 1989 問5

任意の正の整数 $n$ に対し, いずれも素べきでないような $n$ 個の連続する正の整数がとれることを示せ.

ヒント

$p_{i} q_{i} ∣ x + i$ を課してみよ.

解答

工事中

判定中

有名問題

$n$ を正の整数とする. $1$ 以上 $n$ 以下の整数 $x$ であって, $x^{2} \equiv x (\mod n)$ なるものの個数を, $n$ を用いて表せ.

ヒント

$n$ を割りきる素べきについて解く. 答えは $2$ べきになる.

解答

工事中

判定中

IMO 2009 問1

$n$ を正の整数とし, $a_{1}, \dots, a_{k}$ $(k ≧ 2)$ を集合 ${1, \dots, n}$ の相異なる元とする. $i = 1, \dots, k - 1$ に対し, $a_{i} (a_{i + 1} - 1)$ は $n$ で割りきれるとする. このとき, $a_{k} (a_{1} - 1)$ は $n$ で割りきれないことを示せ.

ヒント

背理法を用いる. $n$ を割りきる素べき $p^{r}$ をとり, 任意の $i$ に対して $a_{i} \equiv 0 (\mod p_{r})$ であるか, または任意の $i$ に対して $a_{i} \equiv 1 (\mod p_{r})$ であることを示す.

解答

工事中

判定中

APMO 2009 問4

正の整数 $k$ が任意に与えられている. このとき, 相異なる正の整数 $a_{1}, b_{1}, a_{2}, b_{2}, \dots, a_{k}, b_{k}$ であって, $\frac{a_{1}}{b_{1}}, \frac{a_{2}}{b_{2}}, \dots, \frac{a_{k}}{b_{k}}$ が等差数列であり, かつ各 $i = 1, 2, \dots, k$ に対し $a_{i}$ と $b_{i}$ が互いに素であるようなものが存在することを示せ.

ヒント

正の整数 $x, N$ であって, 以下を既約にすると条件をみたすものを考えよ. $\frac{x + 1}{N}, \frac{x + 2}{N}, \dots, \frac{x + k}{N}$ さらに, それぞれの分数でちょうど一つの素数のみが割られるようにせよ.

解答

工事中

判定中

ELMO 2014 SLP N7

以下の条件をみたす正の整数の組 $(a, b, c)$ をすべて求めよ：

正の整数 $n$ が $2014$ 以下の素数のいずれでも割りきれないとき, $a^{n} + b^{n} + n$ は $n + c$ で割りきれる.

ヒント

適当な十分大きい素数 $p$ について, $n$ を $mod p$ と $mod p - 1$ で固定せよ. $p$ はどのようにとるべきか？

解答

工事中

#10

判定中

出典不明

$3$ 以上の整数 $a > b > c$ が以下の条件をみたすとき, $a, b, c$ のうち少なくとも一つは素数でないことを示せ. $a ∣ b c + b + c, b ∣ c a + c + a, c ∣ a b + a + b$

ヒント

因数分解できる形に持ち込め (Simon’s Favorite Factoring Trick).

解答

工事中

#11

判定中

USA TST 2015 問2

任意の正の整数 $n$ に対し, $n$ 個の正の整数からなる集合 $S$ であって, 以下の条件をみたすものが存在することを示せ.

任意の相異なる $S$ の $2$ 元 $a, b$ に対し, $a - b$ は $a$ と $b$ を割りきるが, 他の $S$ の元いずれをも割りきらない.

ヒント

$n = 3$ のとき, $x_{1} \underset{2}{\underset{⏟}{}} x_{2} \underset{3}{\underset{⏟}{}} x_{3}$ から ${10, 12, 15}$ が見つかる. $n = 4$ のとき, $x_{1} \underset{60}{\underset{⏟}{}} x_{2} \underset{90}{\underset{⏟}{}} x_{3} \underset{7}{\underset{⏟}{}} x_{4}$ から…

解答

工事中

#12

判定中

NIMO 2013 Winter 問8 (改)

有限集合 $X$ に対し, すべての元の総和, 総積をそれぞれ $S (X), P (X)$ で表す.

ともに正の整数からなる有限集合 $A, B$ が $| A | = | B |, P (A) = P (B), S (A) \neq S (B)$ をみたす. $A$ または $B$ に含まれる $n$ およびその素因数 $p$ について, 常に $p^{36} ∣ n$ かつ $p^{37} ∤ n$ が成立するとき, $| S (A) - S (B) | > 5 \cdot 10^{7}$ を示せ.

ヒント

$| S (A) - S (B) |$ が $2^{3} \cdot 3^{3} \cdot 5 \cdot 7 \cdot 13 \cdot 19 \cdot 37$ で割りきれることを示せ.

解答

工事中

#13

判定中

ELMO 2013 問5

以下の条件をみたす整数係数多項式 $P (n)$ をすべて求めよ：

$x y z$ 空間内の格子点それぞれに正の整数を割り当てる方法であって, 任意の正の整数 $n$ に対し, 任意の $n \times n \times n$ の部分グリッドに割り当てられた $n^{3}$ 個の正の整数の和が $P (n)$ で割りきれるものが存在する.

ヒント

$1$ 次元のケースをまず考えよ. $3$ 次元でも状況はそう変わらない.

解答

工事中

#14

判定中

ELMO 2013 問3

$m_{1}, m_{2}, \dots, m_{2013} > 1$ をどの $2$ つも互いに素な整数とし, $i = 1, \dots, 2013$ に対し $A_{i}$ を $1$ 以上 $m_{i} - 1$ 以下の整数からなる集合とする (空でもよい). このとき, 以下の条件をともにみたす正の整数 $N$ が存在することを示せ.

$N ≦ (2 | A_{1} | + 1) (2 | A_{2} | + 1) \dots (2 | A_{2013} | + 1)$
各 $i = 1, \dots, 2013$ に対し, $N$ を $m_{i}$ で割った余りは $A_{i}$ に含まれない.

ヒント

$t_{i} \equiv 1 (\mod m_{i})$ かつ $t_{i} \equiv 0 (\mod m_{j})$ $(i \neq j)$ なる $t_{i}$ をとる. $b_{i} \in B_{i}$ によって以下の形式に表せる数を考えよ. $\sum b_{i} t_{i}$ ここで集合 $B_{i}$ は, 任意の $x, y \in B_{i}$ で $x - y \notin A_{i}$ となるようにとる. このとき, 以下をみたせることをgreedilyに示せ. $| B_{i} | \geq \frac{m_{i}}{2 | A_{i} | + 1}$

解答

工事中