ForHosting KIT · 数学

中国剰余定理計算機

Q: 法は互いに素でなければなりませんか？

はい。 この計算機は互いに素な法を要求し、それにより積を法として一意の解が保証されます。

Q: 負の剰余は使えますか？

はい。 剰余は負でも構いません。法は正の整数でなければなりません。

Q: アルゴリズムは乱数を使いますか？

いいえ。 正確な整数の gcd とモジュラー逆元を用いた決定的な逐次 CRT を使用しています。同じ剰余と法からは常に同じ最小の非負整数解が得られます。

連立合同式を一度に解きます。x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7) の0以上で最小の解は23で、答えは105ごとに繰り返されます。宿題や競技数学、解答例づくりに便利です。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

余り: 2, 3, 2
法: 3, 5, 7

結果

X: 23
絶対値: 105
積: 105
数量: 3

対応する2つの配列をご入力いただくだけで、エンジンが互いに素であることを検証し、正確な整数の最大公約数とモジュラー逆元を用いた逐次 CRT で合同式を畳み込み、0 から積−1 の範囲にある標準代表元を報告します。計算は純粋な整数演算であり、ネットワーク・乱数・時計を一切使わないため、同じ配列からは常に同じ x が得られます。宿題や整数論のデモにはブラウザーで無料でお使いいただけます。

逐次 CRT が解を正確に求める仕組みと活用例

内部では、エンジンは最初の合同式から始めて次の合同式を繰り返しマージします。

部分解 x ≡ x0 (mod m) と、互いに素な m と n を持つ新しい合同式 x ≡ a (mod n) が与えられると、拡張ユークリッド互除法で n を法とする m のモジュラー逆元を求め、それに還元された差 a − x0 を掛け、m 倍したステップで x0 を持ち上げ、m × n を法とする新しい部分解を得ます。

学生は教科書で剰余から数を復元する課題としてこの構成に出会い、教師は不透明な計算機を信用せずに連立合同式ワークシートの解答を生成でき、開発者は同じ契約を使って、互いに素な素因数による CRT で復号を高速化する教育用 RSA デモのモジュラー復元を検証し、整数論ライブラリの決定的なテストベクターを構築します。

このページでは処理はすべてブラウザー内で無料で実行されます。

活用例

宿題やコンテストの連立合同式

x ≡ 2 mod 3、x ≡ 3 mod 5、x ≡ 2 mod 7 のような教科書の連立合同式を解き、法の積とともに最小の非負整数解を得られます。

教育用 RSA とモジュラー復元のデモ

CRT ベースの RSA 高速化、カレンダーパズル、環の同型を説明する際に、互いに素な因数の剰余を一つの整数へ持ち上げられます。

整数論ライブラリ向けの決定的テストフィクスチャー

実装からずれていく手計算の表を埋め込むことなく、単体テストや CI のアサーション用に再現可能な CRT の解を生成できます。

よくある質問

中国剰余定理の計算機の料金はいくらですか？

このページではブラウザーで無料でご利用いただけます。無効な入力は課金されません。

法は互いに素でなければなりませんか？

はい。この計算機は互いに素な法を要求し、それにより積を法として一意の解が保証されます。

負の剰余は使えますか？

はい。剰余は負でも構いません。法は正の整数でなければなりません。

アルゴリズムは乱数を使いますか？

いいえ。正確な整数の gcd とモジュラー逆元を用いた決定的な逐次 CRT を使用しています。同じ剰余と法からは常に同じ最小の非負整数解が得られます。

法の積より小さい答えが1つだけなのはなぜですか？

法が互いに素なとき、中国剰余定理はその積を法として解がただ1つの類になることを保証するからです。例では、ほかの解はすべて23と105の倍数だけ違うので、23が最小です。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/math/chinese-remainder

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/math/chinese-remainder \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"remainders":[2,3,2],"moduli":[3,5,7]}'

