中国剰余定理について

こんにちは。草場です

みなさん、中国剰余定理、知ってます？高校でやるみたいなのですが、やった覚えがない。。。マスター・オブ・整数に乗っていました。ということで、調べてみました。Wikipediaのよると、以下です。

中国の剰余定理は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。

ふむ。

中国の剰余定理の最も基本的な形は次のような形式で述べることができる。
補助定理
与えられた二つの整数 m, n が互いに素ならば、任意に与えられる整数 a, b に対し、連立合同方程式
x ≡ a (mod m)
x ≡ b (mod n)
を満たす整数 x が mn を法として一意的に存在する。

この、法も高校でやるんですかね？マスター・オブ・整数には載ってましたが、やはり高校でやった覚えないですね。

整数 m と n に対して、 m = qn を満たす整数 q が唯一つ定まるとき、m ÷ n = q によって除算を定める。
m は被除数あるいは実と呼ばれ、n は除数あるいは法と呼ばれる。また q は m を n で割った商（しょう、英: quotient）と呼ばれる。商 q は他に「m の n を法とする商」「法 n に関する商」 などとも言う。

さて、細かくは以下に乗ってますので、読んでみてください。

中国剰余定理の証明と例題（二元の場合）