合同式・モジュラー算術

Q: 合同式・モジュラー算術とは何ですか？

整数 a, b と正の整数 m（法・モジュラス）に対して、a - b が m で割り切れるとき「a と b は法 m に関して合同である」といい、次のように書く。 a \equiv b \pmod{m} \iff m \mid (a-b) \iff a \bmod m = b \bmod m これは「a を m で割った余り」と「b を m で割った余り」が一致することと同値であり、整数全体を余りの値ごとに m 個のグループ（剰余類）に分類する関係である。

Q: 合同式・モジュラー算術は社会やプログラミングでどのように使われていますか？

ハッシュ関数のインデックス計算とRSA暗号の高速べき乗剰余演算: ハッシュテーブルは巨大な入力データを固定長の配列に格納するため、ハッシュ値をテーブルサイズで割った余り（モジュラー演算）を格納位置として使う。また、RSA暗号の暗号化・復号は「非常に大きな数の何百桁ものべき乗を法 n で計算する」処理そのものであり、桁あふれを防ぎつつ高速に計算するために繰り返し二乗法（高速べき乗剰余）が使われる。

時計盤のように数がぐるぐる回る「割った余り」の世界と、暗号・ハッシュ関数を支える剰余演算

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: モジュラー算術（合同式）とは、整数を法（modulus） $m$ で割った余りだけに注目して計算する算術体系であり、余りが一致する数どうしを「合同」とみなして $a \equiv b \pmod{m}$ と書く
2: モジュラー算術の世界では数直線がまっすぐ伸びるのではなく、 $m$ 個の数字が並んだ「時計の文字盤」のように輪になって繰り返す（ $m$ を超えると 0 に戻る）
3: この「割った余りだけを扱う」性質のおかげで、どれだけ巨大な数を掛けても計算結果が有限の範囲に収まり続けることが保証され、ハッシュ関数の値域制御やRSA暗号の安全性の根幹を支えている

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

モジュラー算術（合同式）とは、整数を法（modulus）$m$ で割った余りだけに注目して計算する算術体系であり、余りが一致する数どうしを「合同」とみなして $a \equiv b \pmod{m}$ と書く

身につく武器・思考力

モジュラー算術の世界では数直線がまっすぐ伸びるのではなく、$m$ 個の数字が並んだ「時計の文字盤」のように輪になって繰り返す（$m$ を超えると 0 に戻る）

実社会・ITでの活躍現場

•ハッシュ関数のインデックス計算とRSA暗号の高速べき乗剰余演算
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

法（モジュラス） $m$ をスライダーで変えると、時計の文字盤の目盛りの数が変化する。数 $n$ のスライダーを動かして、 $n$ が文字盤上のどの位置（ $n \bmod m$ ）に対応するかをハイライトで確認しよう。さらに2つの数 $a, b$ を選び「足し算」または「掛け算」モードで演算すると、結果が文字盤を何周してどの位置に着地するか（ラップアラウンド）が矢印アニメーションで表示される。

紫 = 現在の数 n の位置、赤 = 演算結果の位置（時計の文字盤 mod m）

法（モジュラス）m = 12数 n = 9 → n mod m = 9

演算を試す: a + b (mod m)

a = 9（≡ 9）b = 8（≡ 8）

9 + 8 = 17 ≡ 5 $\pmod{12}$

↑ m を変えると文字盤の目盛りの数が変わる。a, b や演算を変えると、結果が文字盤を何周かして着地する「ラップアラウンド」の様子が矢印で確認できる。

直感チェック！ミニクイズ

法 $m = 12$ （12時間制の時計）で考えるとき、現在の時刻が 9 時で、そこから 8 時間進むと何時になるか。これは合同式でどう表されるか？

Layer 2 — 定義・受験・証明

定義

整数 $a, b$ と正の整数 $m$ （法・モジュラス）に対して、 $a - b$ が $m$ で割り切れるとき「 $a$ と $b$ は法 $m$ に関して合同である」といい、次のように書く。

a \equiv b \pmod{m} \iff m \mid (a-b) \iff a \bmod m = b \bmod m

これは「 $a$ を $m$ で割った余り」と「 $b$ を $m$ で割った余り」が一致することと同値であり、整数全体を余りの値ごとに $m$ 個のグループ（剰余類）に分類する関係である。

