定義

n が 2 以上の整数として、「二つの整数 a, b が法 n に関して合同である」とは、以下の同値な条件のいずれか（したがってすべて）を満足する場合を指す:

1. それらの差が n で整除される（つまり、適当な整数 k が存在して a – b = kn）;
2. a を n で割った剰余 r が b を n で割った剰余 s と等しい;
3. a – b ∈ nZ（つまり、 a – b が n の倍数全体の成すイデアル nZ の要素になる）

記法

二つの整数が合同であることを表すのに ≡ が記号として用いられる。

a と b とが法 n に関して合同であることを表すのに、以下のような表記がある。

a ≡ b (modulo n)

a ≡ b (mod. n)

a ≡ b (mod n)

a ≡ b mod n

a ≡ b (n)

a ≡ b [n]

a ≡_n b

a ≡ b

どれも同様に「a と b とは法 n に関して合同である」などと読む。法が n であることは「n を法として」「法 n のもとで」「法 n で」「mod n で」などと適宜表現される。前後関係から法 n が明らかな場合は法の表記を省略して単に a ≡ b と表記されることがある。

性質

構成

先述の代数的性質は、法 n に関する加法と乗法において、加えたり掛けたりする数を法 n で合同な別の数に置き換えてもよいことを示している。これはつまり、法 n で合同な数すべてを一つのあつまり（同値類、合同類、剰余類）として扱えば、法 n に関する加法と乗法がこの類の代表元の取り方に依らずに定まるということになる。同じ類に属する整数は法 n で割った剰余がみな同じであるようなものたちであり、法 n で割った剰余のみに注目するのが自然である。つまり、集合 Z_n あるいは Z/nZ を法 n で割った余りからなる n-元集合 { 1, 2, …, n − 1 } （あるいは単に 1, 2, …, n − 1} とも書く）として、加法と乗法をこの集合上で考えるのがよい。この集合を法 n に関する合同類環、剰余環^{[注釈 2]}あるいは商環^{[注釈 3]}と呼ぶ。

この集合上での加法と乗法は、整数に関する加法と乗法と同様に定義される:

• 加法: 二つの剰余類 a, b に対して剰余類 a + b modulo n を割り当てる。理論的には整数の加法と異なる和であるから別の記号で表すべきであるかもしれないが、簡便さを保つために整数の和と同じ記号 "+" をそのまま使うことも多い。
  • 例えば法 6 に関する合同類環では 3 + 2 = 5 が整数の加法同様に成り立つが、4 + 2 は 6 で割った剰余が 0 に等しいから 4 + 2 = 0 が成り立つ。
• 乗法: 二つの剰余類 a, b に対し、剰余類 a × b modulo n を割り当てる。これも同様に整数の乗算記号"×"をそのまま流用する。
  • 法 6 に関する合同類環では、整数の乗法同様に 2 × 2 = 4 が成り立つが、2 × 5 = 4（2 × 5 を 6 で割った剰余は 4 に等しい）や 2 × 3 = 0 などが成り立つ。

法 6 に関する加法と乗法を以下のような表にまとめることができる:

これら加法と乗法は、整数の集合 Z における加法と乗法に良く似た性質を持つ:

• 加法は可換（足す順番を入れ替えられる）、結合的（三項の和は前二項を先に足してもあと二項を先に対しても結果は変わらない）で、単位元を持つ（0 を加えても変わらない）、各元が反数を持つ。
  • Z の加法と比べて異なる点もある。Z の加法では a の逆元 –a は a + (–a) = 0 を満たす元だが、法 n の合同類環では a + (n – a) = 0（a と n − a の和を n で割った剰余は 0）だから a の逆元は n – a である。ただし、法 n に関する合同において –a と n – a は同じ類に入る。–a でなく n – a を選ぶのは、合同類の代表元を 0 から n − 1 の間の整数から常に選ぶことができるという利点があるからである。
• 乗法も可換、結合的で、単位元を持つ（1 を掛けても変わらない）。また剰余類の加法に関して分配的である。

