整数の合同
合同算術は整数の算術体系を、特定の値に決められた「法(ほう)」を用いて修正したものである。
一つの例として、アナログ時計の針の指し示す時刻の「足し算」を記述する「時計算」を挙げる。具体的に、9時をスタートとして4時間を加えると、普通にいえば13時になるはずだが、実際には1時とも言う。同様に、0時をスタートとして7時間の3倍経つと21時であるが、9時とも言う。
基本的に 12 に到達するごとに 0 に戻るのであって、これは法 12 で考えているということになる。先の例では 9 と 21 は法 12 に関して合同であると言う。より一般に 9, 21, 33, 45, ...etc. は法 12 のもとで等しいものと考える。
文字盤に任意個数の整数の書かれた時計を想像すれば、一般化は容易であり、計算もできる。
Z/nZ に乗法が定まるから、反復乗法としての冪を考察するのはまた自然である。剰余は n − 1 種類しかないのだから、自然数冪 a の値もその n − 1 種類以外に取り得ず、何度も同じ値を取らねばならない。つまり、自然数 k および m でa および a が法 n に関して同じ値となるようなものが存在する。冪 a は再帰的に定められるから、剰余の値が既知のものとなれば直ちに、それ以降の値は循環的に同じ値をとるものと分かり、それ以上調べる必要は無くなる。
上記のように Z/7Z および Z/15Z での冪を書きならべてみると、前者に関してどの a に対しても7番目の a で全てが法 7 に関して 1 に合同となることが分かる。後者に関しては冪の値が 1 となることが 15 と互いに素であることに関係してくる。整数 8 は 15 と互いに素であり、15 と互いに素な a に対して a が法 15 に関して 1 と合同であることに注目せよ。
これら二つの例はそれぞれ以下の二つの定理に対応する:
フェルマーの小定理: 任意の素数 p と、 p と互いに素な整数 a に対し、a ≡ 1 (mod p);
オイラーの定理: フェルマーの小定理の拡張。2 以上の整数 n と n と互いに素な整数 a に対して、a ≡ 1 (mod n) が成り立つ。ただし、φ(n) はオイラーの φ-函数(1 から n までの整数のうち n と互いに素なものの数)である。