フェルマーの小定理 計算ツールの使い方
フェルマーの小定理 計算ツールは、$a^n \bmod p$ の冪乗剰余（余り計算）を指数還元の手順とともに瞬時に算出します。3つの整数を入力するだけで、素数判定や合同式の計算プロセスを確認できます。
- 底 a を入力 - 任意の整数（正の数・負の数・0）を入力します。
- 指数 n を入力 - 0以上の整数を入力します。$10^{15}$ のような非常に大きな値も一瞬で処理されます。
- 法 p を入力 - 2以上の正の整数を入力します。素数を指定するとフェルマーの小定理による簡略化が有効になります。
- 計算結果を確認 - ツールの自動判定により、素数判定、互いに素の確認、指数の還元処理、および最終的な余り（剰余）が表示されます。
計算例： $a = 3, n = 100, p = 7$ の場合 法 $p = 7$ は素数であり、$\gcd(3, 7) = 1$ のため小定理が適用できます。 $p - 1 = 6$ より、指数を還元すると $100 \bmod 6 = 4$ となります。 したがって、$3^{100} \bmod 7 = 3^4 \bmod 7 = 81 \bmod 7 = 4$ と計算されます。
公式と理論 - フェルマーの小定理と合同式
フェルマーの小定理を用いた冪乗剰余の計算は、以下の基本定理に基づいています。
p が素数であり、gcd(a, p) = 1 のとき：
a^(p−1) ≡ 1 (mod p)
同値な表現：
a^p ≡ a (mod p)
指数の還元（簡略化）：
a^n mod p = a^(n mod (p−1)) mod p| 記号 | 意味 |
|---|---|
| a | 底となる整数 |
| n | 指数 |
| p | 素数の法（モジュラス） |
| p−1 | 素数 p におけるオイラーのφ関数値 φ(p) |
| n mod (p−1) | フェルマーの小定理により還元された縮小指数 |
なぜ指数の還元ができるのか： $a^{p-1} \equiv 1 \pmod p$ であるため、指数部にある $(p-1)$ の倍数は剰余計算において1に変換されて消去されます。したがって、指数 $n$ を $(p-1)$ で割った余り $n \bmod (p-1)$ のみを計算すればよいことになります。
定理が適用できないケース： 法 $p$ が素数でない場合、あるいは $p$ が $a$ を割り切る場合（$\gcd(a, p) > 1$）は、フェルマーの小定理を直接適用することはできません。その場合、本ツールは繰り返し二乗法（Square-and-Multiply）による直接的な余り計算を行います。
前提条件と計算上限
法 $p$ は2以上の整数、指数 $n$ は0以上の整数である必要があります。すべての入力値は整数である必要があります。
フェルマーの小定理 計算ツールの活用シーン
フェルマーの小定理 計算ツールは、初等整数論の学習、暗号理論の研究、プログラミングコンテスト（競プロ）などで幅広く利用されています。
- 数学・整数論の学習 - $2^{12} \bmod 13 = 1$ などの合同式の問題を手計算した際、正解確認としてツールを活用できます。
- RSA暗号の仕組み理解 - 公開鍵暗号の基盤となる数学的構造（オイラーの定理やフェルマーの小定理）の理解を深めることができます。
- 競技プログラミング（AtCoderなど） - 巨大な冪乗の余りを求めるアルゴリズム（冪乗剰余・逆元計算など）の検証に便利です。
- フェルマーテスト（素数判定） - 様々な底 $a$ に対して $a^{p-1} \bmod p = 1$ が成り立つかを試すことで、確率的素数判定の挙動を体感できます。
本ツールは単に結果を表示するだけでなく、素数判定・互いに素の判定・指数の還元ステップを明示するため、学習・検証ツールとして最適です。