第1章 江戸時代初期

コラム 中国式剰余定理(難易度2)

この定理は、『孫子算経』という古代中国の本に登場していることから欧米で Chinese remainder theorem と呼ばれる、数の余りに関する定理です。『孫子算経』には「ある数を3で割ると2余り、5で割ると3余り、7で割ると2余るという。その数は何か」という問題が載っており、この問題を
「3で割ると2余る数に140があり、5で割ると3余る数に63があり、7で割ると2余る数に30がある。この三つの数をすべて加えると233となるが、この233から105を次々に引いて行くと128、23となり、23が条件を満たす最小の数である」
という風に解いています。この105は割る数の積3×5×7 から来ており、この数から、和算ではこの算法を百五減算と呼びます。
それでは何故この方法で解けるのでしょうか。

aは5でも 7でも割り切れるが、3で割ると2余る数、
bは3でも7でも割り切れるが、5で割ると3余る数、
cは3でも5でも割り切れるが、7で割ると2余る数  とします。

上の解法の140がaに当たり、63がbに当たり、30がcに当たることを確かめてください。aの場合、140を素因数分解すると5×7×22です。5×7が入っているので、5でも7でも割り切れます。
ここでM=a+b+c という数字を作ってみますと、Mを3で割ると2余り、5で割ると3余り、7で割ると2余ります。従って140+63+30=233 は確かに条件を満たす数ですが、そのような数は105おきに無限に存在するということを述べているのが、中国式剰余定理です。この定理を少し簡単な場合について説明してみましょう。

. 2で割ると1余り、3で割ると2余る数は何か。

1から12までの数について、2および3で割った余りを表にすると以下のようになります。

n 1 2 3 4 5 6 7 8 9 10 11 12
2で割った余り 1 0 1 0 1 0 1 0 1 0 1 0
3で割った余り 1 2 0 1 2 0 1 2 0 1 2 0

1から12までの数について、2および3で割った余りを表にすると以下のようになります。

2と3は互いに素な数ですので、2×3=6 種類のパターンが現れ、n=1~6のパターンがn=7~12でも繰り返されています。この表から、求める数は5、11であることが分かり、さらに6ずつ加えた17、23、29...が同じ性質を持った数字であると予想できます。そして、互いに素なp個の数で割った余りのパターンは、そのp個の数の積を周期として繰り返すということを述べているのが中国式剰余定理なのです。
これを『孫子算経』のやり方で解くと、3の倍数のうち2で割ると1余る数である3、9、15等を見つけ、また2の倍数のうち3で割ると2余る数である2、8、14等を見つけ、その和を取ると5、11、17 ... という求める数字を見つけることができます。
もとの百五減算に戻りますと、1から105までの数を3、5、7で割った余りのパターンはすべて異なります。

n123456789101112131415...2170105
3で割った余り120120120120120...010
5で割った余り123401234012340...100
7で割った余り123456012345601...000

もとの百五減算に戻りますと、1から105までの数を3、5、7で割った余りのパターンはすべて異なります。

106から210までは同じパターンの繰り返しとなり、以下、105個のグループごとに無限に繰り返されます。このパターンを書き出せば、求める数を見つけることができるわけですが、手間のかかる作業なので、上記のようなMを作る方法のほうが簡単に答えを求めることができます。

吉田光由『塵劫記』には「ある数を3で割ると2余り、5で割ると1余り、7で割ると2余るという。その数は何か」と、数字を少し変えた問題が出ています。こちらを解いてみましょう。
2×5×7=70は5と7で割り切れ、3で割ると1余りますので、その2倍の140は5と7で割り切れ、3で割ると2余ります。
3×7=21は3と7で割り切れ、5で割ると1余ります。
3×5=15は3と5で割り切れ、7で割ると1余りますので、その2倍の30は3と5で割り切れ、7で割ると2余ります。
そこで、この3つの数を加えた 140+21+30=191 は3で割ると2余り、5で割ると1余り、7で割ると2余る数字です。この数字から3×5×7=105 を引いても、この数字は3でも5でも7でも割り切れますので、余りには影響を与えません。従って、191-105=86 が求める数字の最小のものです。
(実は、5×7=35は5と7で割り切れ、3で割ると2余る数ですので、35+21+30=86とすぐに解が出ます。上のやり方は、pとqで割り切れ、rで割るとs余る数を求めるのに、まずpとqで割り切れ、rで割ると1余る最小の数を探して、それをs倍するとpとqで割り切れ、rで割るとs余る数が求まるという一般的方法です。)

和算では、中国式剰余定理の解法を翦管術(せんかんじゅつ)と呼んでいます。関孝和が『括要算法』で用いた用語ですが、これは関が勉強した13世紀中国の数学書『楊輝算法』からの流用であると言われます。

『括要算法』で取り上げられている問題と解答を紹介してみますと、「5で割ると1余り、7で割ると2余る数は何か」という問題に対して、「7の倍数で5で割ると1余る数21と、5の倍数で7で割ると2余る数30、これらの和 51 は5で割ると1余り、かつ7で割ると2余る。5×7=35 は5でも7でも割り切れるので、51-35 = 16 が求めるものである」という論理の運びをしています。
関はさらに「36で割ると2余り、48で割ると14余る数は何か」「3で割ると2余り、5で割ると1余り、7で割ると5余る数は何か」などの問題を記しています。前者は、割る数が互いに素でないので、工夫が必要で、関はその方法も言及しています。この問題は、腕試し問題Q3で、現代数学の用語で説明しています。

現在の数学では中国式剰余定理は、K.F.ガウス(1777-1855)の考案した合同式という表記法を使って議論を進めて行きます。

ガウスは24歳の時に刊行した『整数論研究(Disqvisitiones arithmeticae)』(1801)を、まず合同式の説明から始めました。合同式は3世紀アレクサンドリアの数学者ディオファントスが論じた不定方程式の問題に由来する記号で、今では初等整数論という分野で系統的に論じられています。なお、ガウスのこの本は1995年に『ガウス整数論』というタイトルで邦訳が出ています。137≡2(mod 3)のような合同式は学校では教えられなかったかもしれませんが、合同式で表わすと足し算、引き算、掛け算が普通にでき、機械的に解きやすくなります。

これらについては「合同式と剰余定理」をご覧ください。

ページ先頭へ