1 合同算術の基本概念
1.1 合同の定義と同値関係
合同算術では、整数 \(a,b\) が「ある数 \(m\) で割った余りが同じ」であることを基準に整理する。通常、\(m\neq 0\) とし、\(m\) による合同は \(a\equiv b \pmod{m}\) の形で表す。このとき定義は \[ a\equiv b \pmod{m}\iff m\mid(a-b) \] である。ここで \(m\mid(a-b)\) は \(a-b\) が \(m\) で割り切れることを意味する。
この関係は同値関係として扱える。すなわち、任意の整数に対して反射性が成り立ち、入れ替えても成り立つ対称性があり、さらに同じ法のもとでの一致が連鎖する推移性がある。したがって合同は「同じ余りを共有する対象の集まり」を作る装置として機能する。
1.2 法と剰余の見方
「法（modulus）\(\,m\)」は、余りによる区別の粒度を決めるパラメータである。一般に \(m\) を固定すると、整数全体は互いに交わらないいくつかの同値類に分割される。これにより計算では、各整数をその同値類の代表元として取り扱える。
剰余の見方としては、任意の整数 \(a\) は \(a=qm+r\)（整数 \(q\)、余り \(r\)）と一意に分解でき、合同 \(a\equiv r\pmod m\) と表される。余り \(r\) を範囲 \(0\) から \(m-1\) のように選ぶことで、代表元を体系的に決めることが多い。
1.3 合同の性質
合同の基本性質は、合同が「同じ余りに関する一致」を保つことから導かれる。とくに、合同のもとでの演算（加算・減算・乗算）が余りの規則と整合する点が中心的である。
1.3.1 加法に関する両立性
\(a\equiv b\pmod m\) かつ \(c\equiv d\pmod m\) が成り立つとき、 \[ a+c\equiv b+d\pmod m \] が得られる。証明は差の割り切れに注目すればよい。合同から \(m\mid(a-b)\) と \(m\mid(c-d)\) が従うので、和に対して \[ (a+c)-(b+d)=(a-b)+(c-d) \] が \(m\) で割り切れることが示される。減算についても同様に、\(a-c\) と \(b-d\) の差が同じように \(m\) で割り切れる。
1.3.2 乗法に関する両立性
同様の両立性は乗法にも拡張される。すなわち \[ a\equiv b\pmod m,\quad c\equiv d\pmod m \] ならば \[ ac\equiv bd\pmod m \] が成り立つ。理由は \[ ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b) \] の形に変形でき、ここで \(m\mid(a-b)\)、\(m\mid(c-d)\) があるため、全体が \(m\) で割り切れることによって従う。
これらの両立性により、合同は単なる記法ではなく「余りに関する計算ルール」として働く。
1.3.3 合同の推移性・対称性・反射性
同値関係としての性質は、合同が数学的に扱いやすい枠組みを与える。
- 反射性：任意の整数 \(a\) について \(a\equiv a\pmod m\)。これは \(m\mid(a-a)=0\) による。
- 対称性：\(a\equiv b\pmod m\) なら \(b\equiv a\pmod m\)。差 \(a-b\) の符号を反転しても割り切れは変わらないためである。
- 推移性：\(a\equiv b\pmod m\) かつ \(b\equiv c\pmod m\) なら \(a\equiv c\pmod m\)。差の和の形で \(a-c=(a-b)+(b-c)\) を用いれば、割り切れが連鎖する。
これにより、合同は「余りの一致」という直観を厳密に実装した関係になる。
2 剰余環としての合同算術
2.1 剰余類の構成
2.1.1 法 m の剰余類
整数 \(m\neq 0\) を固定し、合同 \(a\equiv b\pmod m\) によって定まる同値類を考える。整数 \(a\) が属する剰余類を \[ [a]=\{\,a+km\mid k\in\mathbb Z\,\} \] のように表すと、剰余類どうしは交わらず、整数全体を分割する。特に、代表元の選び方によって同じ剰余類を表すことが許される。
2.1.1.1 0を含む代表元の扱い
剰余類を具体的な要素として扱う際、代表元を余りの範囲に制限することが多い。典型例として、各剰余類には \(0\) から \(m-1\) までのいずれかの整数がちょうど一つ対応するように選ぶ。たとえば \(m>0\) のとき、任意の整数 \(a\) は \(a=qm+r\)（\(0\le r<m\)）を満たし、剰余類 \([a]\) は \([r]\) と一致する。この \(r\) は「余りとしての代表」であり、計算を簡潔にする。
なお、集合としての剰余類には \(0\) を含む場合がある。たとえば \([0]=\{km\mid k\in\mathbb Z\}\) は \(m\) の倍数全体から成り、零剰余類として特別な役割を持つ。
2.2 剰余環の演算規則
剰余類の集合上で演算を定義する。例えば剰余類 \([a]\) と \([b]\) に対して
- 加算：\([a]+[b]=[a+b]\)
- 乗算：\([a]\cdot[b]=[ab]\)
と定める。ここで重要なのは、代表元の取り替えによって結果が変わらないこと、すなわち演算が「well-defined」である点である。合同の両立性により、もし \(a\equiv a'\pmod m\) と \(b\equiv b'\pmod m\) が成り立っていれば \([a+b]=[a'+b']\) および \([ab]=[a'b']\) が従う。
この構造により、剰余類は「環」として振る舞う。通常は \(\mathbb Z/m\mathbb Z\) の形で表され、整数の合同算術はこの環での計算と同一視できる。
2.3 可換性・単位元・零元
剰余環 \(\mathbb Z/m\mathbb Z\) では基本的な性質が保たれる。整数の加法・乗法が可換であるため、剰余類の演算でも可換性が成り立つ。加法については零元が \([0]\) であり、任意の \([a]\) に対して \([a]+[0]=[a]\) が成立する。
乗法については単位元（恒等元）が \([1]\) である。つまり \([a]\cdot[1]=[a]\) が成り立つ。もっとも、これは常に「割り算が可能」を意味するわけではない。乗法の可逆性、すなわち単位元（可逆元）を持つかどうかは、次節で扱う「可逆元」の条件と関係する。
3 合同方程式と解法
3.1 一次合同方程式
3.1.1 線形合同の基本形
一次合同方程式は典型的に \[ ax\equiv b\pmod m \] の形をとる。ここで未知数 \(x\) は剰余類として扱い、解とは \(\mathbb Z/m\mathbb Z\) 上でこの条件を満たすものを指す。
この種の方程式では、整数の互いに割り切れる関係が本質になる。一般には \(a\) と \(m\) の最大公約数が鍵となり、方程式の可解性と解の個数がそこから決まる。
3.2 互除法との関係
3.2.1 最大公約数による解の判定
\(d=\gcd(a,m)\) とすると、合同方程式 \[ ax\equiv b\pmod m \] が解を持つための条件は \(d\mid b\) である。直観的には、左辺 \(ax\) は \(d\) を因子に必ず含み、そのため右辺 \(b\) も同じ因子条件を満たさないと余りとして一致できない。
この判定は、拡張ユークリッド互除法（互除法の改良版）により具体的に解く際に重要になる。拡張互除法は \(a\) と \(m\) の間のベズー係数を与え、\(d\) を用いて方程式を簡約できる。解の構成は、まず \(d\) で割り、残りの部分で逆元（可逆性）を利用する流れになることが多い。
3.3 解の個数と一般解
3.3.1 解が存在する条件
解の存在条件は上で述べた \(d\mid b\) によって与えられる。これが成り立たない場合、合同としての一致は起こりえないので、解集合は空集合となる。
逆に \(d\mid b\) が成り立つ場合、解が存在する。さらに、同値類として数えるため、特定の解が見つかれば全体の解構造も規則的に得られる。
3.3.2 解集合の整理
\(d=\gcd(a,m)\) とし、\(d\mid b\) を仮定する。すると方程式の解は剰余類の中で有限個あり、その個数は \(d\) に等しい。具体的には、ある一つの解 \(x_0\) を得たとき、解全体は \[ x\equiv x_0+\frac{m}{d}t\pmod m\quad (t\in\mathbb Z) \] の形で表される。ここで \(t\) を変えると剰余類が異なる範囲を巡り、合計でちょうど \(d\) 通りの解が得られる。
一般解の整理は、可逆元や簡約後の逆元計算を組み合わせることで実行できる。これにより、合同方程式は「線形方程式のように扱える」状態になる。
4 合同算術の発展的話題
4.1 可逆元と割り算の条件
剰余環 \(\mathbb Z/m\mathbb Z\) での「割り算」は、乗法に関して逆元が存在する場合に限られる。剰余類 \([a]\) が可逆（逆元を持つ）である条件は \[ \gcd(a,m)=1 \] である。これは \(a\) が \(m\) と互いに素であることを意味し、その場合に限ってある \([u]\) が存在して \([a]\cdot[u]=[1]\) が成立する。
逆元が存在すれば、合同方程式 \(ax\equiv b\pmod m\) は両辺に逆元を掛けて \(x\equiv a^{-1}b\pmod m\) と解ける。したがって実務的には、互いに素判定と拡張互除法による逆元計算が中心手順となる。
4.2 中国剰余定理の考え方
中国剰余定理（CRT）は、互いに素な法のもとでの合同を別々に解き、それらをまとめて一つの合同解に復元できるという枠組みである。たとえば \(m_1,m_2\) が互いに素なら、方程式 \[ x\equiv a\pmod{m_1},\qquad x\equiv b\pmod{m_2} \] は、法 \(m_1m_2\) のもとで一意な解を持つ（剰余類として）。
この考え方の利点は、難しい合同問題を小さな部分問題に分解し、結果を合成できる点にある。合成は、解の整合性が互いに素性によって保証されるため、構成手順が規則的に決まる。
4.3 オイラー関数・フェルマー型の合同
オイラー関数 \(\varphi(m)\) は、\(1\) から \(m\) までの整数のうち \(m\) と互いに素なものの個数を表す。合同算術の発展では、可逆元の性質と結びつけて指数に関する合同が現れる。
オイラーの定理は、\(\gcd(a,m)=1\) のとき \[ a^{\varphi(m)}\equiv 1\pmod m \] を与える。ここから指数を扱うフェルマー型の合同が導かれ、素数の場合には \(\varphi(p)=p-1\) を用いて簡潔な形になることが多い。これらは累乗の合同を高速に理解するための基礎となり、計算量の見積もりや指数合同の整合性に関わる。
4.4 応用例（暗号・符号化のための合同）
合同算術は暗号や符号化の理論で頻繁に現れる。理由は、剰余環上での可逆性、指数合同、そして中国剰余定理のような「分解と再構成」の性質が、数学的な制約を設計に反映しやすいからである。
一例として、公開鍵暗号の多くは「指数計算による写像」を利用し、その性質をオイラー関数や特定の合同定理で保証する。さらに、CRTを用いると大きな法の計算を分割して小さな計算に置き換えられる場合があり、実装面での高速化につながる。符号化では、合同により候補値の整合性条件をチェックしたり、復元手続きを剰余の体系に埋め込んだりする場面がある。