中国剰余定理の解説

ある数は 3 で割ると 2 余り、5 で割ると 3 余り、7 で割ると 2 余ります。その数はいくつでしょうか。1 つずつ試していけばやがて 23 にたどり着きますが、この問いには定理が隠れています。割る数どうしが公約数を持たない限り、それらの積より小さい答えは必ずちょうど 1 つあり、試すことなく求められるのです。この定理は約 1,500 年前から知られ、今も暦、コンピューターの計算、そしてウェブを守る暗号の中で働いています。

3 で割って 2、5 で割って 3、7 で割って 2 余る数を示す 3 列の印が、23 の列でそろっている図
3 で割って 2、5 で割って 3、7 で割って 2 余る数を示す 3 列の印が、23 の列でそろっている図

『孫子算経』の問題

3〜5 世紀の中国の算術書『孫子算経』は、3 つずつ数えると 2、5 つずつ数えると 3、7 つずつ数えると 2 余る物の数を問います。答えは 23 で、その解き方は今も教えられています。3 つずつ数えて余った 1 個につき 70、5 つずつで余った 1 個につき 21、7 つずつで余った 1 個につき 15 をとって足し、105 を引けるだけ引くのです。2 × 70 + 3 × 21 + 2 × 15 = 233、233 − 2 × 105 = 23 です。明代の歌が 70、21、15、105 という数を何百年も人々の記憶にとどめました。秦九韶は 1247 年に一般的な解法「大衍求一術」を示し、同じ問題はフィボナッチの 1202 年の『算盤の書』にも登場します。カール・フリードリヒ・ガウスは 1801 年の『整数論の研究』で定理を現代の形で述べました。

『孫子算経』の清代版の一ページ。3〜5世紀の中国の算術書で、三、五、七で数えるとそれぞれ2、3、2余る数を求める。
『孫子算経』の清代版の一ページ。3〜5世紀の中国の算術書で、三、五、七で数えるとそれぞれ2、3、2余る数を求める。
カール・フリードリヒ・ガウス、クリスティアン・アルブレヒト・イェンセンによる1840年の肖像。1801年の『算術研究』で合同の記法 a ≡ b (mod n) を導入した。
カール・フリードリヒ・ガウス、クリスティアン・アルブレヒト・イェンセンによる1840年の肖像。1801年の『算術研究』で合同の記法 a ≡ b (mod n) を導入した。

定理の内容

どの 2 つも公約数を持たない法 n₁、n₂、…、nₖ と、任意の余り a₁、a₂、…、aₖ をとります。すると、すべての i について nᵢ で割ると aᵢ 余る整数 x が、0 から N − 1 の間にちょうど 1 つあります。ここで N = n₁ × n₂ × … × nₖ です。ほかの解はすべて、それと N の倍数だけ異なります。合同算術の記法でいえば、連立合同式 x ≡ aᵢ (mod nᵢ) は解を持ち、それは N を法として一意です。言い換えれば、0 から N − 1 までの数と、その余りの並びはまったく同じ情報を持っています。3 × 5 × 7 = 105 個の数と、3 × 5 × 7 = 105 通りの余りの並びが、1 つずつ対応するのです。

解を組み立てる

70、21、15 という数は魔法ではありません。どれも自分の法で割ると 1 余り、ほかの法で割ると 0 余ります。70 = 2 × 35 は 5 と 7 の倍数で、3 で割ると 1 余ります。一般には、nᵢ 以外のすべての法の倍数である Nᵢ = N / nᵢ をとり、Nᵢ の mod nᵢ での逆元 yᵢ を掛けます。Nᵢ と nᵢ は公約数を持たないので逆元は存在し、拡張ユークリッドの互除法がそれを求めます。最大公約数を求める互除法の割り算を行い、ベズーの等式 1 = s × nᵢ + t × Nᵢ までさかのぼると、t が逆元になります。すると x = a₁N₁y₁ + a₂N₂y₂ + … を N で割った余りは、すべての式を満たします。各項は自分の式に合い、ほかのすべての式では消えるからです。

式を 1 つずつ解く

法の積をすべて使わない第 2 の方法もあります。x ≡ 2 (mod 3) の解はすべて x = 2 + 3t の形をしています。これを次の式に代入すると 2 + 3t ≡ 3 (mod 5)、つまり 3t ≡ 1 (mod 5) となり、3 の mod 5 での逆元 2 を掛けると t ≡ 2 (mod 5) が得られます。すると x = 2 + 3 × 2 = 8 で、最初の 2 つの式を合わせると x ≡ 8 (mod 15) です。3 つ目の式でも同じことを繰り返すと、8 + 15t ≡ 2 (mod 7) から t ≡ 1、よって x ≡ 23 (mod 105) です。この代入法は数を小さく保ち、コンピューターがこうした連立合同式を解くふつうの方法であり、法が公約数を持つ場合にも使えます。

