这样，q只能是8k ? 1或8k ? 3的形式。由于pi ? 3 (mod3)，pi2 ? 1 (mod 8)（1 ? i ? t），所以，N ? 3 (mod 8)，因此，N的素因数不可能都是8k ? 1的形式，即至少有一个q，q?N，q具有8k ? 3的形式。显然q ? pi（1 ? i ? t）。这与个数有限的假设矛盾。因此，形如8k ? 3（k?Z）的素数无穷多个。
习 题 六
1. 已知769与1013是素数，判定方程 (ⅰ) x2 ? 1742 (mod 769)； (ⅱ) x2 ? 1503 (mod 1013)。 是否有解。
2. 求所有的素数p，使得下面的方程有解：
x2 ? 11 (mod p)。
3. 求所有的素数p，使得 ?2?QR(p)，?3?QR(p)。
4. 设(x, y) = 1，试求x2 ? 3y2的奇素数因数的一般形式。 5. 证明：形如8k ? 5（k?Z）的素数无穷多个。 6. 证明：对于任意的奇素数p，总存在整数n，使得
p?(n2 ? 1)(n2 ? 2)(n2 ? 2)。
第七节 Jacobi符号
在上一节中我们看到，对于奇素数p，利用计算Legendre符号可以判定方程
x2 ? a (mod p) (1)
是否有解。对于一般的正整数m，如果它的标准分解式是
?1?2km?p1p2?p?k，
那么，由第二节定理4和第三节定理可知，判定方程
x2 ? a (mod m) (2)
是否有解，归结为对形如方程(1)（p = pi，1 ? i ? k）的可解性判定。因此，在理论上，利用Legendre符号可以判定方程(2)是否有解。但是，
137
写出正整数的标准分解式常会遇到实际困难，所以利用Legendre符号判定方程(2)的可解性并不常是容易实现的。为此，本节中要介绍一个更为切实可行的方法。
定义1 给定正奇数m > 1，m = p1p2?pk，其中p（是奇素数，i1? i ? k）对于任意的整数a，定义
(a)?(a)(a)?(a)， mp1p2pkaa其中右端的()（1? i ? k）是Legendre符号，称()是Jacobi符号。
pim例如，取m = 45 = 3?3?5，则
(2)?(2)(2)(2)?(2)?45335552?1(?1)8??1，45335533注1：当m是奇素数时，Jacobi符号就是Legendre符号。前者是后者的推广。
a注2：如果m是奇素数，当()= 1时，方程(2)有解。当m不是奇素
m数时，这个结论不一定成立。例如，方程x2 ? 5 (mod 9)无解，但是
(5)?(5)(5)= 1。 933尽管如此，利用雅各比符号仍可对方程(2)的无解性给出判断。事实上，如果方程(2)有解，m = p1p2?pk，则对于每个pi（1? i ? k），当p = pi
a时方程(1)有解，因此，由雅各比符号的定义可知()= 1。这样，若
m(a)= ?1，则方程(2)必无解。 m下面，我们研究雅各比符号的计算方法。
定理1 使用定义1中的符号，下面的结论成立： (ⅰ) 若a ? a1 (mod m)，则
(28)?(28)(28)(28)?(3)?3?15?1?(?1)22
(5)?(2)??1。138
(a)?(1)； (3)
m(ⅱ)
amm(ⅲ) 对于任意的整数a1, a2, ?, at，有
aa?aaaa(12t)?(1)(2)?(t)； (4)
mmmm(ⅳ) 对于任意的整数a，b，(a, m) = 1，有
a2b()?(b)。 (5) mm证明 (ⅰ) 由a ? a1 (mod m)，可知
a ? a1 (mod pi)，1? i ? k，
因此
(a)?(a)(a)?(a)mp1p2pk
a1a1a1a1?()()?()?()，p1p2pkm结论(ⅱ)，(ⅲ)，(ⅳ)的证明留作习题。
引理 设ai ? 1 (mod m)，1? i ? k，a = a1a2?ak，则
a?1a?1a1?1(mod m)。 (6) ????kmmm证明 由假设条件，存在整数bi?N， 使得ai = 1 ? bim（1? i ? k），因此
a ? 1 = a1a2?ak ? 1
= (1 ? b1m)(1 ? b2m)? (1 ? bkm) ? 1 = m(b1 ? b2 ? ? ? bk) ? m2A， 其中A是某个整数。于是
a?1?b1?b2??bkm
ak?1a1?1a2?1?????(modm)。mmm
139
(1)= 1；
证毕。
定理2 设m = p1p2?pk是奇数，其中p1, p2, ?pk是素数，则下面的结论成立： ?1(ⅰ) ()?(?1)mm?12；
(ⅱ)
。
m证明 由定义1及第五节定理3，有
k(?1)??(?1)?(?1)mi?1pi由此及式(6)推出结论(ⅰ)。 由定义1及第六节定理1，有
p?1p1?1p2?1????k222(2)?m2?1(?1)8，
mi?1pi由此及式(6)推出结论(ⅱ)。证毕。
定理3 设m，n是大于1的奇整数，则
m?1n?1(2)??(2)?(?1)k22p2?1p1?1p2?1????k888，
?(n)?(?1)22(m)。 (7) mn证明 若(m, n) > 1，则由定义1可知式(7)成立。 若(m, n) = 1，设
m = p1p2?pk ，n = q1q2?pl ，
其中pi，q（1? j ? l）都是素数，(pi, qj) = 1（1? i ? k，1? j ? l），j1? i ? k，
则由定义1及第六节定理2，有
kklqjnn ()??()???()
mpipii?1i?1j?1 ???(?1)i?1j?1klpi?1qj?1?22(p)
iqj140
???(?1)i?1j?1klpi?1qj?122p(??)
ii?1j?1klqj ?(?1)其中
?p?m （8） ()?(?1)()，?ii?1knnpi?1qj?1。 ????22i?1j?1kl|n，2?|m，我们见到 由引理，因为2?kp?1lqj?1kp?1n?1m?1n?1ii???????(mod 2)。 ?2?22222i?1j?1i?1将此式代入式(8），得到式(7)。证毕。
利用以上定理，我们可以很容易地计算Jacobi符号，特别是Legendre符号的数值。但是，必须注意，如同在定义1的注2中指出的，在判断方程(2)的可解性时，Legendre符号和Jacobi的作用是不一
a样的。对于一般的正奇数m来说，()= 1并不能保证方程(2)有解。
m2a例1 设a与b是正奇数，求()与(b)的关系。
4a?ba解 我们有
(2a)?(2)(a)?(?1)4a?b4a?b4a?b?(?1)?(?1)ab?b2?18(4a?b)2?18(a)4a?b
(?1)a?14a?b?1?22(4a?b)a1?b?1a?1b?1??8222(b)。a例2 已知3371是素数，判断方程
x2 ? 12345 (mod 3371) (9)
是否有解。
解 利用Jacobi符号的性质，有
141
(12345)?(2232)?(33713371?2)(4)(279)33713371337133712?13371?1279?1?2(?1)8(?1)2(23)279?(23)?279279?123?1?2(?1)223?13?1?22(279)233
3??()??(?1)23(23)??1。因此，方程(9)无解。
注：在上面例题中，如果用计算Legendre符号的数值来判定方程的可解性，将比这里的方法繁复许多。
习 题 七
1. 证明定理的结论(ⅱ)，(ⅲ)，(ⅳ)。
2. 已知3019是素数，判定方程x2 ? 374 (mod 3019)是否有解。
d3. 设奇素数为p = 4n ? 1型，且d?n，证明：()= 1。
paa4. 设p，q是两个不同的奇素数，且p = q ? 4a，证明：()?()。
pq5. 设a > 0，b > 0，b为奇数，证明：
?a当a?0，1(mod4)?(b)a ()??a2a?b??()当a?2，3(mod4)。?ba|b，b < 4ac，求(6. 设a，b，c是正整数，(a, b) = 1，2?)与(a)4ac?bb的关系。
142