乗法逆元 modulo n
nを法とする掛け算を打ち消す数を求めます。11を法とする3の逆元は4で、3 × 4 = 12を11で割ると余りが1になるためです。逆元があるのは、整数と法が共通の約数を持たないときだけです。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 整数
- 3
- 絶対値
- 11
- 剰余
- 3
- 逆関数
- 4
- Gcd
- 1
- 検算
- 1
整数の法 n における乗法逆元とは、整数と inverse の積が法 n で 1 と合同になる剰余 inverse のことです。この逆元は、整数と法が互いに素であるとき、つまり最大公約数が 1 のときに限り存在します。暗号の教材、RSA の秘密鍵手順、競技プログラミングでのモジュラ除算、巡回群の計算などはこの演算を必要としますが、多くの言語は二進 GCD だけを公開し、Bézout 係数は呼び出し側に任せます。手順をやり直さなくても結果を確認できます。
乗法逆元 modulo n とは何か、いつ存在するか
通常の算術では 0 以外の数はすべて乗法逆元を持ち、それで割ると 1 になります。モジュラ算術では同じ考えが合同式になります。整数と inverse の積を法で割った余りが 1 のとき、inverse をその整数の法 n における乗法逆元と呼びます。
剰余は n ごとに周るため、すべての整数にそのような inverse があるわけではありません。障害は浮動小数ではなく数論的です。d を整数と法の gcd とし d が 1 より大きいと、整数と任意の候補の積は d の倍数になり、d の倍数でない 1 とは決して合同になりません。
逆に Bézout の恒等式は、その gcd が 1 のときちょうど整数×x＋法×y＝1 となる整数 x, y を保証し、x を法 n で還元すると inverse が得られます。
有限環での除算、公開指数を N の phi の法で逆にする RSA 復号指数の選択、ハッシュ処理でのモジュラ乗算の取り消し、競技プログラミングでの一次合同式の解法などで、技術者はこの条件に出会います。互いに素でない対に明示的なエラーを返す方が黙った失敗より有用です。
クライアントは inverse が存在しないと分かり、どのライブラリが誤った剰余を返したかを推測する代わりに gcd で分岐できます。本計算機は互いに素でない対を無効入力として扱い、後の合同検査を壊す仮の inverse は返しません。
本計算機が拡張ユークリッド法をどう実行するか
実装はまず整数を 0 から n−1 の非負剰余類 residue に還元し、residue と modulus の対に拡張ユークリッド法を適用します。各段で整数商を記録し Bézout 係数を更新し、終了時に residue の係数 × residue ＋ 法の係数 ＝ gcd となります。
gcd が 1 なら residue の係数を 0 から n−1 に還元して inverse として返します。絶対値は 1 兆で上限し、モジュラ積の中間倍加が JavaScript の安全整数範囲内に収まるようにします。負の整数は受け付け、ユークリッドループの前に還元します。
マイナス 3 を法 11 で入れると residue 8 として扱い、その類で逆元を求めます。
実用、制限、料金、提供形態
暗号のメモを読むとき、宿題の合同式を確かめるとき、モジュラ乗算の手順をデバッグするときに素早く inverse が欲しければブラウザツールを使ってください。検証失敗と互いに素でない対は残高を消費しません。受け付ける入力は絶対値が最大 1 兆の整数と、2 から 1 兆までの法です。
結果は決定的で、同じ対は常に同じ inverse と check を返します。対を公開範囲内に保ち、互いに素でないエラーをテストの第一級結果として扱い、宿題、LMS プラグイン、エッジワーカー向けに再現可能な inverse を、自前の数式処理系なしで得られます。
活用例
暗号と RSA の教材ラボ
教員と学生は公開指数を φ(N) の法でその場で逆にし、サンプル法が指数と互いに素でないときの gcd を確認できます。
競技プログラミングとモジュラ除算
競技プログラマーは素数・合成数の法でのモジュラ除算を検証する際、場当たり的な拡張 GCD 断片を 1 回の決定的呼び出しに置き換えられます。
よくある質問
どの手順で逆元を求めますか？
拡張ユークリッド法です。還元済み residue と法の Bézout 係数を求め、gcd が 1 のとき residue の係数を 0..n−1 に還元します。
整数と法に共通の約数があるとどうなりますか？
その場合は逆元が存在しません。計算ツールは2つの数と最大公約数を示すメッセージで知らせ、合同式を満たさない値を作り出すことはしません。
逆元が正しいかどうか確かめるには？
nを法として整えた整数に逆元を掛け、nで割った余りが1になるかを見ます。この確認は、整えた整数や最大公約数と一緒に結果の横に表示されます。
どんな数を入力できますか？
絶対値が1兆までの整数で、負の数も使えます。法は2以上です。整数はまず0からn−1までの余りに直され、逆元もその範囲で返ります。
nを法とする逆元はどんな場面で使いますか？
RSA暗号の鍵を求める手順の学習、剰余の世界での割り算、巡回群の計算などで必要になります。数学の授業や問題演習での答え合わせにも役立ちます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/math/multiplicative-inverse-modulo \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"integer":3,"modulus":11}'const res = await fetch("https://api.kit.forhosting.com/math/multiplicative-inverse-modulo", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"integer": 3,
"modulus": 11
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/multiplicative-inverse-modulo",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"integer": 3,
"modulus": 11
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/multiplicative-inverse-modulo", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"integer":3,"modulus":11}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"integer":3,"modulus":11}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/multiplicative-inverse-modulo", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"integer": 3,
"modulus": 11
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.multiplicative_inverse_modulo",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_abs | 1000000000000 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
本計算機は integer と modulus を受け取り、拡張ユークリッド法を決定的に実行し、0 から n−1 の範囲の一意な非負 inverse と、還元済み residue、gcd、検算用の check 積を返します。
本計算機が拡張ユークリッド法をどう実行するか
整数フィールド integer と modulus（modulus は 2 以上）で capability を呼び出します。その gcd が 1 でなければ、両方の入力と gcd を示すメッセージ付きで invalid_input により失敗し、課金されません。応答は integer, modulus, residue, gcd、および residue × inverse mod n に等しい check（成功時は 1）も返します。同じ純粋関数が無料のブラウザツールと API 経路を支えます。
実用、制限、料金、提供形態
スクリプト、採点器、教育プラットフォームが拡張 GCD ルーチンを埋め込まずに多数の逆元を必要とするときは API を使います。成功した各要求は $0.002 の請求単位 1 件です。RSA 教材のサンドボックス、有限環デモ、競技プログラミング補助、近似ヒューリスティックより厳密算術を好む整数パイプラインに endpoint を接続できます。単位は 1 件でエンジンは純粋な parse のため遅延は低く、無料 Web 経路は有料 API を第二のコード経路なしで反映します。
連携の活用例
宿題チェッカーと数論パイプライン
自動採点器とスクリプトは逆元を確認し、invalid_input で互いに素でない入力を検出し、中間積を文書化された範囲内に保てます。
技術的な質問
整数の法 n における乗法逆元をこの API でどう求めますか？
整数フィールド integer と modulus（modulus ≥ 2）の JSON を送ってください。成功時は 0..n−1 の inverse と residue、gcd、1 に等しい check が返ります。
整数と法が互いに素でないと API はどう応答しますか？
要求は invalid_input で失敗します。メッセージに gcd(integer, modulus) が含まれ、乗法逆元が存在しない理由が分かります。検証失敗は課金されません。
乗法逆元 modulo n の計算は無料ですか？
ブラウザ上の widget はお使いの端末で無料です。API 呼び出しは成功 1 件あたり $0.002 の前払い KIT 残高を使います。無効な integer や modulus、互いに素でない対は課金されません。
integer と modulus のどの範囲が受け付けられますか？
integer は絶対値が最大 1 兆の任意の有限整数です。modulus は 2 から 1 兆までの整数でなければなりません。整数でない値は拒否されます。