拡張ユークリッド：最大公約数とベズー係数 x, y
240と46の最大公約数は2で、240 × (−9) + 46 × 47 = 2となります。2つの整数を入れると、最大公約数、2つのベズー係数、それを示す等式が分かります。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 第一の整数
- 240
- 第二の整数
- 46
- 最大公約数
- 2
- X
- -9
- Y
- 47
- 検証
- 2
拡張ユークリッド互除法は、二つの整数の最大公約数を報告するだけでなく、a に x を掛け b に y を掛けた和がその最大公約数になるベズー係数 x と y も求めます。これらの係数は、最大公約数が1のときの合同逆元、線形ディオファントス方程式の構成的証明、余りだけでなく明示的な結合が必要な暗号の演習に現れます。
余りからベズー係数へ
通常のユークリッド除法は対 (a, b) を (b, a mod b) で繰り返し置き換え、余りが零になるまで続けます。最後の非零余りが gcd(a, b) です。拡張形は、各余りが元の入力の整数線形結合としてどう書かれるかを追跡します。
各段階で現在の余りは a にある係数を掛け b に別の係数を掛けた和に等しく、アルゴリズムが止まるとその係数が最大公約数のベズー数そのものになります。授業では商列からの後退代入がよく使われ、本番コードでは余りスタックを保存せず二つの係数対を反復更新することが多いです。どちらも同じ数学的対象を計算します。
a*x + b*y = gcd(a, b) を満たす整数 x と y です。最大公約数自体は常に非負整数として返され、ライブラリやコンテスト問題の標準慣習と一致します。
送信するものと返ってくるもの
零と零の対も拒否されます。gcd(0, 0) は未定義で、意味のある方程式を作る係数が存在しないためです。成功時の応答には正規化済みの a と b、gcd、x、y、同じ係数を持つ入れ子の bezout オブジェクト、a*x + b*y に等しい数値 check、および 240*(-9) + 46*(47) = 2 のような方程式文字列が含まれます。
典型的な確認：240 と 46 では gcd は 2、有効な解の一つは x がマイナス九、y が四十七；gcd が1の素数対では x を法 b で還元すると a の合同逆元が得られます。一方が零で他方が非零の境界では、gcd は非零入力の絶対値、係数パターンは自明になります。
実務でベズー係数が現れる場面
競技プログラマはまず gcd と基本係数を計算し、gcd が c を割るときに一般解を拡大・パラメータ化して ax + by = c を解きます。暗号の学習者は gcd(a, m)=1 のとき a の係数を法 m で読んで RSA 玩具例やアフィン暗号の合同逆元を得ます。
教員は二つの整数が互いに素であることの構成的証明を課し、真偽ビットだけでなく結合を示す決定的オラクルを必要とします。データとシステム技術者は周期スケジュールやストライド算術の調整で明示的な線形結合が必要なことがあります。宿題の素早い確認にはブラウザツールを使い、一括ディオファントス検査が必要なら同じ契約を自動化してください。
係数なしの素の gcd だけが必要でも、本ページはその需要に答えつつより強い構成的結果を教えます。
活用例
線形ディオファントス方程式
a*x + b*y = gcd の特解 (x, y) を得てから、コンテストや宿題で a*x + b*y = c を解く際に拡大とパラメータ化を行います。
合同逆元の構成ブロック
gcd(a, m) = 1 のとき、a のベズー係数を法 m で還元し、暗号や数論の演習用の合同逆元を得ます。
よくある質問
拡張ユークリッド互除法とは何ですか？
gcd(a, b) と、a*x + b*y がその gcd に等しくなる整数 x, y（ベズー係数）を、ユークリッドの余り手順を通じて線形結合を追跡して計算します。
係数は一意ですか？
いいえ。( x, y) が使えるなら任意の整数 k について (x + k*(b/g), y − k*(a/g)) も使えます。本ツールは反復アルゴリズムの一つの特解を返します。
対応する整数範囲は？
a と b はそれぞれ絶対値が最大 9007199254740991（Number.MAX_SAFE_INTEGER）の整数である必要があります。
240と46のベズー係数はどう求めますか？
2つの数を入れます。最大公約数は2で、係数は−9と47です。240 × (−9) + 46 × 47 = 2となり、結果にこの等式も表示されるので確かめられます。
結果から合同式の逆元を求めるには？
最大公約数が1のとき、最初の数の係数を2番目の数で割った余りに直すと、それが最初の数の逆元になります。RSAの例題やアフィン暗号でよく使う方法です。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/extended-euclidean \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":240,"b":46}'const res = await fetch("https://api.kit.forhosting.com/numth/extended-euclidean", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 240,
"b": 46
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/extended-euclidean",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 240,
"b": 46
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/extended-euclidean", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":240,"b":46}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":240,"b":46}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/extended-euclidean", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"a": 240,
"b": 46
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.extended_euclidean",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_abs | 9007199254740991 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
本能力は二つの整数を受け取り、両方が零という未定義の場合を拒否し、gcd、x、y、検証値、ノートやテストに貼れる可読な方程式文字列を含む安定した JSON を返します。
余りからベズー係数へ
本エンドポイントは絶対値上で反復路を実装し、負の入力でも恒等式が成り立つよう符号を戻します。
送信するものと返ってくるもの
整数 a と b を指定してください（a には first または m、b には second または n の別名を受け付けます）。非整数、空欄、プラットフォームの安全整数絶対最大を超える値は invalid_input で拒否され課金されません。
実務でベズー係数が現れる場面
能力が純粋な parse エンジンであるため、モデルのずれ、ネットワーク依存、保存状態はなく、係数の慣例を固定すれば同じ対は常に同じ JSON を返します。API 料金は成功項目あたり公開ベース $0.002 で、検証失敗は残高を消費しません。
連携の活用例
教育と自動チェック
安定した JSON の方程式フィールドで a*x + b*y = gcd を学生に示し、同じ契約を採点器や CI フィクスチャに接続します。
技術的な質問
なぜ a と b の両方が零だと拒否されますか？
gcd(0, 0) は未定義です。正の最大公約数が存在しないため、API は invalid_input を返し課金しません。
費用はいくらですか？
ブラウザツールは無料でローカル実行です。API リクエストは成功項目あたり $0.002 の前払い KIT 残高を使い、無効な入力は課金されません。