1 連立合同式の基礎
1.1 合同式と剰余の定義
整数 \(a,b\) と正の整数 \(n\) に対して、合同式 \(a \equiv b \pmod n\) は「\(n\) が \(a-b\) を割り切る」ことを意味する。これにより、整数は法 \(n\) によって同じ“扱い”になる。剰余は、ある整数 \(a\) を \(n\) で割ったときの余りに対応し、代表元として \(0\) から \(n-1\) の範囲の値が用いられることが多い。
1.2 連立の意味と解の表し方
連立合同式は、複数の合同条件を同時に課す形で与えられる。たとえば \[ x \equiv a_1 \pmod{n_1},\quad x \equiv a_2 \pmod{n_2},\quad \ldots \] のように、同じ未知数 \(x\) が各合同式をすべて満たすことを要求する。解が存在するかどうか、存在するとすればどのように全体像（個数・表現・周期性）を記述できるかが中心課題となる。
1.2.1 同値類としての解の概念
合同は等価関係を作るため、解は「特定の整数 \(x\)」だけでなく「法により同じとみなされる集合」として理解できる。つまり、条件を満たす整数は、ある周期（後述の合成された法）を持って繰り返し現れ、その繰り返し構造が同値類として表現される。
1.2.2 解の集合の記法と代表元
連立条件がある法 \(N\) のもとでまとめられる場合、解の集合は \[ x \equiv r \pmod N \] のように単一の合同式で表せることがある。このとき \(r\) は代表元であり、同値類の取り方によって \(r\) の値は変わっても集合としては同じになる。逆に、法が互いに素でない場合は、条件が一致しなければ解が存在せず、存在する場合も“幅”のある解の集合（いくつかの同値類の集まり）として記述される。
1.3 連立合同式が満たすべき条件
連立合同式の解の存在は、各合同式の整合性に強く依存する。要点は、互いに素でない法が登場するときに、同じ整数 \(x\) が共有する情報が矛盾しないかどうかである。直観的には、2つの条件が同じ“数の意味”を別々の法で制約しているため、重なるところ（最大公約数で決まる範囲）で一致していないと解は作れない。
2 解法の枠組み
2.1 中国剰余定理（互いに素な場合）
中国剰余定理は、連立合同式が最も整然と解ける代表的枠組みである。特に法 \(n_1,n_2,\ldots\) が互いに素（互いに最大公約数が 1）であるとき、解は存在し、さらに合成された法に関して一意に定まる。
2.1.1 一般形と解の一意性
互いに素な正の整数 \(n_1,\ldots,n_k\) と整数 \(a_1,\ldots,a_k\) に対して、連立 \[ x \equiv a_i \pmod{n_i}\quad (i=1,\ldots,k) \] は解を持ち、総法 \(N=n_1n_2\cdots n_k\) のもとで \[ x \equiv r \pmod N \] となる唯一の同値類が得られる。ここで“唯一”とは、総法 \(N\) を法として合同な範囲で同じ解として扱うことを指す。
2.1.1.1 構成方法（合同の合成）
具体的に解 \(r\) を構成する典型手順の一つは、各条件に対応する寄与を重ねる方法である。総法 \(N\) に対し \(N_i=N/n_i\) を作り、さらに \(N_i\) が法 \(n_i\) のもとで逆元を持つことを利用する（互いに素性がこれを保証する）。逆元を用いて \[ r=\sum_{i=1}^{k} a_i\,N_i\,t_i \] の形にまとめ、各項が他の合同条件を壊さずに特定の条件だけを満たすよう調整することで、求める代表元が得られる。結果として、各合同式の条件を同時に満たす整数が構成できる。
2.2 法が互いに素でない場合の扱い
法が互いに素でないと、中国剰余定理の“自動的に一意”という性質は崩れる。解が存在するかどうか、存在するときに解がいくつの同値類に分かれるかは、合同条件間の整合性で決まる。
2.2.1 整合条件（矛盾の見分け方）
2本の合同 \[ x \equiv a \pmod m,\quad x \equiv b \pmod n \] を考える。解が存在するための必要十分条件は、\(a\) と \(b\) が最大公約数 \(d=\gcd(m,n)\) のもとで一致することである。すなわち \[ a \equiv b \pmod d \] が成り立つかどうかで判定できる。これは「重なり合う周期部分で要求される余りが矛盾していないこと」を形式化したものに当たる。
2.2.2 解の存在と個数の考え方
整合条件が満たされるとき、解は存在し、一般に総法を \( \operatorname{lcm}(m,n)\) とした合同式の形で整理できる。具体的には、合同条件の両方を満たす解は無限個あるが、法 \(\operatorname{lcm}(m,n)\) のもとで有限個の同値類に対応する。2本の場合は、条件が整合していれば解は一つの同値類としてまとまることが多いが、多数の合同では“どの部分が自由度を持つか”に応じて同値類の数が決まる。設計上のポイントは「どの法の共通部分が矛盾を生むか」を追跡することにある。
2.3 非線形な場合への拡張の見通し
連立合同式の基本形は線形（未知数の一次）であるが、拡張として二次・高次の合同方程式や、合同条件が積や指数を含む場合に一般化する研究がある。ただし非線形領域では、解の存在・個数・構成の難度が大きく変わる。線形の場合に強く働く“逆元による合成”が機能しにくくなるため、追加の数学的道具が必要になり、解集合の形も単純な合同の形に限られない可能性がある。
3 典型的な計算手順
3.1 逐次的に合同を統合する方法
複数の合同を一度にまとめるより、2本ずつ統合していく方法が実務的である。統合した結果は新しい合同条件として次の段階へ渡され、順番に“条件を蓄積”させる。
3.1.1 2本の合同式から始める手順
まず \[ x \equiv a_1 \pmod{n_1},\quad x \equiv a_2 \pmod{n_2} \] を扱い、整合条件（互いに素か否か、最大公約数による判定）に基づいて統合する。互いに素なら一つの総法のもとで代表元が決まり、そうでなければ整合が取れている範囲で総法 \(\operatorname{lcm}(n_1,n_2)\) に対する合同へ整理する。得られた統合結果を \[ x \equiv a \pmod N \] の形にし、残りの合同式と同様に結合していく。
3.1.2 中間結果を用いた更新
逐次統合では、各ステップで現在の“まとめた条件”を新しい \(x \equiv a \pmod N\) として更新する。更新の際には、次の合同 \(x \equiv b \pmod m\) と組み合わせ、前と同じ整合条件と構成（もしくは逆元利用）を繰り返す。計算量は法の大きさや合同の本数に依存し、実装では途中で扱う数値の肥大を抑えるよう代表元を適切に正規化することが多い。
3.2 具体例による解法の流れ
ここでは、計算の雰囲気をつかむために、互いに素な場合と互いに素でない場合を分けて示す。
3.2.1 互いに素な法の例
たとえば \[ x \equiv 2 \pmod 3,\quad x \equiv 3 \pmod 5 \] を考える。総法は \(N=15\)。ここでは \(N_1=5, N_2=3\) を用い、各法に対する逆元を決めれば、解の代表元 \(r\) が計算できる。得られた \(r\) は \(x\equiv r\pmod{15}\) を満たし、元の2条件も同時に満たす。解が一意な同値類として定まる点が、このケースの特徴である。
3.2.2 互いに素でない法の例
例えば \[ x \equiv 1 \pmod 4,\quad x \equiv 3 \pmod 6 \] では \(d=\gcd(4,6)=2\)。整合条件 \(1 \equiv 3 \pmod 2\) を見ると、どちらも余りは 1 と 1 に対応し一致しているため解は存在する。こうして統合すると、\(x\) は \(\operatorname{lcm}(4,6)=12\) のもとで特定の同値類として表せる。逆に、例えば \(x \equiv 0 \pmod 4\) と \(x \equiv 1 \pmod 6\) のように \(d\) のもとで一致しない場合は、連立全体は矛盾して解を持たない。
3.3 答えの検算と検証
手計算でも計算機でも、最後に検算することで誤りを減らせる。検算は「各法に対する剰余が要求通りか」「同値類としての整合が取れているか」の2点に分けると効率的である。
3.3.1 法に対する剰余の確認
求めた代表元 \(r\) について、各合同式 \(x \equiv a_i \pmod{n_i}\) に対し \(r\) を \(n_i\) で割った余りが \(a_i\) に一致するかを確認する。互いに素でない場合は、整合条件が効いていることも同時に再確認できる。
3.3.2 解の同値性の確認
さらに、総法 \(N\)（あるいは逐次統合で得た \(\operatorname{lcm}\)）に対して、同値類として一致していることを確かめる。代表元の取り方によって値は変わり得るため、\((r-r')\) が総法を割り切るかという形で比較すると検証が容易になる。これにより、計算上の取り違えを検出できる。
4 応用と関連事項
4.1 RSA暗号などへの導入的な関わり
RSA暗号では、法が複合数であることに起因して、合同式の考え方が背後で働く場面がある。特に、秘密鍵に関わる計算では中国剰余的な分解が利用されることが多く、モジュロ冪演算を小さな法のもとへ分けて再合成することで効率が上がる。連立合同式は、その“分解して整合させる”という発想を数学的に支える基盤の一つといえる。
4.2 応用のための計算効率
実装面では、巨大な法に対する直接計算を避け、部分ごとに処理してから合成することが効く。逐次統合は途中計算の設計次第で高速化が可能であり、代表元を適切に調整することで数の桁数を抑えられる。加えて、互いに素性や最大公約数による判定を事前に行うことで、失敗（解が存在しない場合）を早期に検出できる。
4.3 整数論の関連テーマ
連立合同式は、ユークリッドの互除法や最大公約数の性質、合同と逆元の概念と強く結びつく。特に、逆元が存在するかどうかは最大公約数で決まり、これは線形合同を解く基本動力になる。
4.3.1 拡張ユークリッドの互除法
拡張ユークリッドの互除法は、\(\gcd(a,b)\) だけでなく、係数を用いたベズーの等式 \[ ax+by=\gcd(a,b) \] を同時に見つける手続きである。この係数が、ある法における逆元の計算に直結する。互いに素な状況では \(\gcd(a,b)=1\) となるため、合同方程式を解く際に必要な“逆数”が得られる。
4.3.2 最大公約数と合同の関係
最大公約数は、合同が一致するかどうかを判定するための指標として現れる。特に、解が存在するための条件は \(\gcd(m,n)\) を法とした合同に還元されることがある。したがって、最大公約数の計算は単なる補助ではなく、整合性判定や解構成の起点として位置づけられる。