ForHosting KIT · 数学

モジュラ除算

合同算術での割り算を行います。11を法として8÷3は10です。3の逆元は4で、3×10を11で割ると余りは8になります。逆元、最大公約数、検算用の値も表示します。ブラウザで無料で使えます。

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

無料で実行 API仕様を見る

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

計算例

入力した場合

A: 8
B: 3
N: 11

結果

A の法: 8
Bの剰余: 3
逆関数: 4
商: 10

モジュラ除算は、b と q の積が a と n を法として合同になるような剰余 q を求めます。通常の算術では単に割りますが、モジュラ算術では除算は除数のモジュラ逆元による乗算です。その逆元は b と n が互いに素であるときに限り存在します。暗号の演習、競技プログラミング、有限体の課題、線形合同式の練習はいずれもこの演算を必要としますが、多くの言語は GCD や裸のモジュラ逆元だけを公開し、乗算の段を利用者に委ねます。本計算機は整数 a・b と法 n を受け取り、可能なら拡張ユークリッド法で b を n を法として逆元化し、a を掛け、0 から n−1 までの一意な非負商を、逆元・gcd・検証用積とともに返します。手順を再導出せずに結果を確認できます。

モジュラ除算の意味と定義される条件

整数では零以外の数は有理数に逆数を持ち、零を除けば除算は常に定義されます。法 n では状況が厳しく、剰余は環をなし、乗法逆元を持つ単位元だけが合法な除数になります。q が a を b で n を法として割ったモジュラ商であるとは、両方の積を n で剰余化したとき b と q の積が a と同じ余りを残すことをいいます。

同値に、q は a に b の逆元を掛けたものと n を法として合同です。b の逆元は gcd(b, n) が 1 のときだけ存在します。そうでなければ b の任意の倍数は n と共通因子を持ち、すべての剰余類に届かないため、任意の a に対する一意な q は存在しません。

合成法の非素体で割ろうとするとき、線形合同式の係数を約すとき、ハッシュや暗号の段でモジュラ乗算を戻すとき、技術者や学生はこの障壁に直面します。クライアントは除算が未定義だと分かり、不完全なライブラリを信じる代わりに報告された gcd で分岐できます。なお a 自体は n と互いに素である必要はなく、除数 b だけが単位であれば足ります。

a が 1 のモジュラ逆元の特殊例だけを覚えていると、この非対称性は忘れやすいです。

実務での使い方、制限、料金、配信

数論のノートを読みながら素早くモジュラ商が欲しいとき、b x ≡ a (mod n) 形の宿題を確認するとき、手で逆元を掛けているモジュラ処理をデバッグするときはブラウザツールを使ってください。検証失敗や可逆でない除数は残高を消費しません。受け付ける入力は絶対値が最大 1 兆の整数 a・b と、2 から 1 兆までの法 n です。

結果は決定的で、同じ三つ組は常に同じ quotient・inverse・check を返します。a を掛けず b の逆元だけが必要な場合は専用のモジュラ逆元能力を選び、本ページは「モジュラ除算」や「a を b で mod n」と検索される完全な除算意図を対象とします。

活用例

暗号・有限体の教材ラボ

教員と学生は素数を法とする体要素の除算を行い、合成法の例で除数が可逆でなくなるとき gcd を確認できます。

宿題チェッカーと線形合同式

自動採点は返却された商を比較して b x ≡ a (mod n) の解を検証し、一意な剰余類が存在しない場合を拒否できます。

よくある質問

b が n を法として可逆でない場合はどうなりますか？

メッセージに gcd(b, n) が含まれ、モジュラ除算が未定義である理由が分かります。検証失敗は課金されません。

商はどのように計算されますか？

拡張ユークリッド法が gcd(b, n) = 1 のとき b⁻¹ mod n を求め、計算機はその逆元に a を n を法として厳密な整数演算で掛けます。

a・b・n の受理範囲は？

n は 2 から 1,000,000,000,000 の整数である必要があります。a と b は絶対値がその上限以下の整数でなければなりません。範囲外は拒否されます。

11を法として8÷3はいくつですか？

答えは10です。11を法とした3の逆元は4で、8にこれを掛けると商10になります。検算として、3×10を11で割った余りは8です。

aもnと互いに素である必要がありますか？

いいえ。nを法として逆元を持つ必要があるのは割る数bだけで、bとnの最大公約数が1であれば足ります。割られる数aはnと共通の約数を持っていても構いません。

開発者向け — APIアクセス

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

エンドポイント

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

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

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

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

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

import os, requests

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

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

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

リクエスト例

{
  "a": 8,
  "b": 3,
  "n": 11
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

エラー

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

技術的な注記

モジュラ除算の意味と定義される条件

b が可逆でないときに明示的な invalid_input を返す方が、黙って誤った剰余を返すより有用です。

本計算機が b を逆元化し a を掛ける手順

整数フィールド a・b・n（n は 2 以上）で能力を呼び出します。実装はまず a と b を 0 から n−1 の非負剰余 a_mod・b_mod に還元し、続けて b_mod と n に拡張ユークリッド法を適用します。各段は整数商を記録しベズー係数を更新し、終了時に b_mod の係数と b_mod の積に n の係数を加えたものが gcd と等しくなります。gcd が 1 でなければ要求は invalid_input で失敗し、メッセージは b・n・gcd を示します。課金はされません。 gcd が 1 なら b_mod の係数を 0 から n−1 に還元して inverse として保存します。a_mod と inverse のモジュラ積は公開上限まで大きな剰余が正確に保たれるよう厳密な BigInt 演算で求め、quotient として返します。応答は a・b・n・a_mod・b_mod・gcd、および b_mod と quotient の n を法とする積である check も返し、成功時 check は a_mod と一致します。a と b の絶対値および法 n は 1 兆を上限とし、中間値は Worker の安全な整数範囲に収まります。

実務での使い方、制限、料金、配信

拡張 GCD と慎重な multiply-mod を埋め込まずに多数の除算が必要なスクリプト・採点器・教育基盤では API を使ってください。成功した要求は 1 件あたり $0.002 の課金単位です。競技用ヘルパー、有限体デモ、裸の逆元以上を要する RSA 教材、浮動小数のヒューリスティクスより厳密算術を好む整数パイプラインにエンドポイントを接続できます。単位は 1 件でエンジンは純粋 parse のため遅延は低く、無料 Web 経路は有料 API を第二のコード経路なしで反映します。

連携の活用例

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

競技プログラマーは素数法・合成法の下で a/b mod n を計算し、拡張 GCD の場当たりスニペットの代わりに invalid_input で可逆でない除数を検出できます。

技術的な質問

モジュラ除算 a ÷ b mod n はどのように計算しますか？

整数フィールド a・b・n（n ≥ 2）の JSON を numth.modular_division に送ってください。成功時は 0..n−1 の quotient、b の逆元、a_mod、b_mod、gcd、a_mod に等しい check が返ります。

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

ブラウザツールはお使いの端末で無料です。API 呼び出しは成功 1 件あたり $0.002 の前払い KIT 残高を使い、無効または可逆でない入力は課金されません。

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

モジュラ除算

無料で実行

計算例

モジュラ除算の意味と定義される条件

実務での使い方、制限、料金、配信

活用例

暗号・有限体の教材ラボ

宿題チェッカーと線形合同式

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

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

リクエスト例

レスポンス例

料金

エラー

技術的な注記

モジュラ除算の意味と定義される条件

本計算機が b を逆元化し a を掛ける手順

実務での使い方、制限、料金、配信

連携の活用例

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

技術的な質問

ありがとう