合同算術の計算
入力
| 演算 | a mod n |
|---|---|
| a | 17 |
| 法 n | 5 |
| 指数 b | 3 |
合同算術の計算
a mod n・冪乗剰余（a^b mod n）・剰余逆元（a⁻¹ mod n）を計算します。数論の基礎から暗号理論の応用まで対応。
入力
結果
値を入力すると計算結果が表示されます。
詳細
合同算術（modular arithmetic）は、整数を固定の正整数 n（法）で割った余りに注目する数論の一分野です。整数 a と b が n を法として合同であることを a ≡ b (mod n) と表し、両者が n の倍数だけ異なることを意味します。本計算機は、剰余・冪乗剰余・剰余逆元の 3 種類の演算を扱います。
剰余演算（a mod n）
正整数 n に対して、整数 a を n で割った余り r は次の関係を満たす唯一の整数として定義されます。
a=q×n+r,0≤r<nここで q = ⌊a / n⌋ は床商（floor quotient）、r が剰余です。この定義では r は常に非負となります。
計算例。 a = 17、n = 5 のとき：
q=⌊17/5⌋=3,r=17−3×5=2よって 17 mod 5 = 2 です。5 目盛りの時計盤を 17 進めると、針は目盛り 2 を指す、という直感的な理解と対応します。
負の値の場合。 a = −7、n = 5 のとき：
q=⌊−7/5⌋=−2,r=−7−(−2)×5=3よって −7 mod 5 = 3 です。数学的定義では r は常に非負ですが、C 言語・JavaScript などの % 演算子は切り捨て剰余を使うため −2 を返します。本計算機は数学的定義に従い、結果を [0, n − 1] に正規化します。
冪乗剰余（a^b mod n）
a^b を計算してから n で割る素朴な方法は、b が大きくなると指数的に桁数が増えるため実用的ではありません。繰り返し二乗法（バイナリ法）は、この問題を中間値を逐次 n で剰余をとることで解決します。
指数 b を 2 進数に展開し、最下位ビットから順に処理します。各ステップで累積基数を二乗し mod n をとり、ビットが 1 のときはさらに元の底 a を掛けて mod n をとります。この方法では乗算回数が O(log b) に抑えられ、中間値は常に [0, n − 1] に収まります。
計算例。 a = 17、b = 3、n = 5 のとき：
17≡2(mod5) 172≡4(mod5) 173=172×17≡4×2=8≡3(mod5)直接確認：17^3 = 4913 = 982 × 5 + 3。
剰余逆元（a⁻¹ mod n）
整数 a の法 n における剰余逆元とは、次を満たす整数 x のことです。
a×x≡1(modn)存在条件。 剰余逆元が存在するのは、a と n が互いに素（gcd(a, n) = 1）であるとき、そのときに限ります。法 n が素数であれば、1 以上 n − 1 以下のすべての整数が逆元を持ちます。n が合成数の場合、n と公約数を持つ整数には逆元が存在しません。
拡張ユークリッドアルゴリズム。 gcd(a, n) を求める通常のユークリッドアルゴリズムを拡張し、線形結合 a × s + n × t = gcd(a, n) の係数 s, t を追跡します。gcd(a, n) = 1 のとき、s が求める逆元です。
計算例。 a = 3、n = 5 のとき：
- 5 = 1 × 3 + 2
- 3 = 1 × 2 + 1
後退代入：1 = 3 − 1 × 2 = 3 − 1 × (5 − 1 × 3) = 2 × 3 − 1 × 5
よって 3 × 2 ≡ 1 (mod 5)、すなわち 3⁻¹ ≡ 2 (mod 5) です。確認：3 × 2 = 6 = 1 × 5 + 1。
床商とユークリッド恒等式
任意の整数の組 (a, n)（n ≥ 1）に対し、床商 q = ⌊a / n⌋ と剰余 r = a mod n は次の恒等式を満たします。
a=q×n+r,0≤r<n本計算機は r と q を同時に表示するため、この恒等式を任意の入力値で直接確認できます。
応用
合同算術は数学・計算機科学の多くの分野で基礎をなしています。
- 公開鍵暗号。 RSA 暗号は大きな素数の積を法とした冪乗剰余と逆元に基づいています。
- チェックサム。 ISBN-13・IBAN・クレジットカードの Luhn アルゴリズムはいずれも合同算術を用いて入力誤りを検出します。
- 曜日計算。 d 日後の曜日は d mod 7 で求められ、ゼラーの公式などの暦計算も合同演算に帰着します。
- ハッシュテーブル。 キーをバケット番号に写す演算は key mod テーブル長で表されます。
- リングバッファ。 読み書きポインタの更新はインデックス mod 容量で循環します。
よくある質問 (FAQ)
負の数における mod とプログラミング言語の % はどう違いますか？
数学的な mod は結果を常に [0, n − 1] の非負の値に正規化します。たとえば −7 mod 5 = 3 です。これは −7 = (−2) × 5 + 3 の関係から導かれます。一方、C 言語・JavaScript などで使われる % 演算子（切り捨て剰余）は −7 % 5 = −2 を返します。Python 3 の % は床除算を採用しているため数学的定義と同じ結果（3）になります。本計算機は数学的定義に従います。
17^1000 mod 5 のような大きな冪乗剰余はどのように計算しますか？
繰り返し二乗法（バイナリ法）を使います。指数を 2 進数に展開し、各桁を処理するたびに中間値を法 n で剰余をとります。これにより乗算回数を O(log b) に抑えられ、中間値が法 n の範囲内に収まるため、指数が非常に大きくても高速かつメモリ効率よく計算できます。
剰余逆元が存在するのはいつですか？
a と n が互いに素（gcd(a, n) = 1）であるとき、そのときに限り剰余逆元 a⁻¹ mod n が存在します。法 n が素数であれば、1 以上 n − 1 以下のすべての整数は逆元を持ちます。n が合成数の場合、n と公約数を持つ整数には逆元が存在しません。
合同算術はどのような場面で使われますか？
合同算術は数学・計算機科学の広い分野で用いられています。主な応用として、公開鍵暗号（RSA は大きな法に対する冪乗剰余と逆元に基づく）、チェックサム（ISBN・IBAN・クレジットカードの Luhn アルゴリズム）、曜日計算（7 を法とした周期）、ハッシュテーブルのバケット計算（key mod テーブル長）、リングバッファのインデックス管理などがあります。