合同式・モジュラー計算ツール（mod計算機）
基本のmod計算・加減乗算・べき乗（繰り返し二乗法）・モジュラー逆元（拡張ユークリッドの互除法）の4モードに対応した合同式計算機。負の数のmodや大きな指数のべき乗もBigIntで正確に計算します。
モジュラー演算の基本性質
| 性質 | 説明 |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | 加算はmodを取ってから足しても、足してからmodを取っても結果は同じです。 |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | 減算では結果が負になり得るため、最後に +n してから再度mod nすることで [0, n) の範囲に収めます。 |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | 乗算も加算と同様、途中でmodを取っても最終結果は変わりません。この性質がべき乗の高速計算（繰り返し二乗法）の土台になっています。 |
| a と n が互いに素 ⇔ a の n を法とする逆元が存在する | 拡張ユークリッドの互除法で gcd(a, n) = 1 となる場合に限り、a × x ≡ 1 (mod n) を満たす x（逆元）が存在します。 |
Tips
- 負の数のmodはプログラミング言語によって挙動が異なります。本ツールは数学的な定義（結果は常に0以上n未満）に従うため、-7 mod 3 は -1 ではなく 2 になります。
- べき乗モードは「繰り返し二乗法」で計算するため、指数が数百桁になっても瞬時に結果が求まります。RSA暗号の暗号化・復号処理でも同じアルゴリズムが使われています。
- 時計の時刻は身近な合同式の例です。「15時」を12時間表記にすると「15 mod 12 = 3時」になります。
- 逆元モードは、法 n が素数でなくても a と n が互いに素（最大公約数が1）でありさえすれば計算できます。
- 競技プログラミングでは、巨大な答えをそのまま出力する代わりに 1,000,000,007 などの大きな素数で割った余りを答えとして要求する問題が頻出します。本ツールのべき乗モードはそうした検算にも使えます。
よくある質問
数学的な合同式の定義では、mod の結果は常に0以上、法（n）未満の範囲に収まります。そのため -7 mod 3 は、JavaScriptの `%` 演算子がそのまま返す -1 ではなく、2 になります（-7 = -3×3 + 2）。本ツールはこの数学的な定義に従って計算します。
モジュラー逆元は「割り算」に相当する演算を合同式の世界で行いたいときに使います。合同式には通常の割り算が定義されていないため、a で割る代わりに a の逆元を掛けることで同じ効果を得ます。RSA暗号の鍵生成（秘密鍵の算出）や、競技プログラミングで「答えを大きな素数で割った余りとして求めよ」という問題で分数を扱う際によく使われます。
本ツールは「繰り返し二乗法」というアルゴリズムを使っているため、指数が数百桁の巨大な数であっても、指数の桁数（正確には2進数での桁数）に比例する回数の掛け算だけで計算が終わります。単純にべき乗をすべて計算してからmodを取る方法とは異なり、瞬時に結果が求まります。
a の n を法とする逆元が存在するのは、a と n の最大公約数（gcd）が1のとき（互いに素であるとき）に限られます。例えば a=4, n=8 の場合、gcd(4, 8)=4 であり1ではないため、4 × x ≡ 1 (mod 8) を満たす整数 x は存在しません。n が素数の場合は、a が n の倍数でない限り必ず逆元が存在します。
実用上はほぼ同じ意味で使われますが、厳密には「合同式」は a ≡ b (mod n) のように2つの数が同じ余りを持つ関係を表す数学的な概念で、「剰余演算（mod演算）」は a を n で割った余りを実際に計算する操作を指します。本ツールは剰余の計算そのものを扱います。
余談ですが ― 「時計の算数」が支える現代暗号
合同式（モジュラー演算）は、しばしば「時計の算数（clock arithmetic）」と呼ばれます。12時間表記の時計では、13時は1時と「同じ」ものとして扱われます。これはまさに13 ≡ 1 (mod 12) という合同式そのものであり、ある数を法（この場合は12）で割った余りだけに着目する考え方です。ドイツの数学者カール・フリードリヒ・ガウスが1801年の著書『整数論の研究（Disquisitiones Arithmeticae）』で合同式の記法「≡」を体系化したことで、この考え方は現代数学の標準的な道具になりました。
一見素朴に見えるこの演算は、現代のインターネットセキュリティの根幹を支えています。RSA暗号をはじめとする公開鍵暗号方式では、巨大な数のべき乗を法で割った余りを計算する「モジュラー指数計算」が暗号化・復号の中心的な処理です。指数や法が数百桁に及ぶため、単純にべき乗を計算してから余りを求める方法では計算量が爆発してしまいますが、繰り返し二乗法を使えば指数の桁数に比例する回数の掛け算だけで済み、実用的な速度で処理できます。
拡張ユークリッドの互除法によるモジュラー逆元の計算も、暗号理論だけでなく符号理論やハッシュ関数の設計など、コンピュータサイエンスの幅広い分野で使われる基礎技術です。「2000年以上前の古代の算術」と「最新のセキュリティ技術」が同じ数学的土台の上に成り立っているという事実は、数論の普遍性を象徴しています。