公約数を持つ法

2 つの法が公約数を持つと、それらの式は重なり合います。x ≡ 1 (mod 4) はすでに x が奇数であることを意味し、x ≡ 4 (mod 6) は x が偶数であることを意味するので、両方を満たす x はありません。一般に x ≡ a (mod m) と x ≡ b (mod n) が同時に成り立つのは、a と b を g = gcd(m, n) で割った余りが等しいとき、つまり g が a − b を割り切るときに限ります。そのとき解は m × n ではなく lcm(m, n) = m × n / g を法として一意です。2、3、4、5、6 個ずつ取り出すと 1 個余り、7 個ずつだと余らない卵のかごという昔からの問題の答えは 301 で、420 = lcm(2, 3, 4, 5, 6, 7) ごとに繰り返します。連立合同式に解があるのは、どの 2 つの式も矛盾しないときに限るので、解のない連立合同式には必ず矛盾する組が含まれています。

暦、コンピューター、RSA

1583 年、ジョゼフ・スカリゲルは 28 年の太陽周期、19 年の太陰周期、15 年のインディクティオという 3 つの暦の周期を組み合わせ、28 × 19 × 15 = 7,980 年のユリウス周期を作りました。定理により、どの年も 3 つの周期番号の独自の組み合わせを持ち、周期は 3 つすべてが 1 だった直近の年、紀元前 4713 年に始まります。天文学者は今もそこからユリウス日を数えています。コンピューターはこの定理を使い、巨大な数を小さな余りの並びとして計算します。余りは別々に並行して足したり掛けたりでき、最後にまとめられます。RSA の復号も同じしくみです。n = p × q のとき c^d mod n を mod p と mod q の 2 回のべき乗として計算し、定理でまとめると、mod n のべき乗 1 回より約 4 倍速くなります。ミニョットの方式やアスムス・ブルームの方式といった秘密分散法は、秘密を余りの中に隠し、十分な数の余りがそろったときだけ秘密がわかるようにします。

ロン・リベスト、アディ・シャミア、レン・アドルマン(左から右へ)
ロン・リベスト、アディ・シャミア、レン・アドルマン(左から右へ)

試してみよう

ソルバーを開いて、20 個までの式と 200 桁までの数で好きな連立合同式を入力するか、例題を選んでください。孫子の問題、卵のかご、ユリウス周期、2 本のバスの時刻表、RSA の復号、そして解のない連立合同式があります。計算過程は、構成法または代入法で、すべての逆元を拡張ユークリッドの互除法で求めながら、あなたの数を使って書き出されます。図は各式を満たす数に印をつけて、すべてが出会うただ 1 つの列を見せたり、2 つの式の余りを、どの数も自分のマスを持つ表に並べたりします。

よくある質問

連立合同式の解は一意ですか?

法の倍数の違いを除いて一意です。x = 23 が孫子の問題の解なら、23 + 105 = 128、233、−82 も解です。105 を足しても余りはどれも変わらないからです。定理がいうのは、0 から 104 の間に解がちょうど 1 つあるということで、法が公約数を持つ場合は最小公倍数より小さい解がちょうど 1 つあります。

なぜ法は互いに素でなければならないのですか?

構成法では、Nᵢ が mod nᵢ で逆元を持つ必要があり、それは公約数がないときにしか存在しないからです。定理そのものについては、公約数があると一部の式が重なり合うからです。そのとき連立合同式は解を持たないか、異なる解の数が少なくなり、解は積ごとではなく最小公倍数ごとに繰り返します。

モジュラ逆数を手で求めるには?

拡張ユークリッドの互除法を使います。15 の mod 7 での逆元なら、15 = 2 × 7 + 1 より 1 = 15 − 2 × 7、15 × 1 ≡ 1 (mod 7) なので逆元は 1 です。35 の mod 3 での逆元なら、35 = 11 × 3 + 2、3 = 1 × 2 + 1 より 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35 となり、逆元は −1 ≡ 2 です。法が小さければ、積の余りが 1 になるまで 1、2、3、… と試してもかまいません。

この定理と時計にはどんな関係がありますか?

mod n の余りは、n 時間の時計の針の位置です。3 時間と 5 時間の 2 つの時計を同時に動かし、1 時間ずつ進めると、最初に戻るまでに 15 通りの位置の組をちょうど 1 回ずつ示します。3 と 5 は公約数を持たないからです。4 時間と 6 時間の時計は 12 歩で元に戻り、24 通りの組のうち 12 通りしか示しません。奇数の位置と偶数の位置が同時に現れることはないのです。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

中国剰余定理ソルバーを開く