合同式——時計の算数とモジュラー算術

合同式とは

「時計で午前 7 時の 8 時間後は何時？」——$7 + 8 = 15$ ですが、時計は 12 を超えると 0 に戻るので答えは午後 3 時です。このように「割った余りが同じかどうか」に注目した計算の仕組みが合同式（モジュラー算術）です。

整数 $a, b$ と正の整数 $m$ について、$a - b$ が $m$ で割り切れるとき、

$a \equiv b \pmod{m}$

と書き、「$a$ と $b$ は $m$ を法として合同」と読みます。

言い換えると：$a \equiv b \pmod{m}$ $\iff$ $a$ と $b$ を $m$ で割ったときの余りが等しい——「同じグループに属している」という意味です。

時計の算数

「時計の算数は合同式そのもの」——$\text{mod}\ 12$ の算術は時計とまったく同じです。

• 時計は $12$ を超えると $0$（または $12$）に戻る
• $7 + 8 = 15 \equiv 3 \pmod{12}$（午前 $7$ 時の $8$ 時間後 = 午後 $3$ 時）
• $3 \times 5 = 15 \equiv 3 \pmod{12}$

時計の文字盤をイメージすると、合同式は「一周したときに同じ位置にくる数は全部仲間」という考え方です。

var angle, i, numA, numB, sum, modSum;
var cx, cy, radius;

function loop() {
ctx.clearRect(0, 0, W, H);

numA = 7;
numB = Math.round((mx / W) * 11);
sum = numA + numB;
modSum = sum % 12;

cx = W / 2;
cy = 175;
radius = 120;

// clock face
ctx.fillStyle = '#1e293b';
ctx.beginPath();
ctx.arc(cx, cy, radius, 0, Math.PI * 2);
ctx.fill();
ctx.strokeStyle = '#475569';
ctx.lineWidth = 3;
ctx.stroke();

// hour marks and numbers
for (i = 0; i < 12; i++) {
  angle = (i / 12) * Math.PI * 2 - Math.PI / 2;
  var hx = cx + Math.cos(angle) * (radius - 12);
  var hy = cy + Math.sin(angle) * (radius - 12);
  var label = i === 0 ? 12 : i;

  if (i === numA % 12) {
    ctx.fillStyle = '#60a5fa';
    ctx.font = 'bold 15px monospace';
  } else if (i === modSum) {
    ctx.fillStyle = '#22c55e';
    ctx.font = 'bold 15px monospace';
  } else {
    ctx.fillStyle = '#94a3b8';
    ctx.font = '13px monospace';
  }
  ctx.textAlign = 'center';
  ctx.fillText(label, hx, hy + 4);
}

// arc from numA to result
var startAngle = ((numA % 12) / 12) * Math.PI * 2 - Math.PI / 2;
var endAngle = (modSum / 12) * Math.PI * 2 - Math.PI / 2;
ctx.strokeStyle = '#fbbf2488';
ctx.lineWidth = 6;
ctx.beginPath();
ctx.arc(cx, cy, radius - 25, startAngle, endAngle, false);
ctx.stroke();

// hand pointing to result
angle = (modSum / 12) * Math.PI * 2 - Math.PI / 2;
ctx.strokeStyle = '#22c55e';
ctx.lineWidth = 3;
ctx.beginPath();
ctx.moveTo(cx, cy);
ctx.lineTo(cx + Math.cos(angle) * (radius - 30), cy + Math.sin(angle) * (radius - 30));
ctx.stroke();

// hand pointing to numA
angle = ((numA % 12) / 12) * Math.PI * 2 - Math.PI / 2;
ctx.strokeStyle = '#60a5fa';
ctx.lineWidth = 2;
ctx.beginPath();
ctx.moveTo(cx, cy);
ctx.lineTo(cx + Math.cos(angle) * (radius - 45), cy + Math.sin(angle) * (radius - 45));
ctx.stroke();

// center dot
ctx.fillStyle = '#e2e8f0';
ctx.beginPath();
ctx.arc(cx, cy, 5, 0, Math.PI * 2);
ctx.fill();

// labels
ctx.fillStyle = '#e2e8f0';
ctx.font = '14px monospace';
ctx.textAlign = 'center';
ctx.fillText(numA + ' + ' + numB + ' = ' + sum + ' ≡ ' + modSum + ' (mod 12)', cx, 310);
ctx.fillStyle = '#60a5fa';
ctx.fillText('出発: ' + numA, cx - 80, 330);
ctx.fillStyle = '#22c55e';
ctx.fillText('到着: ' + modSum, cx + 80, 330);

requestAnimationFrame(loop);
}
loop();

