1 合同式の基本
1.1 合同の定義
1.1.1 法（モジュロ）の概念
合同式は、2つの整数が「ある整数で割ったときの余りが同じ」であることを、等式に似た形で表す枠組みである。基準として用いる整数を法（モジュロ）と呼び、ふつう非負の整数として扱う。
法を \(m\) とすると、整数 \(a\) と \(b\) が同じ余りをもつとは、差 \(a-b\) が \(m\) の倍数になることと同値である。この同値性により、余りという直観を、割り算を明示しない形の関係へと移し替えられる。
1.1.1.1 法と余りの対応関係
余りの対応は次の形で捉えられる。整数 \(a\) を \(m\) で割るとき、商と余りの関係から \[ a = qm + r,\quad 0\le r < m \] のように表せるとする（これは \(m>0\) のとき標準的）。このとき、別の整数 \(b\) が同じ余り \(r\) を共有することは \[ a-b = (q-q')m \] が成り立つこと、すなわち \(a-b\) が \(m\) の倍数であることと一致する。したがって「余りが等しい」は「差が法の倍数」という条件に置き換わる。
1.1.2 合同の表記
合同は通常、等号ではなく合同記号で書かれる。これにより、通常の等式と区別しつつ、法による「見分けの粗さ」を明確にする。
合同式の標準形は、法を右側に添える形で \[ a \equiv b \pmod{m} \] のように表す。ここで \(\pmod{m}\) は「法 \(m\) に関して」と読み、\(a\) と \(b\) が法 \(m\) のもとで同一視されることを示す。
1.1.2.1 記号「≡」の用法
記号「\(\equiv\)」は、通常の等号のように“完全に一致”ではないことを含意する。具体的には、数直線上での位置の一致ではなく、法 \(m\) による剰余の一致を意味する。したがって、たとえば \(7\) と \(15\) は法 \(4\) のもとでは同じ余りを与えるため \[ 7 \equiv 15 \pmod{4} \] となり、実数として等しいわけではない。
1.2 合同の同値関係としての性質
合同は、特定の法を固定したときに、整数全体に対する同値関係として振る舞う。これにより、同じ同値類内の要素は互いに置き換え可能となり、計算の一貫性が確保される。
1.2.1 反射性
反射性とは、任意の整数 \(a\) について自分自身が同じ余りをもつことを指す。差 \(a-a=0\) はどの法の倍数でもあるため、 \[ a \equiv a \pmod{m} \] が常に成り立つ。
1.2.2 対称性
対称性は、一方が他方と合同であるなら逆も合同であることを意味する。仮に \[ a \equiv b \pmod{m} \] ならば \(a-b\) が \(m\) の倍数である。倍数性は符号を変えても保たれるため、\(b-a=-(a-b)\) も同様に \(m\) の倍数となり \[ b \equiv a \pmod{m} \] となる。
1.2.3 推移性
推移性は、合同の鎖をつなげられる性質である。たとえば \[ a \equiv b \pmod{m},\quad b \equiv c \pmod{m} \] が成り立つとき、差の関係として \(a-b\) と \(b-c\) がいずれも \(m\) の倍数である。すると和 \(a-c=(a-b)+(b-c)\) も倍数となり \[ a \equiv c \pmod{m} \] が得られる。これにより、途中の項を挟んだ置換が論理的に妥当になる。
1.3 代表元と剰余類
合同の同値関係としての見方では、同じ余りをもつ整数の集まりが「1つの塊」になる。これが剰余類であり、各剰余類を代表する整数を代表元として扱う。
1.3.1 余りの範囲
剰余類を区別するためには、余りをどの範囲で標準化するかが重要になる。典型的には法が \(m>0\) のとき、余りを \(0\) から \(m-1\) までの範囲に取り、これを各剰余類の代表として固定する。この選び方により、同じ剰余類に属する整数は同一の代表元に対応づけられる。
負の余りを許す流儀もあるが、その場合でも「同じ剰余類が同じ代表元に対応づく」ように規約を統一する必要がある。
1.3.2 代表元の選び方
代表元は必ずしも標準範囲に限定されない。たとえばある剰余類の代表元として \(r\) を選んだとして、別の代表元 \(r+km\) を選んでも同じ剰余類を表すことになる。計算上は、扱う量が最終的にどの形で必要になるかに応じて代表元を選ぶのが実用的である。
たとえば加減算や合同計算では、余りの大きさを抑える選択が計算量の目安になることがある一方、理論的な証明では代表元の一般性を崩さない形が好まれる。
2 合同式の計算ルール
2.1 合同の演算規則
合同は同値関係であるため、同じ剰余クラスの要素を用いて演算しても、結果の剰余クラスが一貫して決まる。これを支えるのが演算規則である。
2.1.1 加法・減法に関する規則
法 \(m\) を固定し、\[ a \equiv b \pmod{m},\quad c \equiv d \pmod{m} \] が成り立つとする。このとき \[ a+c \equiv b+d \pmod{m} \] および \[ a-c \equiv b-d \pmod{m} \] が成り立つ。直観的には「それぞれ同じ余り同士を足す（引く）ので、結果の余りも一致する」ということが、差の倍数性の保存として保証される。
2.1.1.1 具体例による確認
たとえば \(a=7,\ b=15\) を法 \(4\) とする。すると \(7\equiv 15\pmod{4}\)。また別に \(c=3,\ d=11\) でも \(3\equiv 11\pmod{4}\) が成り立つ。すると \[ 7+3=10,\quad 15+11=26 \] であり、どちらも法 \(4\) で余りが \(2\) になる。実際に \[ 10 \equiv 26 \pmod{4} \] となる。引き算でも同様に整合性が確認できる。
2.1.2 乗法に関する規則
乗法についても合同は整合的に働く。すなわち \[ a \equiv b \pmod{m},\quad c \equiv d \pmod{m} \] ならば \[ ac \equiv bd \pmod{m} \] が成り立つ。理由は \(a-b\) や \(c-d\) が \(m\) の倍数であることから、差 \(ac-bd\) がその倍数性を通じて確保されるためである。
2.1.2.1 変形の正当性
合同式の変形を行う際の典型的な誤りは、置換してよい範囲を外れることである。乗法では「同じ法のもとで合同な項どうし」を掛ける限り、結果の剰余クラスは変わらない。よって \[ a \equiv b \pmod{m} \] ならば任意の整数 \(k\) について \[ ka \equiv kb \pmod{m} \] が正当であり、さらに複数項を含む式でも、合同を保ちながら整理することができる。
2.1.3 累乗と多項式への拡張
累乗は乗法を繰り返すことで扱えるため、一般に \[ a \equiv b \pmod{m} \Rightarrow a^n \equiv b^n \pmod{m} \] が成立する。ここで \(n\) は非負整数とする。
さらに多項式に対しても同様の拡張が可能である。多項式 \(P(x)\) を整数係数で定めるとき、 \[ a \equiv b \pmod{m} \Rightarrow P(a) \equiv P(b) \pmod{m} \] が成り立つ。係数の加減乗がいずれも合同の規則に従うため、結論として多項式評価の剰余が一致する。
2.2 同値な合同式の置換
合同計算では、同値な式を適切に置き換えることで簡潔化を行う。ここでいう「置換」は、同じ剰余類同士の対応を保つという条件を含む。
2.2.1 同じ法での置き換え
固定した法が同じである限り、合同式中の項を同じ法で合同な数に置き換えてよい。たとえば \[ a \equiv a' \pmod{m} \] かつ \[ b \equiv b' \pmod{m} \] ならば、加減や積に関して \[ a+b \equiv a'+b' \pmod{m},\quad ab \equiv a'b' \pmod{m} \] のように置換結果が保証される。
重要なのは、法の一致が前提である点である。法が異なると、同じ見かけの等式変形でも意味が変わる。
2.2.2 近い余りの扱い
合同は「余りが等しい」ことを厳密に要求する。したがって、余りが近い、あるいは数値として似ていることは十分条件にならない。たとえば法 \(m\) で余りが \(r\) と \(r+1\) のように異なれば合同にはならない。
一方で計算の過程では、目標がある余りの範囲内に入れること（標準形への正規化）に過ぎない場合があり、そのときは「近い余り」という感覚ではなく、規約に沿って代表元を選び直す操作として処理する。
2.3 代数的な注意点
合同は等式のように扱える面が多いが、法の扱いと記号の意味を取り違えると誤りにつながる。
2.3.1 法が異なる場合
同じ記号形式でも、法が違えば合同関係の情報量は変わる。たとえば \[ a \equiv b \pmod{m} \] と \[ a \equiv b \pmod{n} \] では、成り立つ条件がそれぞれ「\(a-b\) が \(m\) の倍数」「\(a-b\) が \(n\) の倍数」で別物になる。したがって、法を無意識に置き換えることはできない。
さらに、法の大小や関係（例えば \(m\mid n\) のような関係）があるとき、片方の合同がもう一方を保証するかどうかは別途検討が必要となる。
2.3.2 整数以外への拡張の前提
合同の標準的な定義は整数に基づく。整数であることが、割り算の余りという概念や倍数性の扱いを支えているためである。
整数係数の多項式や、有理数のように分数を含む状況では、分母の扱いを通じて合同を意味づける必要がある。たとえば分数同士の合同を考える場合には、共通分母をそろえることで「整数の合同」に落とし込む手順が不可欠になる。
3 合同式の解法と応用
3.1 一次合同式の解き方
一次合同式とは一般に、未知数 \(x\) に対して \[ ax \equiv b \pmod{m} \] の形を指す。解の存在と個数は、係数 \(a\) と法 \(m\) の関係で決まる。
3.1.1 形式の整理
まず、与えられた式が一つの合同として整理されているかを確認する。不要な因子を合同の枠で整理できる場合もあるが、割り算に相当する操作は常に許されるわけではないため、注意が要る。
典型的には、両辺から共通の倍数を取り除く、あるいは \(a\) と \(m\) の最大公約数で条件を分解する方針が用いられる。これにより、解の存在条件が見える形に変形される。
3.1.2 解の個数と一般解
\[ ax \equiv b \pmod{m} \] で \(g=\gcd(a,m)\) とする。すると、解が存在するのは \(g\mid b\) のときに限られる。これは差 \(ax-b\) が \(m\) の倍数であるという条件が、同時に \(g\) の倍数性も満たす必要があることから従う。
解が存在するとき、剰余類としての解はちょうど \(g\) 個に分かれる。一般には、方程式を \(g\) で割り、簡約した形で解を求めたうえで、元の法 \(m\) に戻すことで全体像が得られる。
3.2 連立合同式
連立合同式は、複数の合同条件を同時に満たす未知数を求める問題である。条件の整合性が鍵になる。
3.2.1 代表的な手順
代表的な手順として、まず各合同式を同じ法に揃えられないかを検討する方法があるが、一般には法が異なるため工夫が必要となる。
法を分解して扱う方針として、互いに素な場合を活用するやり方がある。さらに、一般の法でも最大公約数を使って整合性を判定し、矛盾がなければ合同の解集合を合成する。
具体的には、片方の合同式の解をパラメータ化し、それをもう一方に代入して条件を絞り込む手法がしばしば用いられる。
3.2.2 解の整合条件
連立の成立には、個々の合同が矛盾しないことが必要である。互いに素な法であれば、一般に解は一意に定まる方向に進むが、互いに素でない場合は整合性の判定が追加で必要になる。
たとえば \[ x \equiv r_1 \pmod{m_1},\quad x \equiv r_2 \pmod{m_2} \] を考えると、解が存在するためには \(r_1-r_2\) が \(\gcd(m_1,m_2)\) の倍数であることが基本的条件となる。成立すれば、解は法の積に基づく周期性で整理でき、全解の形が具体化される。
3.3 逆元と割り算の可否
合同の“割り算”は、等号のもとでの通常の割り算と同じ感覚では扱えない。逆元の存在がその可否を左右する。
3.3.1 逆元の存在条件
法 \(m\) に関して、整数 \(a\) が可逆（逆元をもつ）であるのは \(\gcd(a,m)=1\) のときである。このとき、ある整数 \(u\) が存在して \[ au \equiv 1 \pmod{m} \] となる。
逆元が存在しない場合、合同方程式の両辺を \(a\) で割る操作は一般に正当化できない。代わりに最大公約数による場合分けで解集合を導く必要が出る。
3.3.2 逆元を用いた解法の流れ
一次合同式 \[ ax \equiv b \pmod{m} \] で \(\gcd(a,m)=1\) なら、逆元 \(a^{-1}\) を用いて \[ x \equiv a^{-1}b \pmod{m} \] と解ける。手順は次の流れで整理できる。
- \(\gcd(a,m)\) を調べ、可逆性を確認する。
- 逆元を求める（たとえば拡張ユークリッドの互除法を使う）。
- 逆元を両辺に掛けて簡約し、残った合同を読み取る。
逆元が存在する状況では解が一意に剰余類として定まりやすく、計算も短い。
3.4 代表的な計算例
3.4.1 余りからの推定
余りの性質を使うと、計算の入口で簡約が効く。例えば法が \(m\) のとき、任意の整数 \(t\) に対して \[ t \equiv (t \bmod m) \pmod{m} \] が成立するため、大きな数は余りに落としてから扱える。
推定の段階では、整合性の確認として「余りが一致すること」を確認する。次に、合同の規則に従って式を整理し、最終形を標準代表に直すと、解答の形が明確になる。
3.4.2 実際の問題文形式への適用
たとえば「\(x\) を法 \(m\) で表す」形式の問題では、最終的に標準範囲の代表元が求められることが多い。手順は概ね「合同式を解いて剰余類を求める」ことに尽きるが、実務的には途中で次の点を揃える。
- どの法で合同を考えるかを冒頭で固定する。
- 逆元を使う場面では最大公約数を確認し、割り算が合法かどうかを判定する。
- 得られた解を標準化して、求められた形式（たとえば \(0\) 以上 \(m-1\) 以下）に整える。
4 性質の整理と周辺概念
4.1 剰余環としての見方
合同を“等しい”とみなす発想は、代数的対象として整理するとさらに明瞭になる。
4.1.1 合同を「等しい」とみなす考え方
同値関係として合同を捉えれば、「法 \(m\) のもとで区別できない数」は同一視される。そこで、整数を剰余類の集合として扱うと、各剰余類が一つの“元”として機能する。
この観点では、合同式 \(a \equiv b \pmod{m}\) は「剰余類として \(a\) と \(b\) が同じ」と表現できる。計算は剰余類の演算として行われ、規則の整合性は同値関係の性質と一致する。
4.1.2 演算の閉性
剰余類の世界で加算や乗算を定義しても、結果が再び同じ世界に戻ることが必要である。これが閉性に相当する。
具体的には、\(a\) と \(b\) がそれぞれある剰余類の代表であるとき、加算 \(a+b\) や積 \(ab\) の剰余類は、その代表の取り方に依存しない。ゆえに、合同の演算規則が“定義の整合性”を持っていることが分かる。
4.2 最大公約数との関係
最大公約数は、解の存在や構造を決める中心的役割を持つ。合同は差の倍数性で定義されるため、共通因子が結果を強く拘束する。
4.2.1 可解性への影響
一次合同 \[ ax \equiv b \pmod{m} \] の解が存在するかどうかは \(\gcd(a,m)\) によって決まる。先述のとおり \(g\mid b\) が必要であり、条件が満たされると解が実際に構成できる。
この観点は直感にも合う。もし \(a\) と \(m\) が共有する因子が \(b\) に現れていないなら、差を \(m\) の倍数にそろえることはできない。逆に一致していれば、適切な \(x\) を作れる余地が残る。
4.2.2 解の構造
解集合は通常、単一解ではなく周期性をもつ。一次合同では、解が存在する場合に解は剰余類として複数になり、その数は最大公約数と一致する。
また、解の取り方を工夫することで、解の形が簡潔に表される。たとえば「ある解に、あるステップサイズを加えるとすべての解が得られる」という形に落とし込むことが可能で、計算の効率や理解に寄与する。
4.3 鍵となる論理的観点（Logicカテゴリ観点）
4.3.1 変形の正しさを支える根拠
合同式の変形が正しいことは、結局は「同値関係としての置換が可能であること」に帰着する。反射・対称・推移の性質は、計算過程で局所的な置換を積み上げると全体として矛盾が起きないことを保証する。
加えて、演算が合同に関して整合すること（同じ剰余類の代表から作った結果が一意に決まること）が、式変形の“閉じた世界”を作る。こうした意味で、合同は単なる記号ではなく、論理の一貫性を支える枠組みとして働く。
4.3.2 同値性の利用手順
同値性を利用する実務的な手順は、次のように整理できる。
- 問題で固定されている法を確認する。
- 置換したい各項が同じ法で合同であることを確かめる。
- 合同の演算規則に従って式を変形する。
- 最後に標準代表の範囲へ正規化し、解答形式に合わせる。
この流れに従うことで、計算途中の整理が最終結果の意味を保つ。