由于x2, ?, xk对于模p是两两不同余的，所以，上式给出
f1(xi) ? 0 (mod p)，i = 2, ?, k。 (5)
由此及归纳法，即可证明定理。证毕。 推论 若p是素数，则对于任何整数x，有
x p ? 1 ? 1 ? (x ? 1)(x ? 2)?(x ? p ? 1) (mod p)。
证明 由Fermat定理（第二章第四节定理2），数1, 2, ?, p ? 1是同余方程
x p ? 1 ? 1 (mod p)
的解，因此，利用定理1即可得证。 定理2 同余方程(1)的解数? n。
证明 假设同余方程(1)有n + 1个不同的解
x ? xi (mod p)，1 ? i ? n ? 1。
由定理1，有f(x) ? an(x ? x1)?(x ? xn) (mod p)，因此
0 ? f(xn + 1) ? an(xn + 1 ? x1)?(xn + 1 ? xn) (mod p)。 (6) |an，xn + 1?由于p??xi (mod p)，1 ? i ? n，所以式(6)不能成立。这个矛盾说明同余方程(1)不能有n ? 1个解。证毕。
推论 若同余方程bnxn ? ? ? b0 ? 0 (mod p)的解数大于n，则
p?bi，0 ? i ? n。 （7) |bd，d ? n，p?bi， d< j ? n。则 证明 若式(7)不成立，设p?bnxn ? ? ? b0 ? bdxd ? ? ? b0 ? 0 (mod p)。 (8)
由定理2，同余方程(8)的解数不大于d，因而不大于n，这与假设矛盾。因此，式(7)必成立。证毕。
定理3 同余方程(1)或者有p个解，或者存在次数不超过p ? 1的整系数多项式r(x)，使得同余方程(1)与r(x) ? 0 (mod p)等价。
证明 由多项式除法可知，存在整系数多项式g(x)与r(x)，使得
f(x) = g(x)(x p ? x) ? r(x)。 (9)
由Fermat定理，对于任意的整数x，有x p ? x (mod p)，因此，如果r(x)的系数都是p的倍数，则对于任意的整数x，f(x) ? 0 (mod p)，即同余方程(1)有p个解。如果r(x)的系数不都是p的倍数，则r(x)的次数不超过p ? 1。由式(9)看出，对于任意的整数x，f(x) ? r(x) (mod p)，即同余方程(1)与r(x) ? 0 (mod p)等价。证毕。 定理4 设n ? p，则同余方程 122
f(x) = xn ? an ? 1xn ? 1 ? ? ? a1x ? a0 ? 0 (mod p) (10)
有n个解的充要条件是存在整数多项式q(x)和r(x)，r(x)的次数< n，使得
x p ? x = f(x)q(x) ? p?r(x)。 (11)
证明 必要性 由多项式除法，存在整系数多项式q(x)与r1(x)，r1(x)的次数< n，使得
x p ? x = f(x)q(x) ? r1(x)。 (12)
若同余方程(10)有n个解x ? xi (mod p（)1 ? i ? n），则由式(12)和Fermat定理，得到
r1(xi) ? 0 (mod p)，1 ? i ? n。
由此及定理2推论，可知r1(x)的系数都能被p整除，即
r1(x) = p?r(x)，
其中r(x)是整系数多项式。这证明了式(11)。
充分性 若式(11)成立，由Fermat定理，对于任何整数x，有
0 ? x p ? x ? f(x)q(x) (mod p)， (13)
即同余方程
f(x)q(x) ? 0 (mod p)
有p个解，但是，q(x)是p ? n次多项式，所以由定理2，方程q(x) ? 0 (mod p)的解数 ? p ? n。以?表示同余方程(10)的解数，则由第一节定理1，有
? + p ? n ? p，? ? n，
再利用定理2，得到? = n。 证毕。
|an，由辗转相除法可求出an?，p?|an?使得anan? ? 1 (mod p)，注：若p?于是，同余方程(1)与同余方程
an?f(x) = xn ? an?an ? 1xn ? 1 ? ? ? an?a1x ? an?a0 (mod p)
等价。因此，定理4是有普遍性的。
|a则 定理5 若p是素数，n?p ? 1，p? n
x ? a (mod p) (14)
有解的充要条件是
ap?1n?1 (mod p)。 (15)
若有解，则解数为n。
|x0，由Fermat定理，得到 证明 必要性 若方程(14)有解x0，则p?
123
a?充分性 若式(15)成立，则
p?1np?1n(x0)n= x0p ? 1 ?1 (mod p)。
p?1np?1np?1nxp?1?x?x((x)n?a?a?1)?(xn?a)P(x)?x(a?1)，其中P(x)是关于x的整系数多项式。由定理4可知同余方程(14)有n个解。证毕。
例1 判定同余方程2x3 ? 3x ? 1 ? 0 (mod 7)是否有三个解。 解 因为2?4 ? 1 (mod 7)，所以，原方程与
4?2x3 ? 4?3x ? 4 ? 0 (mod 7)
即
x3 ? 2x ? 3 ? 0 (mod 7)
等价。由于
x7 ? x = ( x3 ? 2x ? 3)(x4 ? 2x2 ? 3x ? 4) ? 12x2 ? 16x ? 12， 所以，由定理4可知，原方程的解数小于3。 例2 解同余方程
3x14 ? 4x10 ? 6x ? 18 ? 0 (mod 5)。
解 由Fermat定理，x5 ? x (mod 5)，因此，原同余方程等价于
2x2 ? x ? 3 ? 0 (mod 5)。 (16)
将x ? 0，?1，?2 (mod 5)分别代入方程(16)进行验证，可知这个同余方程解是x ? 1 (mod 5)。
p?1n
习 题 四
1. 解同余方程：
(ⅰ) 3x11 ? 2x8 ? 5x4 ? 1 ? 0 (mod 7)；
(ⅱ) 4x20 ? 3x12 ? 2x7 ? 3x ? 2 ? 0 (mod 5)。 2. 判定
(ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)是否有三个解； (ⅱ) x6 ? 2x5 ? 4x2 ? 3 ? 0 (mod 5)是否有六个解？ 124
3. 设(a, m) = 1，k与m是正整数，又设x0k ? a (mod m)，证明同余方程
xk ? a(mod m)
的一切解x都可以表示成x ? yx0 (mod m)，其中y满足同余方程yk ? 1 (mod m)。
4. 设n是正整数，p是素数，(n, p ? 1) = k，证明同余方程xn ? 1 (mod p)有k个解。
5. 设p是素数，证明：
(ⅰ) 对于一切整数x，xp ? 1 ? 1 ? (x ? 1) (x ? 2)?(x ? p ? 1) (mod p)； (ⅱ) (p ? 1)! ? ? 1 (mod p)。
6. 设p ? 3是素数，证明：(x ? 1)(x ? 2)?(x ? p ? 1)的展开式中除首项及常数项外，所有的系数都是p的倍数。
第五节 素数模的二次同余方程
设p是素数，我们来研究素数模p的二次同余方程
ax2 ? bx ? c ? 0 (mod p)。 (1)
如果p = 2，则可以直接验证x ? 0或1 (mod 2)是否方程(1)的解。
如果(a, p) = p，则方程(1)成为一元一次同余方程。因此，只需考察p > 2，(a, p) = 1的情形。此时，因为(4a, p) = 1，所以，方程(1)等价于方程
4a2x2 ? 4abx ? 4ac ? 0 (mod p)，
即
(2ax ? b)2 ? b2 ? 4ac (mod p)。
这样，研究方程(1)归结为对方程
x2 ? n (mod p) (2)
的研究。
定义１ 给定整数p，对于任意的整数n，(n，p) = 1，若方程(2)有解，则称n是模p的二次剩余，记为n?QR(p)；否则，称n是模p的二次非剩余，记为n?QNR(p)。 显然，若n1 ? n2 (mod p)，则它们同是模p的二次剩余（或二次非剩余），因此，在谈到模p的二次剩余（或二次非剩余）时，把n1和n2看作是
125
同一个。
以下，在本节中，总假定p是奇素数。 定理１ 若(n, p) = 1，则
(ⅰ) n是模p的二次剩余的充要条件是
n? 1 (mod p)； (3)
(ⅱ) 若n是模p的二次剩余，则方程(2)有两个解； (ⅲ) n是模p的二次非剩余的充要条件是
n? ?1 (mod p)。 (4)
证明 结论(ⅰ)与(ⅱ)由第四节定理５直接推出。 (ⅲ) 若(n, p) = 1，由第二章第四节定理１，有
np ? 1 ? 1 (mod p)，
p?12p?12(n?1)(n?1) ? 0 (mod p)。 (5)
因为p是奇素数，所以式(3)式与式(4)必有且仅有一个成立，利用结论(ⅰ)，可得到结论(ⅲ)。证毕。
p?1定理２ 模p的简化系中，二次剩余与二次非剩余的个数都是，
2而且，模p的每个二次剩余与且仅与数列
p?1212，22，?，() (6)
2中的一个数同余。
证明 显然，数列(6)包含了模p的全部二次剩余。为了证明定理，只需证明式(6)中的任何两个数对模p不同余。
p?1对任意的整数k，s，1 ? k < s ?，若
2k2 ? s2 (mod p)， (7)
则p?k ? s或p?k ? s。这都是不可能的，所以式(7)不能成立。证毕。 定义２ 给定奇素数p，对于整数n，定义Legendre符号为
当(n,p)?1；?0，n?()??1，当n?QR(p)； p??1，当n?QNR(p)。?p?12p?12126