ForHosting KIT · 数学

モジュラ乗法逆元

mを法とする掛け算を打ち消す数を求めます。11を法とした3の逆元は4で、3×4を11で割ると余りは1になります。最大公約数と検算値も表示し、逆元がない場合ははっきり知らせます。ブラウザで無料で使えます。

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

無料で実行 API仕様を見る

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

計算例

入力した場合

A: 3
法 m ≥ 2: 11

結果

A の剰余: 3
逆元: 4
最大公約数: 1
検算: 1

整数 a の法 m におけるモジュラ乗法逆元とは、a と x の積が法 m で 1 と合同になる剰余 x のことです。この逆元は、a と m が互いに素であるとき、つまり最大公約数が 1 のときに限り存在します。暗号の教材、RSA の秘密鍵手順、競技プログラミングでのモジュラ除算、巡回群の計算などはこの演算を必要としますが、多くの言語は二進 GCD だけを公開し、Bézout 係数は呼び出し側に任せます。本計算機は a と m を受け取り、拡張ユークリッド法を決定的に実行し、0 から m−1 の範囲の一意な非負逆元と、gcd および検算用の積を返します。手順をやり直さなくても結果を確認できます。

モジュラ逆元とは何か、いつ存在するか

通常の算術では 0 以外の数はすべて乗法逆元を持ち、それで割ると 1 になります。モジュラ算術では同じ考えが合同式になります。a と x の積を m で割った余りが 1 のとき、x を a の法 m におけるモジュラ逆元と呼びます。

剰余は m ごとに周るため、すべての a にそのような x があるわけではありません。障害は浮動小数ではなく数論的です。d を a と m の gcd とし d が 1 より大きいと、a と任意の整数の積は d の倍数になり、d の倍数でない 1 とは決して合同になりません。

有限体での除算、公開指数を n の phi の法で逆にする RSA 復号指数の選択、ハッシュ処理でのモジュラ乗算の取り消し、競技プログラミングでの一次合同式の解法などで、技術者はこの条件に出会います。互いに素でない対に明示的なエラーを返す方が黙った失敗より有用です。

クライアントは逆元が存在しないと分かり、どのライブラリが誤った剰余を返したかを推測する代わりに gcd で分岐できます。

実用、制限、料金、提供形態

暗号のメモを読むとき、宿題の合同式を確かめるとき、モジュラ乗算の手順をデバッグするときに素早く逆元が欲しければブラウザツールを使ってください。検証失敗と互いに素でない対は残高を消費しません。受け付ける入力は絶対値が最大 1 兆の整数 a と、2 から 1 兆までの法 m です。

結果は決定的で、同じ対は常に同じ逆元と check を返します。

活用例

暗号と RSA の教材ラボ

教員と学生は公開指数を φ(n) の法でその場で逆にし、サンプル法が指数と互いに素でないときの gcd を確認できます。

競技プログラミングとモジュラ除算

競技プログラマーは素数・合成数の法でのモジュラ除算を検証する際、場当たり的な拡張 GCD 断片を 1 回の決定的呼び出しに置き換えられます。

よくある質問

a と m が互いに素でないとどうなりますか？

メッセージに gcd(a, m) が含まれ、乗法逆元が存在しない理由が分かります。検証失敗は課金されません。

どのアルゴリズムが逆元を計算しますか？

拡張ユークリッド法です。a mod m と m の Bézout 係数を求め、gcd が 1 のとき a の係数を 0..m−1 に還元します。

モジュラ逆元計算機は無料ですか？

ブラウザツールはお使いの端末で無料です。無効または互いに素でない入力は課金されません。

a と m のどの範囲が受け付けられますか？

m は 2 から 1,000,000,000,000 の整数でなければなりません。a は絶対値がその同じ上限以下の整数です。範囲外は拒否されます。

11を法とした3の逆元はいくつですか？

4です。3に4を掛けて11で割ると余りが1になり、これがまさに逆元の条件です。結果の横に表示される検算値がこの1です。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/modular-inverse

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

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

curl -X POST https://api.kit.forhosting.com/numth/modular-inverse \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":3,"m":11}'

const res = await fetch("https://api.kit.forhosting.com/numth/modular-inverse", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 3,
    "m": 11
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/modular-inverse",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 3,
    "m": 11
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/modular-inverse", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"a":3,"m":11}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"a":3,"m":11}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/modular-inverse", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "a": 3,
  "m": 11
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

max_abs 1000000000000

エラー

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

技術的な注記

モジュラ逆元とは何か、いつ存在するか

逆に Bézout の恒等式は、その gcd が 1 のときちょうど a x + m y = 1 となる整数 x, y を保証し、x を法 m で還元すると逆元が得られます。

本計算機が拡張ユークリッド法をどう実行するか

絶対値は 1 兆で上限し、中間積が JavaScript の安全整数範囲内に収まるようにします。整数フィールド a と m（m は 2 以上）で capability を呼び出します。実装はまず a を 0 から m−1 の非負剰余類 a_mod に還元し、a_mod と m の対に拡張ユークリッド法を適用します。各段で整数商を記録し Bézout 係数を更新し、終了時に a_mod の係数 × a_mod + m の係数 = gcd となります。その gcd が 1 でなければ、両方の入力と gcd を示すメッセージ付きで invalid_input により失敗し、課金されません。gcd が 1 なら a_mod の係数を 0 から m−1 に還元して inverse として返します。応答は a, m, a_mod, gcd、および a_mod × inverse mod m に等しい check（成功時は 1）も返します。同じ純粋関数が無料のブラウザツールと API 経路を支えます。

実用、制限、料金、提供形態

スクリプト、採点器、教育プラットフォームが拡張 GCD ルーチンを埋め込まずに多数の逆元を必要とするときは API を使います。成功した各要求は $0.002 の請求単位 1 件です。RSA 教材のサンドボックス、有限体デモ、競技プログラミング補助、近似ヒューリスティックより厳密算術を好む整数パイプラインに endpoint を接続できます。単位は 1 件でエンジンは純粋な parse のため遅延は低く、無料 Web 経路は有料 API を第二のコード経路なしで反映します。

連携の活用例

宿題チェッカーと数論パイプライン

自動採点器とスクリプトは逆元を確認し、invalid_input で互いに素でない入力を検出し、中間積を文書化された範囲内に保てます。

技術的な質問

この API でモジュラ逆元をどう計算しますか？

整数フィールド a と m（m ≥ 2）の JSON を numth.modular_inverse に送ってください。成功時は 0..m−1 の inverse と a_mod、gcd、1 に等しい check が返ります。

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

モジュラ乗法逆元

無料で実行

計算例

モジュラ逆元とは何か、いつ存在するか

実用、制限、料金、提供形態

活用例

暗号と RSA の教材ラボ

競技プログラミングとモジュラ除算

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

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

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

モジュラ逆元とは何か、いつ存在するか

本計算機が拡張ユークリッド法をどう実行するか

実用、制限、料金、提供形態

連携の活用例

宿題チェッカーと数論パイプライン

技術的な質問

ありがとう