整数全体を自然数 m で割った余りで分類すると m 種類に分かれる．この分類は日常生活でもしばしば用いられる．たとえば，曜日は 7 による割り算の余りで計算される．
２つの整数 a, b の差 a - b がm で割り切れるとき，a と b とは m を法として 合同であるといい，記号では，a ≡ b mod (m) で表す．この記号は ガウスによる．別の言い方をすれば，a ≡ b mod (m) ということは a, b を m で割った余りが一致するということである．式 a ≡ b mod (m) を 合同式という．
命題 1 整数 Z において，m を法として合同ということは同値関係である．
合同式は等式と同様な性質をもっている．
命題 2 a ≡ b mod (m) および a' ≡ b' mod (m) のとき，合同式
系 f(x) を整数係数の多項式とするとき，a ≡ b mod (m) であれば，合同式
f(a) ≡ f(b) mod (m) が成立する．
問題 1 自然数 a を 10 進法で anan-1... a0 と表したとき， an + ... + a0 ≡ 0 mod (3) ならば，a ≡ 0 mod (3) である．
解答 10 ≡ 1 mod (3) だから，任意の k について，10k ≡ 1 mod (3) であり，
an10n + ... + a110 + a0 ≡ an + ... + a1 + a0 mod (3)
が成立する．
問題 2 ある年の 10 月 1 日は水曜日であった．この年の 4 月 1 日の曜日を計算せよ．
ax ≡ b mod (m)
はいつ解をもつのであろうか．まず，a と m が互いに素なときを考えてみよう．
命題 3 GCD(a,m)=1 のとき，任意の b について，1 次合同式
ax ≡ b mod (m)
は解をもつ．１つの解を x0 とすれば，解全体は {x0 + nm | n ∈ Z } で与えられる．
系 p が素数のとき，p が a を割らなければ，1 次合同式 ax ≡ b mod (p) には解が存在する．
一般の場合，解をもつ条件は次のようになる．
定理 4 GCD(a,m) = d のとき，1 次合同式
ax ≡ b mod (m)
が解をもつ必要十分条件は d | b である．また，d | b の場合，m = dm0 とし，１つの解を x0 とすれば，解全体は {x0 + nm0 | n ∈ Z } で与えられる．
問題 3 (フェルマーの小定理) 素数 p が与えられたとき，p で割れない自然数 a に対して，合同式
ap-1 ≡ 1 mod (p)
が成立する．
４世紀頃の中国の数学書「孫子算経」には次のような問題とその解法が記されているという．個数のわからない物があり，3 で割ると 2 余り，5 で割ると 3 余り，7 で割ると 2 余るという，このとき，個数を求めよ．これは次の連立１次合同式の解を求めることと同値である．
| x ≡ 2 mod (3) | (1) |
| x ≡ 3 mod (5) | (2) |
| x ≡ 2 mod (7) | (3) |
素朴に考えてみよう．(1) の解は ...,2,5,8,11,14,17,20,23,... であり，(2) の解は ...,3,8,13,18,23,... であり，(3)の解は ...,2,9,16,23,...
である．したがって，23 が１つの解であることがわかる．一般的な問題と解法は次のようになる．
定理 5 (中国剰余定理) どの２つも互いに素な自然数 m1 ,...,mr が与えられたとき，連立合同式
| x ≡ b1 mod (m1) |
| x ≡ b2 mod (m2) |
| .... |
| x ≡ bn mod (mr) |
には解が存在し，１つの解を x0 とすれば，解全体は {x0 + nΠi mi | n ∈Z } で与えられる．
問題 4 200 以下の自然数のうち，3 で割れば 2 余り，4 で割れば 1 余り，5 で割れば 3 余る数をすべて求めよ．
解答 任意の解は 53 + 60n, {n ∈ Z} で与えられる．したがって，200 以下の自然数解は 53,113,173 の 3 個である．