初等整数論/フェルマーの小定理 で、フェルマーの小定理を用いて、素数を法とする剰余類の構造を調べたので、次に、一般の自然数を法とする合同式について考えたい。まず、素数の冪を法とする場合について考え、次に一般の法について考える。
p^e を法とする剰余類は 0, 1, \ldots, p^e-1 の p^e 個ある。
\gcd(a, p)=1 ならば \gcd(a, p^e)=1 である。よってこのとき任意の b\pmod{p^e} に対し ax\equiv b\pmod{p^e} となる x\pmod{p^e} が一意的に定まる。このような剰余類 a\pmod{p^e} は bp+r, 0\leq b\leq p^{e-1}-1, 1\leq r\leq p-1 の形に一意的に書けるから、ちょうど p^{e-1}(p-1) 個存在する。
一方、a が p の倍数の場合、ax\equiv b\pmod{p^e} となる x\pmod{p^e} が存在するかも定かでない。例えば 2x\equiv 3\pmod{4}, 9x\equiv 3\pmod{27} などは解を持たない。
a=sp^f, b=tp^g, \gcd(s, p)=\gcd(t, p)=1 とおくと ax\equiv b\pmod{p^e} \iff sp^f x\equiv tp^g\pmod{p^e} である。ここで、つぎの3つの場合に分かれる。
1. g\geq e のとき
b\equiv 0\pmod{p^e}  よりこの合同式はすべての剰余類を解に持つ。
2. e, f>g のとき
 つまり sp^{f-g}x-t\equiv 0\pmod{p^e} であるが f>g, \gcd(t, p)=1 より、この合同式は解を持たない。
3. f\leq g のとき
 を解に持つ。しかし ax\equiv b\pmod{p^e} はp^e を法とする合同式である。よって、これはちょうど p^f 個の剰余類 x_0+kp^{e-f}\pmod{p^e} (k=0, 1, \ldots, p^g-1) を解に持つ。
次に、合同方程式 f(x)\equiv 0\pmod{p^e} が解を持つのはどのような場合か考える。そもそも f(x)\equiv 0\pmod{p} が解を持たなければならないことは言うまでもない。まず、正の整数 k, m に対して
より
が成り立つことから、次のことがわかる。
x=a を合同方程式 f(x)\equiv 0\pmod{p^m}  の解とする。このとき f'(a)\not\equiv 0\pmod{p} ならば
 \cdots (*)
となる a\pmod{p} がちょうど1つ定まる。
f'(a)\equiv 0\pmod{p} ならばそのような b\pmod{p} は存在しないか、
すべての b\pmod{p} に対して (*) が成り立つ。
数学的帰納法より、次の定理がすぐに導かれる。
x=a を合同方程式 f(x)\equiv 0\pmod{p}  の解とする。
e\geq 2 を整数とする。
このとき f'(a)\not\equiv 0\pmod{p} ならば
 はちょうど1つ定まる。