const res = await fetch("https://api.kit.forhosting.com/math/chinese-remainder", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "remainders": [
      2,
      3,
      2
    ],
    "moduli": [
      3,
      5,
      7
    ]
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/math/chinese-remainder",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "remainders": [
        2,
        3,
        2
    ],
    "moduli": [
        3,
        5,
        7
    ]
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/chinese-remainder", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"remainders":[2,3,2],"moduli":[3,5,7]}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"remainders":[2,3,2],"moduli":[3,5,7]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/chinese-remainder", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "remainders": [
    2,
    3,
    2
  ],
  "moduli": [
    3,
    5,
    7
  ]
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "math.chinese_remainder",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

制限

max_items 64

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

中国剰余定理の計算機は、法が互いに素である場合に連立合同式（各剰余 a_i に対して法 n_i で x が合同）を解き、最小の非負整数解を法の積とともに返します。どこかの法のペアが共通因数を持つ場合は、推測による答えではなく、明確な invalid_input エラーで失敗します。スクリプトや CI のフィクスチャーで再現可能な答えが必要な場合は、API を成功リクエストごとに $0.002 でご利用いただけます。

中国剰余定理が互いに素な法について保証すること

有名な教室での例、x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7) では x ≡ 23 (mod 105) となり、23 はこのツールが返す最小の非負整数解です。その前提条件が満たされれば、存在と一意性が保証され、答えは常に明確に定義され、マージ処理が共通因数を考慮する必要もありません。互いに素でない法を持つ系は解かずに拒否されるため、契約はシンプルで誠実に保たれます。古典的な中国剰余定理によれば、法 n_1 から n_k が互いに素（どのペアも1より大きい共通因数を持たない）であるとき、すべての合同式 x ≡ a_i (mod n_i) を同時に満たす剰余類が、すべての n_i の積を法としてちょうど一つ存在します。成功時の JSON レスポンスには x、法（ここでは入力した法の積に等しい）、積そのもの、0 から n_i−1 の標準区間に還元された剰余、法のコピー、合同式の数が含まれます。

入力の検証方法と、互いに素でない法が拒否される理由

分数、指数表記、途中の空白は拒否されます。すべての法は正の安全整数でなければならず、剰余は負でも構いませんがマージ前に標準区間へ還元されます。求解の前に、エンジンはユークリッドの互除法による gcd ですべての法のペアを検査します。共通因数を持つ一般的な CRT 系は矛盾することがあり、意味を黙って切り替えるよりも、この計算機は「互いに素な入力、最小の非負整数解を出力」という一つの約束を守ります。受け付けるフィールドは remainders と moduli で、同じ長さの整数の JSON 配列2つです。エイリアス a、ai、residues は remainders に、n、ni、mods は moduli にマッピングされるため、フォーム、クエリ文字列、レガシーノートブックが同一の契約を共有できます。各要素は JSON 整数、または先頭に符号を付けられる10進文字列です。1回のリクエストで受け付ける合同式は最大64個です。どこかのペアの gcd が1より大きい場合、リクエストは invalid_input で失敗し、問題のペアを示すメッセージ（例：gcd(4, 6) = 2）が返されます。これは数学の限界ではなく意図的な設計上の選択です。配列の欠落、長さの不一致、整数でない要素、安全整数の範囲を超える積も invalid_input で失敗するため、スプレッドシートの誤ったセルが静かに間違った答えになることはありません。

逐次 CRT が解を正確に求める仕組みと活用例

API 経由では成功した求解ごとに $0.002 がかかり、検証失敗は課金されず、レスポンス返却後は何も保存されません。

技術的な質問

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

異なる意味論で答えを推測するのではなく、「Moduli are not pairwise coprime: gcd(4, 6) = 2」のようなメッセージとともに invalid_input で失敗します。

KITの完全なドキュメントを見る →

中国剰余定理計算機

無料で実行

計算例

逐次 CRT が解を正確に求める仕組みと活用例

活用例

宿題やコンテストの連立合同式

教育用 RSA とモジュラー復元のデモ

整数論ライブラリ向けの決定的テストフィクスチャー

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

中国剰余定理が互いに素な法について保証すること

入力の検証方法と、互いに素でない法が拒否される理由

逐次 CRT が解を正確に求める仕組みと活用例

技術的な質問

ありがとう