中国剰余定理ソルバー
連立合同式をまとめて解けます。x ≡ 2 mod 3、x ≡ 3 mod 5、x ≡ 2 mod 7 なら答えは x ≡ 23 mod 105 です。共通の約数を持つ法にも対応し、矛盾する場合はそう知らせます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 剰余
- 2, 3, 2
- 法
- 3, 5, 7
- X
- 23
- 法
- 105
- 積
- 105
- 数量
- 3
宿題やコンテストの練習、法算術のデモにはブラウザで無料でご覧ください。
剰余と法の読み取り方と逐次CRTの正確さの保ち方
分数、指数表記、埋め込まれた空白は拒否されます。すべての法は正の安全な整数でなければなりません。剰余は負でもかまわず、統合前に正規の区間に整理されます。
内部では、エンジンは最初の合同式から始めて次を繰り返し統合します:x ≡ x0 mod mとx ≡ a mod nが与えられると、mとnのgcdであるgを計算し、a引くx0がgで割り切れなければ系を拒否し、そうでなければm/g のn/gを法とする逆元で更新された解を組み立て、法にn/gを掛けて新しいlcmを得ます。
すべての乗算は保護されているため、積と中間のCRTの法はJavaScriptの安全な整数の範囲内に収まります。過大な積は、包み直すのではなく明確に失敗します。
CRTの系が学習・暗号の直感・コードで果たす役割
学生は、教科書が剰余から数を再構成させるとき、互いに素な法の積を法とするZが環の積と同型であることを証明するとき、そして3・5・7が混在する周期のカレンダーやスケジューリングのパズルを解くときに中国剰余定理に出会います。教師は、中間のgcdを隠す不透明な電卓を信用せずに、連立合同式のワークシートの解答例を生成できます。
開発者は、同じ契約を使って教育用RSAデモの法の再構成を検証したり、法算術ライブラリの決定的なテストベクトルを構築したり、スキーマ変更後も剰余のパイプラインが単一の類に持ち上がるかを確認したりします。コンテストの練習では、手書きの作業を数秒で確認できるよう、高速なオフラインソルバーがよく必要とされます。
2つの整数のgcdだけが必要な場合は互いに素チェッカーと、連立系ではなく単一の法の背後にある素数べきが必要な場合は素因数分解と組み合わせてください。
活用例
宿題とコンテストの連立合同式
x ≡ 2 mod 3、x ≡ 3 mod 5、x ≡ 2 mod 7のような教科書の系を解き、法の積を法とする一意の類を検証します。
教育デモでの法の再構成
環の同型、カレンダーパズル、教育用RSA風のCRTのステップを説明する際に、剰余のリストを単一の整数の類に戻します。
法算術ライブラリ向けの決定的なテストフィクスチャ
実装とずれる手計算の表を埋め込まずに、単体テストとCIアサーション向けに再現性のあるCRTの解を生成します。
よくある質問
法は互いに素なペアである必要がありますか?
いいえ。 互いに素なペアの法は常にその積を法とする一意の解を生みます。互いに素でない法も、剰余が各gcdを法として一致すれば受け付けられます。そうでなければ系は不整合として拒否されます。
負の剰余は許可されますか?
はい。 剰余は負でもかまいません。法は正の整数でなければなりません。
このアルゴリズムはランダム化されていますか?
いいえ。 正確な整数のgcdと法の逆元を用いた決定的な逐次CRTを使います。同じ剰余と法は常に同じxと法を返します。
x ≡ 2 mod 3、x ≡ 3 mod 5、x ≡ 2 mod 7 はどう解きますか？
余り2、3、2と法3、5、7を同じ順番で入力すると、答えは23です。23に105の倍数を足したり引いたりした数も、すべて条件を満たします。
合同式どうしが矛盾しているとどうなりますか？
答えをでっち上げず、連立式が矛盾していると知らせます。解があるのは、どの2つの余りも、対応する2つの法の最大公約数を法として合同なときだけです。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/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/numth/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/numth/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/numth/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/numth/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": "numth.chinese_remainder",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
中国剰余定理ソルバーは、連立合同式(各法n_iに関して各剰余a_iに合同なx)の系を受け取り、解が存在する場合は一意の解の類を返します。剰余と法の並列な配列を指定すると、エンジンは逐次的なCRTでそれらを畳み込み、法が公約数を共有する場合は整合性を確認し、0から法-1の範囲の代表元xと解の類の法(法が互いに素なペアのときはn_iの積、そうでなければそれらの最小公倍数)の両方を報告します。この経路は純粋な整数算術です:通信もランダム性も時計もありません。採点スクリプトや暗号の教育ツール、再現性のあるCRTの回答が必要なCIフィクスチャの場合は、成功したリクエストごとに$0.002のAPIをご利用ください。
中国剰余定理は何を返し、いつ系は失敗するか
有名な授業の3つ組であるx ≡ 2 mod 3、x ≡ 3 mod 5、x ≡ 2 mod 7はx ≡ 23 mod 105を生みます。このツールは一般的な形式も受け付けます:法は互いに素なペアである必要はありません。古典的には、法が互いに素なペアであれば、すべての合同式を同時に満たす、n_iの積を法とする剰余類がちょうど1つ存在します。その場合、解が存在するための必要十分条件は、対応する法の最大公約数を法として、剰余の各ペアが一致することであり、解はすべてのn_iの最小公倍数を法として一意です。剰余が一致しない場合、リクエストは、偽のxを作り出すのではなく不整合を名指しするメッセージとともにinvalid_inputで失敗します。成功時のJSONレスポンスにはx、modulus(解の類のCRTの法)、product(入力した法の生の積)、0からn_i-1に整理されたremainders、moduliのコピー、countが含まれます。配列の欠落、長さの不一致、正でない法、非整数、安全な整数範囲外の値もinvalid_inputで失敗するため、不正なスプレッドシートのセルが黙って誤った答えになることはありません。
剰余と法の読み取り方と逐次CRTの正確さの保ち方
優先されるフィールドは、整数の等しい長さのJSON配列としてのremaindersとmoduliです。エイリアスa、ai、residuesはremaindersに、n、ni、modsはmoduliに対応するため、フォームやクエリ文字列、レガシーなノートブックでも1つの契約を再利用できます。各要素は先頭の任意の符号付きJSON整数、または10進文字列でかまいません。この再現性が、無料のブラウザ経路をAPI経路とビット単位で同一にし、CIフィクスチャの正しさを保ちます。
CRTの系が学習・暗号の直感・コードで果たす役割
このページでは処理はすべてブラウザ内で完結し、API経由では成功した解決1件ごとに$0.002かかり、検証に失敗した場合は課金されず、レスポンスを返した後は何も保存されません。
技術的な質問
中国剰余定理ソルバーの料金は?
このページのブラウザ上では無料です。API経由では成功したリクエストごとに$0.002かかり、無効な入力には課金されません。
系が不整合な場合はどうなりますか?
リクエストは、法のgcdを法として剰余が一致しないため系全体を満たす整数xが存在しないというメッセージとともにinvalid_inputで失敗します。