1 合同の基本概念
1.1 合同の定義
1.1.1 剰余による定式化
整数 \(a,b\) が正の整数 \(m\) に関して「合同」であるとは、差 \(a-b\) が \(m\) で割り切れることをいう。つまり \(a\equiv b \pmod m\) は \(m\mid(a-b)\) と同値である。この条件は「同じ余りを持つ」という直観と対応し、計算対象を剰余のクラスにまとめて扱える。
1.1.2 合同式の表記と読み方
合同式は一般に \(a\equiv b \pmod m\) と書く。読み方は「\(a\) は \(b\) と \(m\) を法として合同」などである。ここで記号 \(\pmod m\) は「\(m\) を法（モジュラス）」として考える、という意味を表し、以後の等号の意味が通常の等号ではなく合同であることを明示する。
1.2 合同が表す同値関係
1.2.1 反射律・対称律・推移律
合同は同値関係を成す。反射律は \(a-a=0\) が任意の \(m\) で割り切れることから従う。対称律は \(m\mid(a-b)\) なら同時に \(m\mid(b-a)\) が成り立つため成立する。推移律は \(m\mid(a-b)\) と \(m\mid(b-c)\) がともに成り立てば、差を足し合わせて \(m\mid(a-c)\) も従うことにより示される。
1.2.2 合同類の考え方
合同によって整数全体は「同じ余りをもつものの集まり」に分割される。これらの集まりは合同類と呼ばれ、代表元を1つ選ぶことでその類の計算が可能になる。合同類どうしの間では、演算を「代表元の取り方に依存しない形」で定義できる点が合同の有用性を支える。
1.3 合同と剰余の関係
合同は剰余の概念を、特定の代表元に縛られない形で抽象化したものとみなせる。任意の整数 \(a\) は \(m\) で割ると \(a=qm+r\)（\(0\le r<m\)）の形に整理でき、同じ \(r\) をもつ整数同士が互いに合同になる。したがって、合同の議論は「余りの体系」上で行われるが、その際に整数そのものではなく余りのクラスを操作対象に据えることで、計算や証明が整理される。
2 合同式の性質
2.1 合同の演算への適用
2.1.1 足し算・引き算に関する性質
\(a\equiv b\pmod m\) かつ \(c\equiv d\pmod m\) が成り立つとき、加法について \(a+c\equiv b+d\pmod m\) が従う。理由は差を展開して \( (a+c)-(b+d)=(a-b)+(c-d)\) が \(m\) で割り切れることにある。減法も同様に扱え、合同は加減算と両立する。
2.1.1.1 置換可能性と計算の簡略化
合同が確立している場面では、同じ法のもとで合同な数を互いに置き換えてよい。これにより大きな整数を直接扱わず、余りだけに置き換えて計算量を減らせる。たとえば積や冪の途中で大きな値が出ても、適宜合同により縮約すれば最終的な余りを効率的に求められる。
2.1.2 掛け算に関する性質
乗法についても同様の両立性が成り立つ。具体的に \(a\equiv b\pmod m\) なら任意の整数 \(c\) について \(ac\equiv bc\pmod m\) が成り立つ。さらに \(a\equiv b\pmod m\) と \(c\equiv d\pmod m\) なら \(ac\equiv bd\pmod m\) が従う。差を用いた展開により、割り切れ性が保たれることが確認できる。
2.1.3 整数係数多項式への拡張
合同の両立性は多項式にも拡張される。整数係数の多項式 \(f(x)\) に対して、\(a\equiv b\pmod m\) なら \(f(a)\equiv f(b)\pmod m\) が成立する。これは多項式が和と積の有限回から構成されるため、先の加法・乗法の整合性を積み重ねればよいからである。この性質により、合同式の変形が系統的に行える。
2.2 除算が可能な場合・不可能な場合
2.2.1 法と元の関係（可逆性の観点）
合同式で「割り算」を行うには注意が必要である。一般に \(ax\equiv ay\pmod m\) から \(x\equiv y\pmod m\) を即座に引くことはできない。これは \(a\) が \(m\) に対して可逆（逆元を持つ）でない場合に、打ち消しが失敗するためである。整数の個数論では、特に \(\gcd(a,m)=1\) のときに逆元が存在し、合同式の両辺を \(a\) で「正しく」割ったと同等の操作が可能になる。
2.2.2 割り算を誤用したときの注意
誤用の典型は、合意形成済みの打ち消し則を通常の等号と同様に扱うことにある。たとえば \(m\) が 6 で、左右に 2 が掛かっている合同式を考えると、2 は 6 と互いに素でないため、両辺を 2 で割って同値な合同へ写せる保証はない。このため実務では、打ち消しを行う前に \(\gcd\) を確認し、必要に応じて別手順（整理して解く、一次合同に戻す等）を選ぶ。
3 合同式の解法
3.1 1次合同式
3.1.1 具体的な解き方の手順
1次合同式は典型的に \(ax\equiv b\pmod m\) の形で現れる。手順の核は、左辺と法の関係を調べて、解の存在条件と簡約された形を得ることにある。まず \(\gcd(a,m)=d\) とし、\(d\mid b\) なら解が存在し、存在しなければ解はない。存在する場合には、合同全体を \(d\) で割って問題を簡単化し、残った係数が法と互いに素になる状況で逆元を用いて \(x\) を求める流れになる。
3.1.2 解の個数と条件
解の個数は法の縮約と一致して決まる。先の記号のもとで \(d=\gcd(a,m)\) とすると、解が存在するなら通常 \(d\) 個の解が法 \(m\) の範囲で区別される。より具体には、縮約後の一次合同が一意に解ける状況を作り、そこから合同類として戻すと、法の分割に対応した個数が現れる。従って「条件が満たされるか」と「満たされたときに何通りになるか」を同時に確認することが重要である。
3.2 連立合同式
3.2.1 典型的な解法の発想
連立合同式は \(x\equiv a_1\pmod{m_1}\)、\(x\equiv a_2\pmod{m_2}\)、…のように複数の制約がある場合を指す。発想としては、各制約が同じ \(x\) によって同時に満たされるように、法の構造に沿って統合する点にある。代表的には法が互いに素であるとき、解は一意性の強い形で構成できるため、順に条件を組み合わせる戦略が有効になる。
3.2.2 整合条件の確認
法が互いに素でない場合、条件が矛盾する可能性がある。たとえば \(x\equiv a\pmod m\) と \(x\equiv b\pmod n\) が同時に成り立つためには、両者が矛盾しない調整が必要である。具体的には \(\gcd(m,n)\) に関する整合条件が現れ、差 \(a-b\) がその最大公約数で割り切れるかどうかが鍵になる。これにより解が存在する場合だけ次の計算へ進める。
3.3 モジュラス（法）の変更
3.3.1 法を縮める・広げる考え方
法の変更では、情報の強さが変わることを理解する必要がある。法 \(m\) での合同 \(a\equiv b\pmod m\) は、一般に \(m\) が大きいほど条件が強くなる。逆に法を小さくすると条件は緩和されるため、同じ合同が自動的に成立するとは限らないが、成立する場合は整理されやすい。逆方向、つまり緩い条件から強い条件へ戻すのは別の制約が必要になりうる。
3.3.2 同値な問題への変換
解法の効率化には、同値な条件へ写す操作が頻出する。たとえば係数が共通因子を持つ場合に両辺を整理して一次合同の標準形へ寄せたり、余りの代表を別の形に取り直して計算を単純化したりする。合同は剰余クラス上の等式として理解できるため、表現の変更は「同じクラスを指しているか」を保つ限り有効である。
4 合同の応用と発展
4.1 合同と約数・倍数
4.1.1 公約数・公倍数との関係
合同は約数・倍数の言い換えとして現れることが多い。たとえば \(a\equiv b\pmod m\) は \(m\) が \(a-b\) を割り切ることを意味し、差の約数として捉えられる。さらに連立した条件は、それぞれの法が生成する割り切り制約として理解できるため、公約数や公倍数の観点が解の構造を説明する枠組みになる。
4.1.2 割り切り判定への応用
割り切りの判定は、合同を使うと判定対象を余り計算へ落とし込める。たとえばある整数式 \(F\) が \(m\) で割り切れるかは \(F\equiv 0\pmod m\) と同じである。よって、式の計算の途中で合同による縮約を行い、最終的な余りが 0 になるかどうかを確認すればよい。
4.2 合同から環の構成へ
4.2.1 商環としての見方（概説）
合同類を集めて操作を定義すると、新しい代数的対象が得られる。具体的には、整数全体を法 \(m\) による合同で割り、得られた合同類の集合に加法と乗法を「代表元の選び方に依存しない形」で入れる。これは商環（あるいは同値関係による商）の構成に対応し、通常の整数演算と同じ要領で余りクラスを扱えるようになる。
4.2.2 合同類の演算（直観）
合同類どうしの和や積は、各類の代表元を選んで計算し、その結果の類を返すことで定義できる。代表を入れ替えても同じ合同類が得られるため、結果が安定する。この直観は、合同式が「余りの計算で完結する」ことを理論的に裏付けるものである。結果として、計算は有限個の状態（余り）に還元され、整理された枠組みの上で展開可能になる。
4.3 応用例（初等分野）
4.3.1 暗号での利用を支える考え方（概説）
暗号分野では、合同による計算の体系が繰り返し現れる。特に大きな整数の演算を行う際に、法を固定して余りだけを追うことで効率化できる点が実用上重要である。また、同じ合同の枠組みでも「逆元が存在するか」や「ある操作を元に戻せるか」といった性質が安全性議論に関わることがある。ここでは詳細なアルゴリズムは扱わず、合同が計算の土台になるという位置づけを示す。
4.3.2 パズル・数当てゲームへの応用（例）
数当てパズルでは「ある法で同じ余りになる」という条件がヒントとして使われることがある。たとえば参加者に複数の合同条件を与え、成立する解の候補を絞り込む形式にすると、解が 1 つに定まる場合や複数に分岐する場合の違いが自然に表れる。合同の考え方を用いると、全探索より少ない手数で候補を絞れるため、ゲーム性のある学習素材としても機能する。