数字を「割ったときの余り」と聞くと、学校で習った算数を思い出す人も多いはず。実はこの「余り」を扱う仕組みこそが“モジュロ（mod）”。コンピュータの世界、暗号、データベース、日付・曜日計算、そして競技プログラミングまで、あらゆる場面で使われています。本記事では、モジュロの基本から、合同式・逆元・中国剰余定理といった数学的背景、さらには各プログラミング言語での注意点や実務での使いどころまで、ていねいに解説します。初心者にもわかりやすく、でも使える知識になるよう、例とコードをたっぷり交えて進めます。
モジュロの基本：まずは「余り」の話から
モジュロ（mod、モジュラス演算・剰余演算とも言います）とは、「ある整数を n で割ったときに出てくる余り」を扱う演算のことです。
たとえば
- 17 を 5 で割ると 3 余り 2 → 17 mod 5 = 2
- 25 を 7 で割ると 3 余り 4 → 25 mod 7 = 4
この「n で割った余り」を 法（ほう） n のもとで考える、と表現します。法 n の世界では、値はつねに 0 から n−1 の範囲に“折りたたまれる”イメージです。
記法と読み方：a mod n と 合同 ≡
モジュロには代表的な二つの書き方があります。
- 余りとして書く
a mod n（エー・モッド・エヌ）と書いて、a を n で割った余りを意味します。
例：23 mod 7 = 2 - 合同式で書く
a ≡ b (mod n)と書き、a と b を n で割ると余りが同じであることを表します。
例：23 ≡ 2 (mod 7)（どちらも 7 で割ると余り 2）
合同式は性質がわかりやすく、計算規則（後述）も整理しやすいのが利点です。
直感的なイメージ：時計と円環
モジュロの代表的な比喩は時計。
12 時間制の時計は 12 を法とする世界です。
10 時に 5 時間進めると 15 時ですが、時計では 3 時。これは 15 ≡ 3 (mod 12) と同じ。
大きな数も 12 で折りたたまれて 0〜11（あるいは 1〜12 の表現）に戻ってきます。
この「ぐるっと一周して戻る」円環（サークル）イメージは、モジュロを直感的に理解する助けになります。
具体例で理解する：正負の数・大きな数
17 mod 5 = 2（すなおな例）-13 mod 5は？
「-13 を 5 で割ったときに、0〜4 のどれに折りたたむか」を考えると、2 になります（-13 は 5 の倍数 −15 に 2 を足したものだから）。
つまり -13 ≡ 2 (mod 5)。- 大きな数でも同じ：
10^9 + 7（よく使う素数）で折りたたむとき、分割して都度 mod を取るのがコツです。
心得：途中でこまめに mod を取る
巨大な計算は途中でオーバーフローすることがあります。**「計算の途中で mod を取る」**ことで、値の範囲を保ち、安全かつ高速に計算できます。
合同式の基本性質
法 n のもとで、次が成り立ちます（a ≡ b, c ≡ d (mod n) のとき）：
- 和：a + c ≡ b + d (mod n)
- 差：a − c ≡ b − d (mod n)
- 積：a × c ≡ b × d (mod n)
- 累乗：a^k ≡ b^k (mod n)（k は非負整数）
つまり、余り同士で計算してよいということ。これがアルゴリズム実装での強力な武器になります。
「割り算」はいつできる？逆元の話
モジュロでは基本的に割り算はできません。代わりに「逆元（ぎゃくげん）」を使います。
法 n において、整数 a に対して a の逆元 a⁻¹ が存在するのは、gcd(a, n) = 1（a と n が互いに素）のとき。
このとき
a × a⁻¹ ≡ 1 (mod n)
となる a⁻¹ が一意に存在します。
例：3 の逆元（mod 11）
3 と 11 は互いに素。実際に探すと 4 が逆元です（3×4=12 ≡ 1 (mod 11)）。
逆元の求め方：拡張ユークリッドの互除法
ax + ny = gcd(a, n) を満たす整数 x, y を求めると、gcd(a, n)=1 のとき x ≡ a⁻¹ (mod n) です。
実装は短く、競技・実務で頻出。
# Python: 逆元（a^(-1) mod n）を拡張ユークリッドで
def inv_mod(a, n):
# ax + ny = gcd(a,n) を解く
r0, r1 = a, n
x0, x1 = 1, 0
while r1 != 0:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
x0, x1 = x1, x0 - q * x1
if r0 != 1:
raise ValueError("逆元は存在しません（a と n が互いに素でない）")
return x0 % n # 正の代表にそろえる
素数のときは簡単：フェルマーの小定理
p が素数で a が p の倍数でない（gcd(a, p)=1）なら、
a^(p-1) ≡ 1 (mod p)
したがって
a^(-1) ≡ a^(p-2) (mod p)
と求まります。競技プログラミングで **MOD=10^9+7（素数）**が多用されるのはこのため。逆元が簡単に計算できます。
# Python: pow の第3引数で高速累乗＋mod
inv = pow(a, MOD-2, MOD) # MOD は素数、a は 0 でない
オイラーの定理とオイラー関数
一般の n に対して、a と n が互いに素なら
a^φ(n) ≡ 1 (mod n)
が成り立ちます。ここで φ(n) は オイラーのトーシェント関数（n 以下の n と互いに素な整数の個数）。
RSA 暗号の理論的土台にも登場します。
中国剰余定理（CRT）：大きな法を分解して解く
法が互いに素な複数の合同式の組を、一つの合同式にまとめる定理です。
例
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
3, 5, 7 は互いに素。CRT により、法 105（=3×5×7）のもとでただ一つの解が存在します。実際に計算すると x ≡ 23 (mod 105) になります。
このように「小さな法で分割して計算 → まとめる」という発想は、実装上も高速化や分散計算に役立ちます。
法が素数の世界は“きれい”
法 p（素数）での整数全体は、「足し算・掛け算・逆元」が揃った**体（フィールド）**になります。
つまり 0 以外のすべての要素に逆元があり、線形代数（行列の逆行列など）もモジュロで行えます。
一方、法が合成数だと逆元が存在しない要素が出てくるため、注意が必要です。
計算表で見る：mod 5 の足し算・掛け算
足し算（mod 5）
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
掛け算（mod 5）
| × | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
2 や 3 に掛けると 0 以外の値がぐるぐる巡回しているのが見て取れます（逆元があることの反映）。
プログラミング言語の % は“同じじゃない”に注意
「% 演算子＝モジュロ」と思いがちですが、言語によって定義が違うことが最大の落とし穴です。とくに負の数を扱うと差が出ます。
| 言語 | -13 % 5 | 備考 |
|---|---|---|
| Python | 2 | 結果は除数（5）と同じ符号（非負）になる。a == (a//b)*b + a%b が成立し、a%b は 0..b-1 に収まる（b>0）。 |
| Ruby | 2 | Python と同様に非負へ正規化される（b>0）。 |
| JavaScript | -3 | **剰余（remainder）**寄りの定義。結果の符号は被除数（a）の符号に一致。 |
| C/C++ | -3 | C99/C++ は除算が 0 方向へ切り捨て。a%b の符号は被除数に一致。 |
| Java | -3 | C/C++/Java は同系。 |
この違いはハッシュのバケット計算、配列インデックス化、日付算でバグの温床です。
**負の可能性があるなら「正規化」**を徹底しましょう。
# Python は不要なことが多いが、慣用的な正規化
x = (x % MOD + MOD) % MOD
// JavaScript / C / Java など：負が出たらもう一度足して正規化
let r = a % n;
if (r < 0) r += n; // 0..n-1 に整える
高速に計算する：繰り返し二乗法（binary exponentiation）
巨大な指数 a^k mod n は、そのまま計算すると間に合いません。そこで 繰り返し二乗法。
指数を 2 進法で分割し、都度二乗・必要時だけ掛け合わせます。
def pow_mod(a, k, n):
a %= n
res = 1
while k > 0:
if k & 1:
res = (res * a) % n
a = (a * a) % n
k >>= 1
return res
計算量は O(log k)。暗号・競技ともに必須テクニックです。
実務での使いどころ
曜日・カレンダー計算
- 「今日から 100 日後は何曜日？」→ (基準曜日 + 100) mod 7。
- 月内ローテーション、週次スケジュールも mod 7／mod 14 で簡潔に。
ID の分散・ハッシュテーブル
ユーザー ID をバケット数 m で割って bucket = hash(id) mod m とすれば、配列にほぼ均等に分散できます。
テーブルサイズを素数にして偏りを抑える、m を 2 の冪にしてビット演算で高速化する、などの設計判断とも相性が良いです。
チェックディジット（誤り検出）
- ISBN-10 は mod 11、**クレジットカード（Luhn）**は mod 10 を使った検査手法がベース。
数字の転記ミスを機械的に検出できます。
擬似乱数・暗号
- 線形合同法（LCG）
x_{n+1} = (ax_n + c) mod m - RSA の暗号化・復号は巨大整数の mod 計算（モジュラ指数演算）そのものです。
グラフィックス・音楽・ゲーム
- ループアニメ、シームレスタイルリング、リズムパターンの周期表現などは mod の得意分野。
- 色相（H）を 360 度で折り返すのも
H mod 360。
競技・実装での鉄則
- 途中で mod を取る
加減乗算のたびに%MODを挟み、値の暴走を防ぐ。 - 負の値を正規化
x = (x % MOD + MOD) % MOD（Python/Ruby なら前半省略可のことも多い）。 - 割り算＝逆元
divide(a, b) ≡ a × inv(b) (mod M)。gcd(b, M) = 1を確認。 - オーバーフローに注意
C++ でlong longを使ってもa*bがはみ出す場合は64bit 乗算の安全化や__int128、Montgomery 乗算などを検討。
// C++: 64bit 安全寄りの乗算（__int128 を使える環境）
long long mul_mod(long long a, long long b, long long m){
__int128 t = (__int128)a * b;
t %= m;
return (long long)t;
}
例題で手を動かす
例題1：基本の余り
12345 mod 7 を求めよ。
解：12345 = 12320 + 25。12320 = 7 × 1760 は 7 の倍数なので、余りは 25 mod 7 = 4。答え 4。
例題2：合同式の利用
2025 ≡ ? (mod 9)
解：9 の倍数判定は各桁和を 9 で割るのと同じ。2+0+2+5=9 → 0。したがって 0。
例題3：累乗の高速化
3^100 mod 7 を求めよ。
解：φ(7)=6、3^6 ≡ 1。よって 3^100 ≡ 3^(96)×3^4 ≡ 1×81 ≡ 4 (mod 7)。答え 4。
例題4：逆元
法 17 で 5 の逆元を求めよ。
解：試すと 5×7=35 ≡ 1 (mod 17) → 7。
例題5：CRT
x ≡ 1 (mod 3), x ≡ 2 (mod 4) を解け。
解：3 と 4 は互いに素。小さい方から試すとx = 1, 4, 7, 10, 13, ... のうち、4 で 2 余るのは 10。
よって x ≡ 10 (mod 12)。
SQL・スクリプトでも役立つワンパターン
- SQL（多くの方言）：
col % 7で曜日ローテを作る、WHERE id % 4 = 0でシャーディング風に抽出。 - Excel/Google スプレッドシート：
=MOD(A1, 7)。 - Bash：
$((a % b))。ただし負の扱いは要確認。
「剰余（remainder）」と「モジュロ（modulus）」の違い（用語メモ）
- remainder（剰余）：単に割り算で出る余り。言語仕様によっては結果が負になることも。
- modulus（法）：折りたたむ“幅”そのもの（n のこと）。
- modulo（モジュロ）：その法のもとで計算すること、あるいは “〜を法として” の意味。
- congruence（合同）：余りが等しい関係
≡を指す数学用語。
実務的には「mod 演算」と「%」をほぼ同義に呼ぶことも多いですが、負数の扱いと逆元の存在条件の二点は、数学と実装とでズレやすいので丁寧に切り分けて理解しておきましょう。
よくある質問（FAQ）
Q. a mod 0 はできますか？
A. できません。0 で割ることは定義されません。
Q. 同じ数で何度も mod を取るのはムダでは？
A. 正しさは変わりませんが、オーバーフロー防止と数の桁を削る効果があるので、むしろ実装では推奨です。
Q. なぜ素数の法が好まれる？
A. 0 を除くすべての要素に逆元が存在し、扱いが簡潔だから。ハッシュや暗号・数値処理での設計自由度も高まります。
Q. mod の前後で計算順序を変えると結果は変わる？
A. 加減乗では (a ∘ b) mod n = ((a mod n) ∘ (b mod n)) mod n が成り立ちます（∘ は +, −, ×）。
ただし 割り算は逆元を通して扱うので別物です。
まとめ：モジュロを味方に
- モジュロは「n で割った余り」を扱う仕組み。
- 合同式を使うと、余り同士で計算してよい。
- 割り算は基本的にできないが、互いに素なら逆元で置き換えられる。
- 素数の法は扱いやすく、逆元や高速累乗がシンプル。
- 実務（曜日、ハッシュ、検査、暗号）や実装（オーバーフロー対策、計算高速化）で威力を発揮。
- 言語ごとの
%の仕様差（とくに負数）は必ず確認・正規化！
ここまで押さえれば、「モジュロって結局なに？」が「モジュロ、使える！」に変わるはず。今日からコードと数式で、うまく“折りたたんで”いきましょう。
コメント