例如，由定理1，1与4是模5的二次剩余，2与3是模5的二次非剩余，于是
(1)?1，(2)??1，(3)??1，(4)?1， 5555定理3 设p是奇素数，n是整数，则 n(ⅰ) ()?npp?12(mod p)；
(ⅱ) 若n ? n1 (mod p)，则(nn)?(1)； pp1?1(ⅲ) ()?1，()?(?1)2；
pp(ⅳ) 对任意的整数ni，1 ? i ? k，有
aa?aaaa(12k)?(1)(2)?(k)。
pppp证明 结论(ⅰ)与(ⅱ)容易由定义2及定理1得到。
为了证明结论(ⅲ)，只需证明其中的第二个等式。由结论(ⅰ)，有
p?1(?1)?(?1)2(mod p)， p其中同余式两端都只能取值 ?1或 ?1，因此，结论(ⅲ)的第二个等式成立。
最后，由结论(ⅰ)，有
p?1p?1a1a2?ak2()?(a1a2?ak)?a12a22?akpaaa?(1)(2)?(k)(modp)。pppp?1p?12p?1
由于上式首端与末端都是只取值 ?1，0或1的整数，所以它们必相等。结论(ⅳ)得证。证毕。
推论 设p是奇素数，则 ?1?QR(p)的充要条件是p ? 1(mod 4)；?1?QNR(p)的充要条件是p ? 3(mod 4)。 例1 判断方程x2 ? 5 (mod 11)有没有解。
127
解 由定理2，因为
(5)?51111?12?55?5?54?5?32?1 (mod 11)，
方程有解。
例2 设p是奇素数，p ? 1 (mod 4)，则
(?(p?1)!)2? ?1 (mod p)
2解 由Wilson定理（第二章第二节例3），有
?1?(p?1)!?(?1)?(?1)?((p?121?2?p?12(p?1)!p?1p?1?(p?1)
22p?12)!)(modp)。2定理2和例2说明，当素数p ? 1(mod 4)时，模p的所有二次剩余之积
对模p同余于 ?1。此外，我们还得到了方程x??1(modp)的解。 例3 设n是整数，证明n2 ? 1的任何奇因数都是4m ? 1（m?Z）的形式。
解 由于任何奇数都可表成奇素数之积，而且任意多个形如4m ? 1的整数之积也具有4m ? 1的形式，我们只需证明：若素数p是n2 ? 1的因数，则p具有4m ? 1的形式。 事实上，若p?n2 ? 1，则
n2 ? ?1 (mod p)，
即?1?QR(p)。由定理3推论得出所需结论。 例４ 形如4m ? 1（k?Z）的素数有无穷多个。
解 用反证法。假设只有有限多个形如4k ? 1的素数p1, p2, ?, pk，记
N = 4(p1p2?pk)2 ? 1。
由例2，必有奇素数q，q ? 1 (mod 4)，q?N，显然q ? pi（1 ? i ? k），这与假设矛盾，所以形如4m ? 1的素数有无穷多个。
例５ 若a ? 1 (mod 4)，2?b，并且b没有形如4k ? 3（k?Z）的素因数，证明方程
y2 = x3 ? a3 ? b2 (8) 128
2没有整数解。
解 用反证法。假设有整数x，y满足方程(8)。 若2?x，则由式(8)得则y2 ? ?1(mod 4)这不可能。 若x ? 3 (mod 4)，则由式(8)得到
y2 ? x3 ? a3 ? b2 ? 33 ? 13 ? 0 ? 2 (mod 4)，
这是不可能的。 若x ? 1 (mod 4)，则
x2 ? ax ? a2 ? 1 ? a ? a2 ? 3 (mod 4)， (9)
因此，必有素数p ? 3 (mod 4)，使得
p?x2 ? ax ? a2 。 (10)
由式(8)与式(10)得到
y2 = x3 ? a3 ? b2 ? ?b2 (mod p)， (11)
|b2，所以有 即 ?b2 ?QR(p)。但是，由假设，p??b2?1b2()?()()??1， ppp这与式(11)矛盾。
例６ 设p是素数，证明：数例1, 2, ?, p ? 1中的模p的二次剩余之和是
p(p?1)k2S??p?[]。
24k?1pp?1解 对于整数k，1 ? k ?，记
2k2 = pqk ? rk，qk?Z，1 ? rk ? p ? 1，
k2则qk =[]，并且，由定理2，有
p2p?12k2S??rk??k?p?[]k?1k?1k?1p2p?12p?12p?12p(p2?1)k2??p?[]。24k?1pp?12
129
例７ 设p是奇素数，证明：若同余方程
x4 ? 1 ? 0 (mod p) (12)
有解，则p ? 1 (mod 8)。
解 设x ? a (mod p)是方程(12)的解，则
a4 ? ?1 (mod p)， (13) a8 ? 1 (mod p)。 (14)
以d0表示使
ad ? 1 (mod p) (15)
成立的最小正整数d，记8 = qd0 ? r，0 ? r ? d0 ? 1，则由式(14)与式(15)得到
1 ? a8 =aqd0?r? ar (mod p)，
因此，若r ? 0，则上式与d0的定义矛盾。所以r = 0，即d0?8，这样，d0的取值只可能是1，2，4或8。由式(13)可知d0 = 8。
用同样方法以及Fermat定理可以证明8?p ? 1即p ? 1 (mod 8)。
习 题 五
1. 同余方程x2 ? 3 (mod 13)有多少个解？
2. 求出模23的所有的二次剩余和二次非剩余。
3. 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。
n4. 设素数 p ? 3 (mod 4)，()= 1，证明x ? ?npp?14(mod p)是同余方
程
x2 ? n (mod p)
的解。
5. 设p是奇素数，(n, p) = 1，?是正整数，证明同余方程
x2 ? n (mod p?)
n有解的充要条件是()= 1。
p130
6. 设p是奇素数，证明：模pp同余。
p?1的所有二次剩余的乘积与(?1)2对模
第六节 二次互反律
本节要对Legendre符号和二次剩余做进一步的研究。以下，总以p表示奇素数。
引理 设(n, p) = 1，对于整数k（1 ? k ?
p?1），以rk表示nk对 2模p的最小非负剩余。设在r1,r2,?,rp?1中大于
2p的有m个，则 2(n)= (?1)m。
p证明 在数列r1,r2,?,rp?1中，假设大于
2pp的是a1, a2, ?, am，小于22mt的是b1, b2, ?, bt，则
np?12(p?1)!??(nk)??ai?bi(mod p)。 (1) 21?k?p?12i?1i?1pp?ai?p，所以0?p?ai?，而且对于任意的i，j，1 ? i ? m，22p?11 ? j ? t，有bj ? p ? ai，否则，将有整数k1与k2，1 ? k1, k2 ?，使
2得
nk1 ? nk2 ? 0 (mod p)，
即
p?n(k1 + k2)，
由于(n, p) = 1，于是p?k1 ? k2，这是不可能的。这样，由式(1)推出 因为
131