合同式・モジュラー計算ツール（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（逆元）が存在します。 |
合同式・モジュラー計算（mod計算）とは
合同式（モジュラー演算）とは、ある数を法（modulus）と呼ばれる正の整数で割った余りにだけ着目する演算です。2つの整数 a、b が同じ法 n で割ったときに同じ余りになるとき、「a と b は n を法として合同である」といい、a ≡ b (mod n) と表記します。このツールは「基本 mod」「加減乗算」「べき乗」「逆元」の4モードで、合同式にまつわる代表的な計算をまとめて行えます。
内部の計算はすべて JavaScript のネイティブ BigInt で行うため、指数が数百桁に達するべき乗や、桁数の大きい整数どうしの加減乗算でも、丸め誤差を起こさず正確な結果が得られます。負の数を入力した場合も、数学的な合同式の定義（結果は常に0以上、法未満の範囲に収まる）に従って正規化するため、プログラミング言語ごとに異なる剰余演算子の挙動に振り回されずに済みます。
合同式・モジュラー計算ツールの使い方
- モードを選ぶ 「基本 mod」「加減乗算」「べき乗」「逆元」の4つから、求めたい計算の種類を選びます。
- 整数を入力する 選んだモードに応じて a・b・法 n（または底と指数）を入力します。負の整数もそのまま入力できます。
- 演算子を選ぶ（加減乗算モードのみ） 加算・減算・乗算のいずれかをプルダウンから選びます。
- 結果を確認する 入力するたびに自動で再計算され、数式と結果が表示されます。逆元が存在しない場合はその旨のメッセージに切り替わります。
- 入力をやり直す 「クリア」ボタンで全モードの入力欄を空にできます。
使いこなすためのヒント
- 負の数のmodはプログラミング言語によって挙動が異なります。本ツールは数学的な定義（結果は常に0以上n未満）に従うため、-7 mod 3 は -1 ではなく 2 になります。
- べき乗モードは「繰り返し二乗法」で計算するため、指数が数百桁になっても瞬時に結果が求まります。RSA暗号の暗号化・復号処理でも同じアルゴリズムが使われています。
- 時計の時刻は身近な合同式の例です。「15時」を12時間表記にすると「15 mod 12 = 3時」になります。
- 逆元モードは、法 n が素数でなくても a と n が互いに素（最大公約数が1）でありさえすれば計算できます。
- 競技プログラミングでは、巨大な答えをそのまま出力する代わりに 1,000,000,007 などの大きな素数で割った余りを答えとして要求する問題が頻出します。本ツールのべき乗モードはそうした検算にも使えます。
合同式・モジュラー計算が役立つ場面
公開鍵暗号のアルゴリズムを学ぶ
RSA暗号の暗号化・復号は、巨大な数のべき乗を法で割った余りを求める処理そのものです。べき乗モードで指数と法を大きくして、繰り返し二乗法の速さを体感できます。
ハッシュ関数の設計原理を確認する
多くのハッシュ関数は内部で剰余演算を使って値を一定の範囲に折りたたみます。加減乗算モードで途中式の余りがどう変化するかを追えます。
チェックディジット（検査数字）の仕組みを調べる
ISBN・クレジットカード番号・銀行口座番号などの検査数字は、各桁の重み付き和を法で割った余りから算出されます。基本 modモードで手計算の検算に使えます。
曜日・カレンダーの周期計算をする
「n日後は何曜日か」「うるう年は何年周期か」といった周期性のある問題は、7や4を法とした合同式として表せます。
競技プログラミングの検算をする
「答えを 1,000,000,007 で割った余りを求めよ」という頻出形式の問題で、自分の実装結果が正しいかをべき乗モード・加減乗算モードで照合できます。
合同式・モジュラー計算に関する用語集
- 合同式（congruence）
- a ≡ b (mod n) の形の式で、「a と b を n で割った余りが等しい」ことを表します。「=」ではなく「≡」を使うのは、等しいのは値そのものではなく余りだからです。
- 法（modulus）
- 割る数のことです。本ツールでは1以上の整数を指定します。法が変わると同じ数でも合同関係が変わります。
- 剰余演算（mod演算）
- ある数を法で割った余りを実際に計算する操作です。数学的な定義では結果は常に0以上、法未満の範囲に収まります。
- モジュラー逆元
- a・x ≡ 1 (mod n) を満たす整数 x のことです。合同式の世界で「a で割る」操作の代わりに「a の逆元を掛ける」ことで同じ効果を得られます。
- 互いに素
- 2つの整数の最大公約数が1であることです。a と n が互いに素であるときに限り、a の n を法とする逆元が存在します。
- 拡張ユークリッドの互除法
- 最大公約数を求める過程と同時に、a・x + n・y = gcd(a, n) を満たす整数の組 (x, y) を求める算法です。逆元モードの計算に使われています。
- 繰り返し二乗法（高速べき乗法）
- 指数を2進数展開し、底を繰り返し2乗しながら該当する桁だけ結果に掛け込むことで、指数の桁数に比例する回数の乗算だけでべき乗を求めるアルゴリズムです。べき乗モードで使われています。
- モジュラー指数計算
- 底のべき乗を法で割った余りを求める計算です。RSA暗号の暗号化・復号処理の中心的な演算で、本ツールの「べき乗」モードに対応します。
よくある質問
余談ですが ― 「時計の算数」が支える現代暗号
合同式（モジュラー演算）は、しばしば「時計の算数（clock arithmetic）」と呼ばれます。12時間表記の時計では、13時は1時と「同じ」ものとして扱われます。これはまさに13 ≡ 1 (mod 12) という合同式そのものであり、ある数を法（この場合は12）で割った余りだけに着目する考え方です。ドイツの数学者カール・フリードリヒ・ガウスが1801年の著書『整数論の研究（Disquisitiones Arithmeticae）』で合同式の記法「≡」を体系化したことで、この考え方は現代数学の標準的な道具になりました。
一見素朴に見えるこの演算は、現代のインターネットセキュリティの根幹を支えています。RSA暗号をはじめとする公開鍵暗号方式では、巨大な数のべき乗を法で割った余りを計算する「モジュラー指数計算」が暗号化・復号の中心的な処理です。指数や法が数百桁に及ぶため、単純にべき乗を計算してから余りを求める方法では計算量が爆発してしまいますが、繰り返し二乗法を使えば指数の桁数に比例する回数の掛け算だけで済み、実用的な速度で処理できます。
拡張ユークリッドの互除法によるモジュラー逆元の計算も、暗号理論だけでなく符号理論やハッシュ関数の設計など、コンピュータサイエンスの幅広い分野で使われる基礎技術です。「2000年以上前の古代の算術」と「最新のセキュリティ技術」が同じ数学的土台の上に成り立っているという事実は、数論の普遍性を象徴しています。