公式・数理モデル

a \equiv b \pmod m \iff m \mid (a-b), \qquad (a+c) \equiv (b+d),\; (ac) \equiv (bd) \pmod m \;\text{（}a\equiv b, c\equiv d\text{ のとき）}

証明・導出

合同式が加法・乗法と両立すること（合同式の演算規則）の証明： $a \equiv b \pmod m$ かつ $c \equiv d \pmod m$ であるとする。定義より、ある整数 $p, q$ が存在して

a - b = mp, \qquad c - d = mq

と書ける。

【加法について】

(a+c) - (b+d) = (a-b) + (c-d) = mp + mq = m(p+q)

これは $m$ の倍数であるから、 $(a+c) \equiv (b+d) \pmod m$ が成り立つ。

【乗法について】 $a = b + mp,\; c = d + mq$ を用いて $ac$ を展開すると、

ac = (b+mp)(d+mq) = bd + bmq + dmp + m^2pq = bd + m(bq + dp + mpq)

したがって $ac - bd = m(bq+dp+mpq)$ は $m$ の倍数であり、 $ac \equiv bd \pmod m$ が成り立つ。

この2つの性質により、合同式は「先に余りを取ってから足し算・掛け算しても、先に計算してから余りを取っても同じ結果になる」ことが保証される。これがモジュラー算術で巨大な数の計算を余りだけで完結できる理論的根拠である。

押さえておきたいポイント

合同式は「同値関係」であり、整数全体を $m$ 個の剰余類 $\{0, 1, \ldots, m-1\}$ に分割する（時計の文字盤のイメージ）
$\gcd(a, m) = 1$ （ $a$ と $m$ が互いに素）であるとき、かつそのときに限り $a$ の「モジュラー逆数」（ $ax \equiv 1 \pmod m$ を満たす $x$ ）が存在する
フェルマーの小定理: $p$ が素数で $\gcd(a,p)=1$ のとき $a^{p-1} \equiv 1 \pmod p$ が成り立ち、RSA暗号の理論的基盤となっている
ハッシュ関数の多くは「巨大な入力を固定サイズのテーブルに割り振る」ためにモジュラー算術（ハッシュ値 mod テーブルサイズ）を利用している

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

ハッシュ関数のインデックス計算とRSA暗号の高速べき乗剰余演算

ハッシュテーブルは巨大な入力データを固定長の配列に格納するため、ハッシュ値をテーブルサイズで割った余り（モジュラー演算）を格納位置として使う。また、RSA暗号の暗号化・復号は「非常に大きな数の何百桁ものべき乗を法 $n$ で計算する」処理そのものであり、桁あふれを防ぎつつ高速に計算するために繰り返し二乗法（高速べき乗剰余）が使われる。

1// ハッシュテーブルの格納位置を決めるモジュラー演算
2function hashIndex(key: string, tableSize: number): number {
3  let hash = 0;
4  for (let i = 0; i < key.length; i++) {
5    hash = (hash * 31 + key.charCodeAt(i)) % tableSize; // 各文字ごとに mod を取り桁あふれを防ぐ
6  }
7  return hash;
8}
9
10// 高速べき乗剰余 (Fast Modular Exponentiation): base^exp mod m を O(log exp) で計算
11// RSA暗号の暗号化・復号 c = m^e mod n の核となるアルゴリズム
12function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
13  let result = 1n;
14  base = base % mod;
15
16  while (exp > 0n) {
17    if (exp % 2n === 1n) {
18      // 指数が奇数のビットのときだけ結果に掛け込む
19      result = (result * base) % mod;
20    }
21    exp = exp / 2n;       // 指数を半分にする（2進数を1桁シフト）
22    base = (base * base) % mod; // 底を2乗する（繰り返し二乗法）
23  }
24  return result;
25}
26
27// 例: ハッシュテーブル(サイズ16)への格納位置
28console.log(hashIndex("math-world-lab", 16)); // 0〜15のどこかに収まる
29
30// 例: RSAでの暗号化計算 c = m^e mod n （実際は数百桁の数を使う）
31const encrypted = modPow(42n, 17n, 3233n);
32console.log(`暗号文: ${encrypted}`); // 桁があふれず高速に法 n の範囲内で計算できる