これらの性質を満足する集合は（単位的）環と呼ばれる。

簡約と合同方程式

Z では常に正当であるにも拘らず、合同類環 Z/nZ では必ずしも正当化されない操作の一つに、簡約（消約）がある。

• 実際、等式 2a = 4 を Z で考えれば明らかに両辺を 2 で簡約して a = 2 が得られるが、法 6 で考えれば 2a = 4 は 2a を 6 で割った剰余が 4 であるということだから、a は 3 で割った剰余が 2 に等しいような類である。そのような a は 6 で割った剰余類の中では類 2 または類 5 が満たす。従って、2×2 ≡ 2×5 だがそれを簡約した 2 ≡ 5 は成立しない。

同様に、整数の演算では常に成り立っているのに Z/nZ 上では必ずしも成り立たない性質として、零積性質（英語版）「積が 0 に等しいならばいずれかの数が 0 に等しい」というものがある。

• 実際、法 6 で 2 × 3 ≡ 0 だが 2 も 3 も 0 でない。つまり、環 Z/6Z は整域でない。

こういった理由により、乗法を含む方程式を解くのは少々厄介である。

• 方程式 x + 2 = 1 を Z/6Z 上で考えるなら、両辺に同じ量 4 を加えて x = 5 とすればよい (2 + 4 ≡ 0 [6] に注意);
• 方程式 3x = 2 を Z/10Z 上で考えるとき、7 × 3 ≡ 1 に注意すれば 3x = 2 と x = 7 × 2 が同値であることが分かる（一方から他方へはそれぞれ両辺に 7 あるいは 3 を掛ければ変形できる）。故に方程式の解は 4（7 × 2 を 10 で割った剰余は 4）である。;
• 方程式 2x = 3 は Z/10Z 上で解を持たない。また方程式 2x = 6 は二つの解 (3 と 8) を持つ。

未知数（フランス語版） x の方程式 ax = b が Z/nZ 上で一意な解を持つための必要十分条件は、a と n とが互いに素であることである。

x² ≡ a (mod n) の形の方程式の解は a および n の値に依存して 0 個、1 個、2 個の何れかになる。さらに詳細な結果が平方剰余の研究によって得られており、平方剰余の相互法則として知られている。

合同類環 Z/nZ の構成は環のイデアルによる商構成である。環 Z/nZ の代数的性質に関しては合同類環の項へ譲る。

冪とフェルマーの小定理

Z/nZ に乗法が定まるから、反復乗法としての冪を考察するのはまた自然である。剰余は n − 1 種類しかないのだから、自然数冪 a^k の値もその n − 1 種類以外に取り得ず、何度も同じ値を取らねばならない。つまり、自然数 k および m でa^k および a^m が法 n に関して同じ値となるようなものが存在する。冪 a^k は再帰的に定められるから、剰余の値が既知のものとなれば直ちに、それ以降の値は循環的に同じ値をとるものと分かり、それ以上調べる必要は無くなる。

上記のように Z/7Z および Z/15Z での冪を書きならべてみると、前者に関してどの a に対しても7番目の a⁶ で全てが法 7 に関して 1 に合同となることが分かる。後者に関しては冪の値が 1 となることが 15 と互いに素であることに関係してくる。整数 8 は 15 と互いに素であり、15 と互いに素な a に対して a⁸ が法 15 に関して 1 と合同であることに注目せよ。

これら二つの例はそれぞれ以下の二つの定理に対応する:

• フェルマーの小定理: 任意の素数 p と、 p と互いに素な整数 a に対し、a^p−1 ≡ 1 (mod p);
• オイラーの定理: フェルマーの小定理の拡張。2 以上の整数 n と n と互いに素な整数 a に対して、a^φ(n) ≡ 1 (mod n) が成り立つ。ただし、φ(n) はオイラーの φ-函数（1 から n までの整数のうち n と互いに素なものの数）である。

注釈