最小の解
法
各法

    合同式

    中国剰余定理についてもっと詳しく

    中国剰余定理ソルバー

    物の山を 3 つずつ数えると 2 余り、5 つずつ数えると 3 余り、7 つずつ数えると 2 余る。物は 23 個、あるいは 128 個、あるいは 233 個で、105 ごとに答えが 1 つあります。これが中国剰余定理の名の由来となった『孫子算経』の問題です。連立合同式 x ≡ a (mod n) を、式の数も数の大きさも自由に入力すると、答え、あなたの数を使った計算過程、そしてなぜ成り立つかを示す図が表示されます。すべての式が同時に成り立たない場合は、矛盾する 2 つの式とその理由を示します。 合同式 x ≡ a (mod n) を 1 行に 1 つずつ入力します。a は余り、n は法です。「式を追加」または最後の法で Enter を押すと行が増え、× で削除できます。200 桁までの整数が使え、a は負でもかまいません。例題を選ぶこともできます。タイルには最小の解と、それが何ごとに繰り返すかが表示され、その下に最初の正の解と各式の検算が並びます。図は各式を満たす数に印をつけ、すべての行に印がある列が解です。余りの表は 2 つの式を同時に表示します。計算過程は、教科書の構成法または代入法で、あなたの数を使って書き出されます。

    使い方

    1. 合同式 x ≡ a (mod n) を 1 行に 1 つずつ入力するか、孫子の問題、卵のかご、ユリウス周期などの例題を選びます。
    2. 最小の解、それが繰り返す法、最初の正の解を読み取ります。どの解もすべての式で検算されています。
    3. 構成法または代入法で計算過程を一歩ずつたどり、図を数直線と余りの表で切り替えます。

    構成法のしくみ

    どの 2 つの法も公約数を持たないとき、解を直接組み立てられます。法を掛け合わせます。孫子の問題では N = 3 × 5 × 7 = 105 です。各式について、ほかのすべての法の倍数である Nᵢ = N / nᵢ をとります。35、21、15 です。次に拡張ユークリッドの互除法で Nᵢ の mod nᵢ での逆元 yᵢ を求めます。35 を 3 で割ると 2 余り、2 × 2 = 4 ≡ 1 (mod 3) なので y₁ = 2、21 と 15 は余りが 1 なので逆元は 1 です。すると x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233、233 mod 105 = 23 となります。各項は自分の式に合い、ほかの法の倍数でもあるので、和はすべての式に合います。

    法が公約数を持つとき

    法が公約数を持つ連立合同式にも解があることがあります。2 つの式 x ≡ a (mod m) と x ≡ b (mod n) が同時に成り立つのは、a − b が gcd(m, n) の倍数であるときに限り、そのとき解は m × n ごとではなく lcm(m, n) ごとに繰り返します。5 分と 11 分に出発し、12 分ごとと 18 分ごとに出るバスは、29 分に出会い、その後 36 分ごとに出会います。11 − 5 = 6 が gcd(12, 18) = 6 の倍数だからです。しかし x ≡ 1 (mod 4) と x ≡ 4 (mod 6) は決して同時に成り立ちません。前者は x を奇数に、後者は偶数にするからです。連立合同式全体に解があるのは、どの 2 つの式の組にも解があるときに限られ、ソルバーはこうして矛盾する 2 つの式を見つけます。

    よくある質問

    中国剰余定理とはどういう定理ですか?

    法 n₁、n₂、… のどの 2 つも公約数を持たなければ、どんな余り a₁、a₂、… に対しても、すべての i について x ≡ aᵢ (mod nᵢ) となる x が 0 から N − 1 の間にちょうど 1 つあります。N は法の積です。ほかの解はすべて、それと N の倍数だけ異なります。孫子の問題の解は 23、128、233、… と 105 ごとに 1 つです。

    なぜ「中国」と呼ばれるのですか?

    この種の問題で知られている最古のものは、3〜5 世紀に書かれた中国の算術書『孫子算経』にあります。3 つずつ、5 つずつ、7 つずつ数えると、ある物の数が 2、3、2 余るという問題です。秦九韶は 1247 年にこうした問題の一般的な解法を示し、カール・フリードリヒ・ガウスは 1801 年に定理を現代の形で述べました。

    法が互いに素でない場合はどうなりますか?

    その場合は解がないこともあり、解があっても法の積ごとではなく最小公倍数ごとに繰り返します。2 つの式は、余りが法の gcd を法として等しいときに矛盾しません。卵の問題は公約数を持つ 2、3、4、5、6、7 を使いますが、それでも解があります。301 で、420 ごとに繰り返します。

    RSA は中国剰余定理をどう使っていますか?

    RSA のメッセージを復号するとは、n = p × q として c^d mod n を計算することです。指数を p − 1 と q − 1 で割った余りに小さくして c^d mod p と c^d mod q を別々に計算し、2 つの結果を定理でまとめるほうが速くなります。数の長さが半分になると 2 回のべき乗はそれぞれ約 8 分の 1 の手間で済むので、復号は約 4 倍速くなり、ほとんどの RSA ソフトウェアはこの方法を使っています。

    どれくらい大きな数を扱えますか?

    式は 20 個まで、数はそれぞれ 200 桁までです。ソルバーはブラウザー内で厳密な整数を使って計算するので、答えがどれほど長くても正確で、データはどこにも送信されません。

    試してみますか?

    ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

    エディターへ