np?12(p?1)!?(?1)m?(p?ai)?bimt2i?1i?1
p?1)!(modp)，2从而由第五节定理3推出引理结论。证毕。 定理1 下面的结论成立：
?(?1)m((ⅰ)
p(ⅱ) 若n是奇数，(n, p) = l，则
(2)?(?1)p2?18； (2)
(n)?(?1)i?1p其中l??[p]lni， (3)
p?1。 2证明 使用引理中的符号rk，ai，bi，m与t，由
p?1nknk?p[]?rk，1?k?，
p2及引理的证明过程，看到
np?1?22k?1?nk?p?[k?1lp?12llnk]??rkpk?1mtnk?p?[]??ai??bik?1pi?1i?1lmtmnk?p?[]??(p?ai)??bi?2?ai?mp k?1pi?1i?1i?1llmnk?p?[]??i?2?ai?mpk?1pi?1i?1mp2?1nk?p?[]??2?ai?mp，2k?1pi?1l因此 132
lmp2?1nk(n?1)?p?[]?2?ai?mp。 (4)
8k?1pi?1nknk若n = 2，则当1 ? k ?l时，0 << 1，所以[]= 0，于是由式(4)得
pp到
p2?1? m (mod 2)。 (5) 8|n则由式(4)推出 若2?k?1nk[?]? m (mod 2)。 (6)
lp由式(5)，式(6)及引理，证得定理。证毕。
推论 设p是素数，则
当p??1(mod8)，?1，(2)??
?1，当p??3(mod8)。p?定理2(二次互反律) 设p与q是不相同的两个素数，则
(q)?(?1)p证明 只需证明
p?1q?1?22(p)。
q?(q)(p)?(?1)22。 (7) pqp?1q?1记p1?。由定理１，有 ，q1?22p1q1qpkqkpr()()?（?1），r??[]??[]。 (8) pqk?1pk?1q考察有序数对(u, v)所成的集合
S = { (u, v)；u = py，v = qx，1 ? x ? p1，1 ? y ? q1 }
p?1q?1显然S中有p1q1 =个元素。由于(p, q) = 1，所以，对于任何?22(u, v)?S，u ? v记
S1 = { (u, v)；(u, v)?S，u > v }
p?1q?1 133
S2 = { (u, v)；(u, v)?S，v > u }
则
S1?S2 = ?，S1?S2 = S。 (9)
对于(u, v)?S1，有u > v，即
ppy > xq，x qp1qxpy因此S1中有?[]个元素。同理，S2中有?[]个元素，所以 x?1py?1qq1q1p?1q?1p1kqkp???[]??[]。 (10) 22k?1pk?1q联合式(7)，式(8), 和式(10)，证得定理。证毕。 利用第五节和本节中的定理，可以判定素数模的二次同余方程的可解 n性。一般地，若p是素数，计算Legendre符号()可按以下步骤进行： p(ⅰ) 求出n0 ? n (mod p)，1 ? n0 ? p； (ⅱ) 将n0写成n0 = Q2q1q2?qk的形式，其中Q?Z，q1, q2,?, qk是互不相同的素数； q(ⅲ) 若有某个qi = 2，用定理1推论判定(i)之值； pqp(ⅳ) 若qi ? 2，利用定理2将(i)的计算转化为计算()； qipq(ⅴ) 重复以上步骤，直至求出每个(i)； pkqq(ⅵ) 计算()??(i)。 ppi?1例1 已知563是素数，判定方程x2 ? 429 (mod 563)是否有解。 解 利用已有的定理，有 134 (429)?(3?11?13)?(3)(11)(13)5635635635635633?1563?111?1563?113?1563?1???563563?(?1)22()(?1)22()(?1)22(563) 31113?(23)(211)(413)?(?1)(?1)?1。方程有解。 例2 求所有的素数p，使得 ?2?QR(p)，3?QR(p)。 解 若 ?2?QR(p)，则(?2p)= 1，因此， ???(?1?p)?1???1或?(p)??1， ???(2p)??1???(2p)??1所以，由定理1推论和第五节定理3推论，有 ??p?1(mod4)?p??1(mod8)或??p?3(mod4)， ?p??3(mod8)由式(12)中的第一组同余式，得到 p ? 1 (mod 8)； 由式(12)中的第二组同余式，得到 p ? 3 (mod 8)。 (ⅰ) 若式(13)成立，并且3?QR(p)。由定理2，有 3?1p?11?(32?2p)?(?1)(pp3)?(3)， 因此p ? 1 (mod 3)。由此及式(13)，利用孙子定理得到 p ? 1 (mod 24)。 (ⅱ) 若式(14)成立，并且3?QR(p)。由定理2，有 3?1?p?11?(3)?(?1)22ppp(3)??(3)， 因此p ? 2 (mod 3)。由此及式(14)，利用孙子定理得到 (11) (12) (13) (14) (15) 135 p ? 11 (mod 24)。 (16) 由式(15)与(16)可知所求的素数具有形式 p = 24k ? 1 或 p = 24k ? 11，k?Z。 例３ 证明：形如8k ? 7（k?Z）的素数有无穷多个。 解 用反证法。假设只有有限个形如8k ? 7（k?Z）的素数p1, p2, ?, pt。记 N = (p1p2?pt)2 ? 2。 |N。设q是N的一个奇素因数，则 显然，2?(p1p2?pt)2 ? 2 (mod q)， 因此，由定理1推论，有q ? 1或7(mod 8)。 若N的所有奇素因数都具有8k ? 1的形式，则N也是8k ? 1的形式，但是，由于任何奇数的平方对模8与1同余，所以应有 N ? 1 ? 2 ? ?1 (mod 8)。 这个矛盾说明，N至少有一个形如8k ? 7的奇素因数q。显然，q ? pi（1 ? i ? t），这与个数有限的假设矛盾。这个矛盾说明，形如8k ? 7（k?Z）的素数有无穷多个。 例4 证明：形如8k ? 3（k?Z）的素数无穷多个。 解 用反证法。假设只有有限个形如8k ? 3（k?Z）的素数p1, p2, ?, pt。记 N = (p1p2?pt)2 +2。 设q是N的一个素因数，显然q>2。由于 ?2?QR(q)，所以 (?2)?(?1)(2)?1。 qqq考虑两种可能： ?12(ⅰ) ()?1，()?1，则 qqq ? 1 (mod 4)并且q ? 1或7 (mod 8)， 这导出q ? 1 (mod 8)。 ?12(ⅱ) ()??1，()??1，则 qqq ? 3 (mod 4) 并且q ? 3或5 (mod 8)， 这导出q ? 3 (mod 8)。 136