例 任意の素数 p と正の整数 e に対し、合同方程式 x^{p-1}\equiv 1\pmod{p^e} の解の個数は p-1 個である。より詳しく、各 a=1, 2, \ldots, p-1 に対し、x^{p-1}\equiv 1\pmod{p^e}, x\equiv a\pmod{p} となる x\pmod{p^e} が1個ずつある。
一般の合成数を法とする場合は素数冪を法とする場合に帰着される。具体的に、次のような問題を考えてみる。
問 7 で割って 6 余り、13 で割って 12 余り、19 で割って 18 余る数はいくつか?
答えは、7×13×19 - 1 である。さて、このような問題に関して、次の定理がある。
定理 (中国の剰余定理)
m_1, m_2, \cdots, m_k のどの2つをとっても互いに素であるとき、任意の整数 a_1, a_2, \cdots, a_k について、
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_k \pmod{m_k}
\end{cases}
を満たす x は m_1m_2m_3 \cdots m_k を法としてただひとつ存在する。（ここでの「ただひとつ」というのは、互いに合同なものは同じとみなすという意味である。）
証明 1
まず、k = 2 のときを証明する。
\begin{cases}
x \equiv a_1 \pmod{m_1} \ \cdots (1)\\
x \equiv a_2 \pmod{m_2} \ \cdots (2)\\
\end{cases}
(m_1, m_2) = 1 より、一次不定方程式に関する定理 1.9 より m_1u + m_2v = 1 と表せる。このとき、
\begin{cases}
m_2v \equiv 1 \pmod{m_1}  \ \cdots (3) \\
m_1u \equiv 1 \pmod{m_2} \ \cdots (4) \\
\end{cases}
となる。
x \equiv a_1m_2v + a_2m_1u \pmod{m_1m_2} とおくと、
x - a_1 = a_1(m_2v - 1) + a_2m_1u となる。(4) より、m_2v - 1 = m_1M とおけば、
x - a_1 = a_1m_1M + a_2m_1v は m_1 で割り切れる。したがって、合同の定義より方程式の (1) を満たす。また、同様に (3) を用いることで、(2) をも満たすことは容易に証明される。
よって、解が存在することが証明された。
さて、その唯一性であるが、y を任意の解とすれば、x, y \equiv a_1 \Rightarrow x \equiv y \Rightarrow x-y \equiv 0 \pmod{m_1} となる。また同様にして x-y \equiv 0 \pmod{m_2} となる。したがって合同の定義より、x-y は m_1, m_2 の公倍数。(m_1, m_2) = 1 より、x-y は m_1m_2 の倍数である。したがって x-y \equiv 0 \Rightarrow x \equiv y \pmod{m_1m_2}
となり、唯一性が保証された。
次に、定理を k に関する数学的帰納法で証明する。
(i) k = 1 のとき
x \equiv a_1 \pmod{m_1} は x = a_1 が唯一の解である（除法の原理より唯一性は保証される）。
(ii) k = n のとき成り立つと仮定する
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_n \pmod{m_n} \\
\end{cases}
最初の n の式は、帰納法の仮定によって x \equiv b \pmod{m_1m_2 \cdots m_n} なる b がただひとつ存在する。
ゆえに、
\begin{cases}
x \equiv b \pmod{m_1m_2 \cdots m_n} \\
\end{cases}
を解けば良い。仮定より、(m_1m_2 \cdots m_n, m_{n+1}) = 1 であるから、k = 2 の場合に当てはめて、この方程式を満たす x が、m_1m_2 \cdots m_nm_{n+1} を法としてただひとつ存在する。
したがって、k = n のとき成り立つならば k = n+1 のときも成り立つことが証明された。
(i)(ii) より数学的帰納法から定理が証明される。
証明 2 この証明はガウスによる。
M = m_1m_2 \cdots m_n とおき、
M = m_1M_1 = m_2M_2 = \cdots = m_nM_n
とおく。仮定より、(M_k, m_k) = 1 \ \ (k = 1, 2, \cdots , n) なので定理 1.8 から
M_kt_k \equiv 1 \pmod{m_k} なる t_k が存在する。
すると、連立合同方程式の解は、x \equiv a_1M_1t_1 + a_2M_2t_2 + \cdots + a_nM_nt_n \pmod{M} となる。なぜなら任意の 1 \leqq k \leqq n について、
M_kt_k \equiv 1 \Rightarrow a_kM_kt_k \equiv a_k \pmod{m_k} となり、他の全ての項は M_1, M_2, \cdots , M_{k-1}, M_{k+1}, \cdots , M_n の積なので m_k で割り切れる。
したがって、x \equiv a_k \pmod{x_k} となる。よって x が解である。
もちろん、各剰余類 x\pmod{m_1m_2\cdots m_k} に対し、 x\equiv x_i\pmod{m_i} となる剰余類 x_i\pmod{m_i} はただ一つ存在する。このことから
x\pmod{m_1m_2\cdots m_k} と (x_1\pmod{m_1}, x_2\pmod{m_2}, \ldots, x_k\pmod{m_k}) は 1対1 に対応していることがわかる。
特に a\equiv 1\pmod {m_1m_2\cdots m_k} は各 i に対して a\equiv 1\pmod{m_i} となることと同値である。
さて、 1より大きい整数 n を n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} と素因数分解すると、p_i^{e_i} はどの2つをとっても互いに素である。
ここで、次のことがわかる。
n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} と素因数分解すると、任意の整数 a_1, a_2, \cdots, a_k について、
 \\
 \\
\cdots \\
\end{cases}
を満たす a は n を法としてただひとつ存在する。
さらに、ここで \gcd(a, n)=1\iff \gcd(a_i, p_i^{e_i})=1 (i=1, 2, \ldots, k) が成り立つ。
 証明 
前段は中国の剰余定理を m_i=p_i^{e_i} に適用したものである。
\gcd(a_i, p_i^{e_i})>1 ならば p_i は a_i の素因数であり、そうなると
p_i は a の素因数になってしまい、 p | \gcd(a, n) となってしまう。
逆に a, n を共に割り切る素数があるとするとそれは p_i のいずれかである。そのようなものを1つ取ると
a_i\equiv a\equiv 0\pmod{p_i} より \gcd(a_i, p_i^{e_i})>1 となる。
この定理から、次のことがすぐにわかる。
n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} と素因数分解する。n を法とする既約剰余類の個数は \prod_{i=1}^k p_i^{e_i-1}(p_i-1) である。
ここで現れた
を n の オイラー関数 (Euler's totient) という。これは円分多項式の次数として現れたものである。
中国の剰余定理から、フェルマーの小定理は次のように一般化される。
a を n と互いに素な整数とすると
が成り立つ。
証明
n と互いに素な数で 1 から n-1 までのもの b_1, \ldots, b_k をとる。
中国の剰余定理から k=\varphi(n) である。
ab_i (i=1, \ldots, k) はすべて n と互いに素である。さらに、これらを p で割ったとき余りはすべて異なっている。
よって、これらは n と互いに素な数で 1 から n-1 までのものをちょうど1回ずつとる。
したがって、
である。積 b_1 b_2 \cdots b_k も n と互いに素であるから
が成り立つ。
素数を法とする場合と同様 a を n と互いに素な数とし、a^l\equiv 1\pmod{n} となる最小の正の整数 l を n を法とする a の位数と呼ぶ。
位数の法則 から
が成り立つ。これと、フェルマー・オイラーの定理から位数は \varphi(n) の約数であることがわかる（この \varphi(n) は、多くの場合、より小さな値をとる関数で置き換えられることを合成数を法とする剰余類の構造で見る）。