ForHosting KIT · 開発者向けツール

トーティブ一覧計算機：n と互いに素な整数

n のトーティブとは、n 以下の正の整数のうち、n と共有する因数が 1 だけの数です。この計算機はオイラーのトーシェント関数の値だけでなく、該当する数を昇順ですべて返します。正の整数を入力すると、元の値、条件を満たす整数の個数、トーティブの一覧を取得できます。合同算術の演習を確認したり、既約剰余系を調べたり、どの値がオイラーのトーシェント関数に数えられるかを具体的に確かめたりする際に役立ちます。

● Beta無料・ブラウザ内で実行

無料で実行 API仕様を見る

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

トーティブ一覧が表すもの

n のトーティブは、1 から n までの整数のうち、n との最大公約数が 1 である数です。2つの数の最大公約数が 1 であることを、互いに素であるといいます。たとえば、候補が n の約数でなくても、n と素因数を1つでも共有していれば除外されます。候補を 1 から順番に調べるため、返される配列は昇順です。1 はすべての正の整数と互いに素なので、必ず含まれます。通常、終点の n 自体は含まれません。gcd(n, n) は n だからです。ただし n = 1 は例外で、一覧は [1] になります。併記される個数は一覧の長さと一致し、オイラーのトーシェント関数 phi(n) の値でもあります。この機能は実際の要素を表示します。非常に大きな整数について個数だけが必要な場合は、トーシェント値専用の計算機が適しています。この違いは合同算術で重要です。ここで得られる要素そのものが、n を法とする既約剰余系を構成するためです。

計算の仕組み

計算を始める前に n を検証します。整数の数値、または通常の10進表記による整数の文字列を受け付けます。小数や数値でない値は拒否し、n が 1 未満なら入力エラーを返します。また、大きな JSON 配列を生成する処理がブラウザーでも API でも予測可能になるよう、公開されている上限を適用します。検証後、アルゴリズムは 1 から n までの各整数を調べます。各候補にはユークリッドの互除法を使います。余りが 0 になるまで、数の組を除数と余りで繰り返し置き換え、最後の 0 でない除数を最大公約数とします。その値が 1 の候補だけを結果に加えます。この処理は厳密な整数演算であり、近似、因数データベース、ネットワーク通信、乱数、時刻を使用しません。そのため、同じ入力からは常に同じ順序の出力が得られます。個数は別の式で求めず、完成した配列から算出するので、表示された一覧と件数が食い違うこともありません。

結果を適切に利用する方法

次の処理で個数だけでなく個々の剰余類が必要な場合に、この一覧をご利用ください。初等整数論では、n を法として逆元を持つ数を直接確認できます。一覧に含まれる値はすべて n を法とする乗法逆元を持ち、省かれた値は持ちません。暗号理論の学習では、乗数が法と互いに素でなければならない理由を示す資料になります。ただし、これは教育用の算術結果であり、鍵生成システムではありません。返された個数をオイラーのトーシェント公式による手計算と比較すれば、素因数分解の確認にも使えます。互いに素であることは2数間の関係であり、一覧の各数が素数だという意味ではありません。n と素因数を共有しなければ、合成数も含まれます。たとえば、素数を法とする場合には合成数の候補もトーティブになり得ます。自動処理ではトーティブ配列を直接読み、個数を要約値としてお使いください。特定の2数だけを判定したい場合は、一覧全体を作らない互いに素の判定機能が適しています。

活用例

既約剰余系を作成する

n を法として逆元を持つ剰余類の代表元を、昇順ですべて生成します。

整数論の演習を確認する

手作業で求めたトーティブ一覧と個数を、決定的な計算結果と比較できます。

合同式の逆元を調べる

標準範囲にある値のうち、n を法とする乗法逆元を持ち得るものを特定します。

よくある質問

トーティブとは何ですか？

n のトーティブとは、n 以下の正の整数で、n との最大公約数が 1 である数です。

個数はオイラーのトーシェント関数ですか？

はい。トーティブ配列の要素数が、オイラーのトーシェント関数 phi(n) の値です。

n 自体が通常は一覧にないのはなぜですか？

gcd(n, n) は 1 ではなく n だからです。例外は n = 1 で、トーティブ一覧は [1] です。

トーティブはすべて素数ですか？

いいえ。n と素因数を共有しなければ、合成数でもトーティブになります。

1回の利用料金はいくらですか？

API は1回 $0.002 です。ブラウザー版はローカルで動作するため、API 料金はかかりません。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/totatives-list

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

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

curl -X POST https://api.kit.forhosting.com/numth/totatives-list \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":12}'

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

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/totatives-list",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 12
},
)
task_id = res.json()["task_id"]

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

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

リクエスト例

{
  "n": 12
}

レスポンス例

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

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

料金

1リクエストあたり$0.002

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

制限

max_n 100000

エラー

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

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