補題 n ≧ 1 と m ≧ 1 を有理整数とする。 d = gcd(n, m) とおく。 a を有理整数とする。
合同方程式 nx ≡ a (mod m) に解があるためには a が d で割れる ことが必要十分である。 このとき x^n = a 解の個数は d である。
証明 nb ≡ a (mod m) となる b ∈ Z があるとする。 nb - a = mk となる k ∈ Z がある。 a = nb - mk である. よって a ≡ 0 (mod d) である。
逆に a ≡ 0 (mod d) とする。 a = d(a ') と書ける。
n と m は d で割れるから n = d(n ') m = d(m ') と書ける。 よって nx ≡ a (mod m) は (n ')x ≡ a ' (mod m ') と同値である。 gcd(n ', m ') = 1 だから (n ')x ≡ a ' (mod m ') は mod m ' で唯一の解 b ' を持つ。
nx ≡ ny (mod m) なら、n(x - y) ≡ 0 (mod m) よって n '(x - y) ≡ 0 (mod m ') よって x ≡ y (mod m ')
これから nx ≡ a (mod m) の解は b ', b ' + m ', ..., b ' + (d - 1)m ' の d 個である。 証明終
