0404中国剰余定理の証明

これは質問の多かったところでもあります。特に存在性の証明については

何人かから質問がありました。

存在性の証明：なぜ「パーツ」は必ず作れるのか？

私たちがやりたいのは、以下の2つの条件を同時に満たす数字 x を見つけることです。

• x を m で割ると a 余る

• x を n で割ると b 余る （※前提として、m と n は「互いに素」という、共通の約数を持たない関係だとします）

1. 準備：魔法の等式

数学には、**「m と n が互いに素なら、mp + nq = 1 となる整数 p, q が必ず見つかる」**という超強力なルールがあります。これが、パーツを作るための「種」になります。

2. 実際にパーツを組み立てる

魔法の等式 mp + nq = 1 を、少しだけ形を変えてみましょう。 nq = 1 - mp

この式を、「m で割ったとき」と「n で割ったとき」で考えてみます。

• m で割ると？： 右側が「1 － (mの倍数)」の形なので、余りは 1 になります。

• n で割ると？： 左側が「nq」つまり n の倍数そのものなので、割り切れて余りは 0 です。

ほら！これで**「n の倍数なのに、m で割ると 1 余る特殊な数」が完成しました。これをパーツ1**と呼びましょう。

同じようにして、「m の倍数なのに、n で割ると 1 余る特殊な数（mp）」も作れます。これをパーツ2と呼びます。

3. 合体！

あとは、出したい余り（a と b）をそれぞれのパーツに掛け算して合体させるだけです。 x = (a × パーツ1) + (b × パーツ2)

これが答えの数字になります。本当になっているか、確かめてみましょう。

• m で割ったとき パーツ2は「m の倍数」なので、何倍しても m で割り切れて消えます。 パーツ1は「m で割ると 1 余る数」だったので、それを a 倍した全体では、余りは a になります。

• n で割ったとき パーツ1は「n の倍数」なので、何倍しても n で割り切れて消えます。 パーツ2は「n で割ると 1 余る数」だったので、それを b 倍した全体では、余りは b になります。

結論

1. どんな数字 m, n でも、mp + nq = 1 という式が作れる。

2. そこから「片方で割り切れて、もう片方で 1 余るパーツ」が必ず作れる。

3. そのパーツを組み合わせれば、どんな余りの条件でも満たす数 x が必ず存在すると言える。

これが「存在性」の証明の正体です。