最初に頭の体操を1つ。比較的よく知られた「百五算」と呼ばれるものです。
「ある数(整数)を3で割ったら2余り、5で割ったら3余り、7で割ったら2余りました。ある数ってなぁに?」
ご存知の方には自明の暗号数理の基礎の基礎、ここからビットコイン(Bitcoin)の話をしようという趣旨ですが、少しおつき合いください。
「中国人の剰余問題」から
出題文に別段難しいことは何一つ記されていません。小学生でも題意はすぐに理解できる。で、これを一目見たとき、小学生でも大人でも結構です、読者のあなたはどんなふうに考えるでしょう?
その「筋」で、実はIT環境での適応力を判断することができるかもしれない、実は上の問題はやや微妙な性質を持っているのです。
ここでは一番一般的な方法から物事を考えてみましょう。「ある数」と言っているから未知数をXと置くなら、L、M、Nを整数として
X = 3×L + 2 (1)
= 5×M + 3 (2)
= 7×N + 2 (3)
となりますから、例えば(1)と(2)から
3L+2 = 5M+3 (4)
L =(5M+1)/3 (4)’
Lは整数だから、数(5M+1)は3の倍数にならなければならないはずです。そこで試しにM=1としてみるとL=2、X=8となりますが、これだと(3)式を満たしません。つまり
8 = 7N+2
となるいかなる整数Nも存在しない。よってX=8はペケと知れる。同様にM=2、3・・・と(4)式に当てはめて見ると5M+1=11、16となって3の倍数ではない。これを4としてみると5M+1=21で3の倍数となり、L=7、3L+2=23となり、(3)式で検算してみると
23 =7N+2 N=3
となって整数の値としてL、M、Nをめでたく確定することができました。ということで、
X = 23
がひとまずの答ですが、本当は一般的な解として、3、5、7の最小公倍数、3×5×7=105と整数nを用いて、
X = 105n + 23
と書くのが本来の正解、この最小公倍数105から「百五算」と呼ばれる古典的な問題であります。
これは「中国人の剰余問題」としてよく知られるもので、暗号数理の教科書では一般化した「中国人の剰余定理」として「剰余類」の表現を使って記されています。上の(1)と同様の内容を
X ≡ 2(mod3)
などと記しますが、多くの読者に分かり難い可能性を考えて、上のように表記してみました。