ForHosting KIT · 数学

ユークリッド互除法

Q: 負の数を渡せますか？

はい。 最大公約数は絶対値で計算されるため、gcd(-1071, 462) は gcd(1071, 462) と同じ結果を返します。

1071と462の最大公約数は21で、1071 = 462 × 2 + 147、462 = 147 × 3 + 21と割り算を3回行うと余りが0になります。2つの整数を入力すれば、答えだけでなく途中の手順もすべて分かります。ブラウザで無料で使えます。

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

無料で実行 API仕様を見る

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

計算例

入力した場合

A: 1,071
B: 462

結果

Gcd: 21
工程数: 3

ユークリッド互除法の計算ツールは、2つの整数を受け取り、二千年前以上にユークリッドが記した方法、つまり割り算を繰り返して余りを引き継ぐ方法で最大公約数を求めます。最終的な数値だけでなく、被除数 = 除数 × 商 + 余りという形式の各行を含む完全なステップリストを返すため、答えに至る過程を正確にご確認いただけます。負の値も受理します（最大公約数は絶対値で計算されます）。整数でない入力は拒否され、未定義の gcd(0,0) のケースも拒否されます。

ユークリッドの互除法が実際に行うこと

2つの整数の最大公約数とは、両方を余りなく割り切る最大の数です。ユークリッドの互除法は、因数分解を一切行わずにそれを求めるため、非常に大きな入力でも高速なままです。考え方は単純です。ある数が a と b の両方を割り切るなら、a を b で割った余りも割り切ります。

そこで組 (a, b) を (b, a mod b) に置き換えて繰り返します。各ステップは1回の割り算で、たとえば 1071 = 462 × 2 + 147 のようになり、余りがゼロになるまで続けます。最後のゼロでない余りが最大公約数です。

余りは各ステップで必ず小さくなるため、ループは必ず終了し、しかも速く終了します。ステップ数は小さい方の入力の対数に比例します。

ステップ付きの最大公約数が役立つ場面

最大公約数そのものはどこにでもあるもので、どの言語の標準ライブラリにもあります。この機能が付け加えるのは追跡記録です。教師や学生はステップリストを使って、約数の当て推量ではなく本物のユークリッド互除法で演習が解かれたことを確認します。

開発者は、分数の約分、アスペクト比の削減、互いに素であることの検査をデバッグする際にこれを使います。252 = 105 × 2 + 42 という行を見れば、手計算がコードとどこで分かれたかが正確にわかるからです。

暗号学を学ぶ方は、ベズー係数とモジュラ逆数を生成する拡張版の基礎としてこのアルゴリズムに出会いますが、先に単純な割り算のステップを見ておくと、その飛躍がずっと容易になります。デモと本番の間に驚きはありません。

活用例

解いた演習問題を確認する

宿題の問題の2つの数を貼り付け、手書きの割り算ステップとアルゴリズムが実際に生成するステップを比較します。

分数と比率を約分する

分子と分母の最大公約数を取得して分数を約分します。ステップリストが、除数がどう見つかったかの監査証跡になります。

拡張版の前にアルゴリズムを教える

まず学生に単純な割り算の追跡を示し、その後、同じループの上に構築されるベズー係数とモジュラ逆数に進みます。

よくある質問

なぜ gcd(0,0) は拒否されるのですか？

ゼロとゼロの最大公約数は未定義だからです。どの整数もゼロを割り切るため、最大のものが存在しません。少なくとも1つはゼロ以外の値を指定してください。

負の数を渡せますか？

はい。最大公約数は絶対値で計算されるため、gcd(-1071, 462) は gcd(1071, 462) と同じ結果を返します。

steps 配列には何が含まれますか？

割り算ごとに1つのオブジェクト、つまり被除数、除数、商、余りが含まれ、各行は被除数 = 除数 × 商 + 余りと読めます。最後のゼロでない余りが最大公約数です。

入力はどのくらい大きくできますか？

安全な整数の最大値 9007199254740991 までです。出力の商と余りはすべて正確です。

割り算は何回くらい必要ですか？

余りは毎回必ず小さくなるので、計算は必ず終わり、しかも速く終わります。手順の数は小さいほうの数の対数に比例し、1071と462なら3回の割り算で最大公約数21が出ます。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/math/euclidean-algorithm

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

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

curl -X POST https://api.kit.forhosting.com/math/euclidean-algorithm \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":1071,"b":462}'

const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 1071,
    "b": 462
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/math/euclidean-algorithm",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 1071,
    "b": 462
},
)
task_id = res.json()["task_id"]

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

body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "a": 1071,
  "b": 462
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

max_abs 9007199254740991

エラー

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

技術的な注記

同じコードがこのページのブラウザ上で無料で実行され、有料APIでもご利用いただけます。

ユークリッドの互除法が実際に行うこと

このエンドポイントはまさにその手続きを実行し、結論だけでなく行われたすべての割り算を返します。そのため、宿題の確認にも、より大きなシステム内の計算の監査にも有用です。

入力、エッジケース、エラーの報告方法

負の整数も有効です。最大公約数は絶対値で定義されるため、gcd(-1071, 462) は gcd(1071, 462) と同じであり、ステップリストも絶対値で計算されます。ただし、両方がゼロの場合は gcd(0,0) が数学的に未定義であるため拒否されます。エラーが部分的な応答を生成することはありません。a と b の2つのフィールドを送信し、どちらも整数である必要があります。"1071" のような正確な整数を表す数値文字列は受理されますが、小数、分数、指数表記、非数値は、何が問題だったかを説明する invalid_input エラーで拒否されます。ゼロは一方のフィールドには有効な入力で、gcd(a, 0) は |a| であり、この場合割り算が不要なためステップリストは空になります。値は IEEE 754 倍精度の安全な整数範囲（約900京）に制限されているため、出力の商と余りはすべて正確です。リクエストは機械可読のコードと、ユーザーに表示できるメッセージとともに拒否されます。

技術的な質問

料金はいくらですか？

API経由で1リクエスト$0.002です。このページのブラウザ上でも無料で実行できます。

整数として認められるのは何ですか？

小数部分のないJSON数値、または先頭に符号を付けられる数字の文字列です。小数、指数表記、非数値は invalid_input エラーで拒否されます。

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

ユークリッド互除法

無料で実行

計算例

ユークリッドの互除法が実際に行うこと

ステップ付きの最大公約数が役立つ場面

活用例

解いた演習問題を確認する

分数と比率を約分する

拡張版の前にアルゴリズムを教える

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

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

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

ユークリッドの互除法が実際に行うこと

入力、エッジケース、エラーの報告方法

技術的な質問

ありがとう