「割り切れる」とはどういうことか ― 整数論はなぜ mod から始まるのか
mod 演算は「情報を捨てる射影」です．時計・曜日・競プロの 10^9+7 がすべて同じ構造をもつことを見抜き，整除の定義から合同式，Z/nZ の環構造への入り口までを解説します．
整数論の教科書を開くと，最初の数ページで「」という記号が登場します．しかし，なぜ整数論は割り算の余りから始まるのでしょうか？ この記事では，mod 演算が「情報を意図的に捨てる射影」であり，日常の時計や曜日の計算と本質的に同じ構造をもつことを見ていきます．
1 整除の定義 ― すべての出発点
定義 1 (整除).
整数 に対し， をみたす整数 が存在するとき， は を割り切るといい， と書きます．
例 2.
です（）．一方 です．
整除は一見単純ですが，強力な性質をもちます．
定理 3 (整除の基本性質).
整数 に対して，
かつ ならば および
ならば，任意の整数 に対して
かつ ならば （推移律）
これらは証明も簡単ですが，「割り切れるという関係は線形結合で保存される」という本質を示しています．
2 除法の定理 ― 余りの存在と一意性
定理 4 (除法の定理).
整数 と正の整数 に対し，
をみたす整数 （商）と （余り）がただ一組存在します．
証明.
存在は の最小元として を取ればよいです．もし ならば かつ で の最小性に矛盾します．一意性は， とすると で， より が従います． □
この定理により，余りが well-defined であることが保証されます．
3 合同式 ― 余りに注目する
定義 5 (合同式).
整数 と正の整数 に対し， が成り立つとき， と は を法として合同であるといい，
と書きます．
注意 6.
は「 と を で割った余りが等しい」と同値です．つまり合同式は余りだけに着目するということです．
合同式の強力さは，四則演算と整合する点にあります．
定理 7 (合同式の演算).
， ならば，
証明.
かつ とします．加法は より明らかです．乗法は と分解すれば，各項が の倍数なので従います． □
4 mod の直感 ― 時計・曜日・そして 10^9+7
mod 演算は日常に溢れています．
例 8 (時計).
午前 10 時に 5 時間後は午後 3 時です．．時計は の世界で動いています．
例 9 (曜日).
今日が水曜日（3 とする）で 10 日後は何曜日か？ ，つまり土曜日です．曜日は の世界です．
例 10 (競プロの ).
AtCoder などの競技プログラミングで「答えを で割った余りを出力せよ」という問題が頻出します．なぜこの数なのでしょうか？
は素数です．素数を法とすると逆元が存在し，割り算もできます（後の記事で詳しく扱います）
なので，2つの余りの積が となり，64 ビット整数に収まります
5 情報の射影としての mod
注意 11.
mod 演算の本質は情報を捨てることにあります．整数 から への写像は， から への全射です．商 という情報を捨て，余り だけを残します．情報を捨てるのに，加法と乗法が保存される ― これが合同式の驚くべき性質です．この性質を代数学の言葉で言えば， が環の準同型であるということです．
6 の環構造への伏線
余りの世界に加法と乗法を入れた代数系をと書きます．
定義 12 ().
に演算 ， を定めたものを剰余環と呼びます．
注意 13.
が素数のとき， は体（field）になります．つまり 0 以外のすべての元に逆元が存在し，割り算ができます．これが が素数であることの代数的な意味です．
7 まとめ
整除 は整数論の最も基本的な関係です
合同式は「余りだけに着目する」操作で，加法・乗法と整合します
mod は「情報を捨てる射影」であり，時計，曜日，競プロの はすべて同じ構造です
は余りの世界に代数構造を与えたもので， が素数なら体になります
次の記事では，この mod の世界における「最大公約数」の計算法 ― ユークリッドの互除法に迫ります．