整数の合同

整数の合同（ごうどう、）は、数学において二つの整数の間に定められる関係である。初めてこれを構造として研究したのはドイツの数学者ガウスで、1801年に発表された著書『Disquisitiones Arithmeticae』でも扱われている。今日では整数の合同は、数論や一般代数学あるいは暗号理論などに広く用いられる。
整数の合同に基づく数学の分野は合同算術 (modular arithmetic) と呼ばれる。これは整数そのものを直接的に扱うのではなく、何らかの整数（法と呼ばれる、以下本項では で表す）で割った剰余を代表元として扱う算術である。合同算術の歴史や道具立てあるいはその応用については合同算術の項を参照。また、より包括的で堅苦しくない説明は剰余類環 () の項へ譲る。
直観的な例：時計算.
合同算術は整数の算術体系を、特定の値に決められた「法」を用いて修正したものである。
一つの例として、アナログ時計の針の指し示す時刻の「足し算」を記述する「時計算」を挙げる。具体的に、9時をスタートとして4時間を加えると、普通にいえば13時になるはずだが、実際には1時とも言う。同様に、0時をスタートとして7時間の3倍経つと21時であるが、9時とも言う。
基本的に に到達するごとに に戻るのであって、これは法 で考えているということになる。先の例では と は法 に関して合同であると言う。より一般に etc. は法 のもとで等しいものと考える。
文字盤に任意個数の整数の書かれた時計を想像すれば、一般化は容易であり、計算もできる。
法 に関する合同.
定義.
 が 以上の整数として、「二つの整数 が法 に関して合同である」とは、以下の同値な条件のいずれか（したがってすべて）を満足する場合を指す:
記法.
二つの整数が合同であることを表すのに が記号として用いられる。
 と とが法 に関して合同であることを表すのに、以下のような表記がある。
どれも同様に「 と とは法 に関して合同である」などと読む。法が であることは「 を法として」「法 のもとで」「法 で」「mod で」などと適宜表現される。前後関係から法 が明らかな場合は法の表記を省略して単に と表記されることがある。
性質.
同値律.
法 に関する合同という関係は以下の性質を満たす:
即ち法 に関する合同という関係は同値関係である。
代数学的性質.
特に踏まえておくべき代数学的性質は、 かつ ならば
が成り立つことである。ここから ならば任意の整数 に対して および であること、および正整数 に対して であることが容易に導ける。
これは法 に関する合同関係がある意味で整数の加法および乗法と「両立する」ことを示すものであり、「法 に関する合同は有理整数環 の構造と両立する」と言い表す。これにより商集合 に合同算術の環を定義することができるようになる。
合同類環.
構成.
先述の代数的性質は、法 に関する加法と乗法において、加えたり掛けたりする数を法 で合同な別の数に置き換えてもよいことを示している。これはつまり、法 で合同な数すべてを一つのあつまり（同値類、合同類、剰余類）として扱えば、法 に関する加法と乗法がこの類の代表元の取り方に依らずに定まるということになる。同じ類に属する整数は法 で割った剰余がみな同じであるようなものたちであり、法 で割った剰余のみに注目するのが自然である。つまり、集合 あるいは を法 で割った余りからなる -元集合 （あるいは単に とも書く）として、加法と乗法をこの集合上で考えるのがよい。この集合を法 に関する合同類環、剰余環あるいは商環と呼ぶ。 
この集合上での加法と乗法は、整数に関する加法と乗法と同様に定義される:
法 に関する加法と乗法を以下のような表にまとめることができる:
これら加法と乗法は、整数の集合 における加法と乗法に良く似た性質を持つ:
これらの性質を満足する集合は（単位的）環と呼ばれる。
簡約と合同方程式.
 では常に正当であるにも拘らず、合同類環 では必ずしも正当化されない操作の一つに、簡約（消約）がある。
同様に、整数の演算では常に成り立っているのに 上では必ずしも成り立たない性質として、「積が に等しいならばいずれかの数が に等しい」というものがある。
こういった理由により、乗法を含む方程式を解くのは少々厄介である。
 の方程式 が 上で一意な解を持つための必要十分条件は、 と とが互いに素であることである。
 の形の方程式の解は および の値に依存して 0 個、1 個、2 個の何れかになる。さらに詳細な結果が平方剰余の研究によって得られており、平方剰余の相互法則として知られている。
合同類環 の構成は環のイデアルによる商構成である。環 の代数的性質に関しては合同類環の項へ譲る。
冪とフェルマーの小定理.
 に乗法が定まるから、反復乗法としての冪を考察するのはまた自然である。剰余は 種類しかないのだから、自然数冪 の値もその 種類以外に取り得ず、何度も同じ値を取らねばならない。つまり、自然数 および で および が法 に関して同じ値となるようなものが存在する。冪 は再帰的に定められるから、剰余の値が既知のものとなれば直ちに、それ以降の値は循環的に同じ値をとるものと分かり、それ以上調べる必要は無くなる。
上記のように および での冪を書きならべてみると、前者に関してどの に対しても7番目の で全てが法 に関して に合同となることが分かる。後者に関しては冪の値が となることが と互いに素であることに関係してくる。整数 は と互いに素であり、 と互いに素な に対して が法 に関して と合同であることに注目せよ。
これら二つの例はそれぞれ以下の二つの定理に対応する: