PSoC 4200 Prototyping Kit (5)

中国剰余定理 PSoC4

「中国剰余定理」(Chinese Remainder Theorem) は古代中国の算術書「孫子算経」に由来するもので「孫子の定理」と呼ばれることもあります。
「Chinese」は「中国の」とか「中国式」とか言うよりも、むしろ「(名前の分からない) 中国人の」といった意味合いです。
それは「孫」さんということになりますが、「孫子算経」が書かれた年代も 3 〜 5 世紀ごろとはっきりせず、作者も不明で、結局「名前の分からない中国人」という所に戻ってしまいます。
ちなみに、「孫子の兵法」で知られる「孫子」は紀元前 5 〜 4 世紀ごろに書かれたもので、時代が違います。
「孫子算経」には次のような問題と答え、解法が記されているだけで、定理の証明が載っているわけではありません。 これを一般化したものが中国剰余定理です。

  • ある数 (自然数) があって、
  • 3 で割ると 2 余り、
  • 5 で割ると 3 余り、
  • 7 で割ると 2 余る。
  • もとの数はいくつか？

この条件を満たす数の一般解は k を正の整数として
23 + 105•k
となります。　そのなかで最も絶対値の小さい数 23 を答えとします。　一般解の中に現れる 105 にちなんで、和算では「百五減算」と呼ばれています
HP の電卓 HP49 シリーズ (hp48gII、hp49g、hp49g+、hp49gII、hp50g) では CAS (Computer Algebra System) モードで使える ICHINREM() 関数があるようです。　先頭の「I」は「逆」を表すものではなく「整数」を表す「I」です。　
中国剰余定理の対象は整数環だけでなく多項式環にも一般化でき、HP49 シリーズでは多項式環上の計算を行う関数の方を「CHINREM()」(CHINese REMainder の意) と命名しているので、整数を対象にする方を ICHINREM() と呼んでいるようです。
また、Mathematica では ChineseRemainder[] 関数で計算できるようです。
HP の電卓も、Mathmatica も持っていないので試すことはできないのですが、ググっていたら、フリーの数式処理システムである「Maxima」のメーリング・リストで下のリンクのような投稿を見つけました。

https://www.ma.utexas.edu/pipermail/maxima/2009/019672.html

内容を要約すると、Maxima にはガロア体 (有限体) 上での計算を行うパッケージ「gf.mac」が付属していて、その中の (付属ドキュメントには載っていない) chrem() 関数で計算できるということです。
さっそく試して見た結果を下に示します。

gf パッケージは標準で付属していますが、デフォルトでは読み込まれていないので、まず load(gf) により読み込みます。
その後は孫子算経の例を入力してみました。　正しく結果の 23 が得られています。
次回以降では中国剰余定理の証明や一般的な解法には立ち入らず、今回の応用に必要な部分だけを説明します。