使い方
- 演算を選びます。a mod n、逆元、累乗、中国剰余定理のいずれかです。
- 数a、指数e、法nを、求められた欄に入力します。または、合同式（1行に1つ）に1行ずつ入力します。
- 結果を読み取ります。逆元の場合は、確認の欄で存在するかどうかが示されます。
- 計算の過程をたどります。表には、拡張互除法の行または二進法の桁が示されます。
剰余、逆元、累乗
aをnで割った余りrは、0 ≤ r < nで、a = q·n + rを満たす数です。そのためa mod nは負になりません。たとえば −17 mod 5は3です。−17 = (−4)·5 + 3だからです。aのnを法とする逆元は、a·x ≡ 1 (mod n)を満たすxです。これはgcd(a, n) = 1のときに限り存在し、拡張互除法で求められます。累乗a^e mod nは二乗と掛け算で計算します。eの二進法の各桁につき、1回の二乗を行います。
a mod n = a − n·⌊a ÷ n⌋
s·a + t·n = 1ならば、a⁻¹ ≡ s (mod n)- 多くの計算ツールは、−17 mod 5に −2を返します。これは切り捨て割り算の余りで、剰余ではありません。剰余は常に0からn − 1です。
- 負の指数を持つ累乗はaの逆元を使うため、gcd(a, n) = 1の場合にだけ存在します。
- 互除法の表と二進法の表には中間の数がすべて示されるため、計算を手でたどって確かめられます。
中国剰余定理と扱わない範囲
中国剰余定理は、連立合同式の各式について、mᵢ で割ると余りがrᵢ になる数xを1つ求めます。法どうしが互いに素であれば、それらの積を法として解はちょうど1つあります。互いに素でない場合は、余りが法どうしのgcdを法として一致していなければならず、そうでなければ解はありません。
- 二進法で64桁を超える大きな指数は受け付けません。計算過程を読みやすく保つためです。
- x以外の変数の合同式、多項式の合同式、剰余の平方根は扱いません。
- 計算ツールは整数だけを扱います。小数は受け付けません。
計算例：4¹³ mod 497とほかの演算
指数13は、二進法で1101です。1から始め、各桁で二乗し、桁が1のときには4を掛けると、結果は4、64、120となり、その後445です。よって4¹³ mod 497 = 445です。同じ方法が、計算ツールの桁の表として示されます。
そのほかの例：−17 mod 5 = 3。7を法とする4の逆元は2で、4 × 2 = 8 ≡ 1です。x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)の解はx ≡ 23 (mod 105)です。
| 問い | 答え |
|---|---|
| 4^13 mod 497 | 445 |
| −17 mod 5 | 3 |
| 7を法とする4の逆元 | 2 |
| x ≡ 2 (mod 3)、3 (mod 5)、2 (mod 7) | x ≡ 23 (mod 105) |
よくある質問
−17 mod 5が −2ではなく3になるのはなぜですか？
剰余は負にならない余りで、0 ≤ r < nです。−17 = (−4) × 5 + 3なので、剰余は3です。多くの計算ツールが示す −2は、切り捨て割り算の余りで、剰余ではありません。
数はいつ、法nでの逆元を持ちますか？
その数とnの最大公約数が1のときです。たとえば4は、7を法として逆元2を持ちますが、6を法としては逆元を持ちません。gcd(4, 6) = 2だからです。
累乗で、繰り返しの掛け算ではなく二乗を使うのはなぜですか？
各二進数の桁で二乗して剰余をとると、どの数も小さく保たれます。4¹³では、途中の最大の値は484 × 4 = 1936です。長い積をそのまま計算すると、約8桁の数になってしまいます。
合同式の法どうしが公約数を持つ場合はどうなりますか？
解は依然として存在することがあります。余りは、2つの法のgcdを法として一致している必要があります。x ≡ 2 (mod 4)とx ≡ 8 (mod 6)は一致し、解はx ≡ 2 (mod 12)です。
入力した数は、サーバーに送られますか？
いいえ。計算はブラウザの中で行われ、入力した内容が当サイトに送られることはありません。
出典
- Wikipedia（英語）: Modular arithmetic
- Wikipedia（英語）: Modular exponentiation
- Wikipedia（英語）: Extended Euclidean algorithm
- Wikipedia（英語）: Chinese remainder theorem
数値と文章の最終確認日：2026年11月10日火曜日。