合同式の性質

「合同式は普通の計算とほぼ同じように足し算・掛け算ができる」——余りの世界で計算しても、先に余りを取っても結果が変わらないのが合同式の便利なところです。

$a \equiv b \pmod{m}$ かつ $c \equiv d \pmod{m}$ のとき：

注意：除法（割り算）は $m$ と割る数が互いに素のときのみ可能です——「時計の世界では割り算に注意が必要」。

モジュラー逆数

「掛けると 1 になる数——通常の逆数の合同式版」。普通の数で $5 \times \frac{1}{5} = 1$ のように、合同式の世界でも「掛けると 1 になる相手」があります。

$a \cdot a^{-1} \equiv 1 \pmod{m}$

$a$ の $m$ を法とするモジュラー逆数 $a^{-1}$ は $\gcd(a, m) = 1$ のときに（一意に）存在します。

例：$5^{-1} \pmod{7}$ を求める。

$5 \times 1 = 5$、$5 \times 2 = 10 \equiv 3$、$5 \times 3 = 15 \equiv 1$ ✓

よって $5^{-1} \equiv 3 \pmod 7$——「$5 \times 3 = 15$ は 7 で割ると余り 1 になる」。

フェルマーの小定理

「大きな数のべき乗の余りを、一から計算しなくてもよい方法」——フェルマーの小定理はこれを可能にします。

$p$ が素数で $\gcd(a, p) = 1$ のとき：

$a^{p-1} \equiv 1 \pmod{p}$

「素数 $p$ を法として、任意の整数を $(p-1)$ 乗すると必ず 1 になる」——これを使えば巨大なべき乗の余りが少ないステップで計算できます（RSA 暗号の鍵）。

例：$2^{100} \pmod{7}$ を計算。

$p = 7$ なので $2^6 \equiv 1 \pmod 7$。$100 = 6 \times 16 + 4$ なので：

$2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 \equiv 2 \pmod 7$

「100乗を6乗ずつのかたまりに分けて、残りの4乗だけ計算すれば済む」——大きな計算が一気に小さくなります。

中国の剰余定理（CRT）

「複数の時計を使って場所を特定する」——ちょうど「3で割ると2余り、5で割ると3余る数は何か？」という謎解きのようなものです。

互いに素な正の整数 $m_1, m_2$ に対して、連立合同式：

$x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$

は $0 \le x < m_1 m_2$ の範囲に唯一の解を持ちます——「2つの条件を同時に満たす数はちょうど1つだけある」。

例：$x \equiv 2 \pmod 3$、$x \equiv 3 \pmod 5$ を解く。

$x = 3k + 2$ を代入：$3k + 2 \equiv 3 \pmod 5$ → $3k \equiv 1 \pmod 5$ → $k \equiv 2 \pmod 5$。

$k = 5j + 2$ なので $x = 3(5j+2) + 2 = 15j + 8$。よって $x \equiv 8 \pmod{15}$——「答えは 8」。確認：$8 = 3 \times 2 + 2$ ✓、$8 = 5 \times 1 + 3$ ✓。

モジュラー算術の応用

「合同式は現代のデジタル技術を支えている」——日常生活では見えませんが、あらゆる場所で動いています：

練習問題

問題1

$2026 \bmod 7$ を計算せよ。

$2026 = 7 \times 289 + 3$ なので $2026 \equiv 3 \pmod 7$——「2026年は曜日の計算で余り 3 に相当する」。

問題2

$7^{2025} \pmod{11}$ を計算せよ。

フェルマーの小定理より $7^{10} \equiv 1 \pmod{11}$——「10乗ずつのかたまりはすべて 1 になる」。

$2025 = 10 \times 202 + 5$ なので $7^{2025} \equiv 7^5 = 16807 \equiv 10 \pmod{11}$。

まとめ

• $a \equiv b \pmod{m}$：$a$ と $b$ を $m$ で割った余りが等しい——「同じ余りのグループ」
• 合同式の加法・乗法・べき乗は余りの世界でそのまま成立——「先に余りを取っても計算できる」
• モジュラー逆数：$\gcd(a,m)=1$ のとき存在する——「合同式の世界の割り算」
• フェルマーの小定理：$a^{p-1} \equiv 1 \pmod p$（$p$ 素数）——「巨大なべき乗の計算が楽になる」
• 中国の剰余定理：互いに素な法の連立合同式は唯一解を持つ——「条件が2つあれば1つに絞れる」
• RSA 暗号・ハッシュ・曜日計算など広く応用される——「インターネットを守る算数」

次回は行列の基本——数値を表形式に並べた強力な道具を学びます。