連立合同式

整数の性質の問題で，

「aを整数とする。a+2は4の倍数、a+3は7の倍数であるとき，a+10が28の倍数であることを示せ。」

という問題を量産したい。

「a+pはmの倍数，a+qはnの倍数であるとき，a+rがmnの倍数であることを示せ。」

と置くことができるが，

m,nが互いに素であれば、p,qにどのような数を選んでもrを0以上mn未満の整数からただ1つ決めることができる。

いわゆる「中国人の剰余の定理」である。

ざっくり言えば，互いに素である2つの法m,nによる余りを使ってタグ付けすると，mn通りの数を分類できるという話だ。

まぁ、数をmn個並べて余りを出しておいてそこから選べばいいよね。