【正文】 8)考察有序數(shù)對(duì)(u, v)所成的集合S = { (u, v)；u = py，v = qx，1 163。 x 163。 p1，1 163。 y 163。 q1 }顯然S中有p1q1 =個(gè)元素。由于(p, q) = 1，所以，對(duì)于任何(u, v)206。S，u 185。 v記S1 = { (u, v)；(u, v)206。S，u v }S2 = { (u, v)；(u, v)206。S，v u }則S1199。S2 = 198。，S1200。S2 = S。 (9)對(duì)于(u, v)206。S1，有u v，即py xq，x y，1 163。 y 163。 q1，因此S1中有個(gè)元素。同理，S2中有個(gè)元素，所以。 (10)聯(lián)合式(7)，式(8), 和式(10)，證得定理。證畢。利用第五節(jié)和本節(jié)中的定理，可以判定素?cái)?shù)模的二次同余方程的可解性。一般地，若p是素?cái)?shù)，計(jì)算Legendre符號(hào)()可按以下步驟進(jìn)行：(ⅰ) 求出n0 186。 n (mod p)，1 163。 n0 163。 p；(ⅱ) 將n0寫(xiě)成n0 = Q2q1q2Lqk的形式，其中Q206。Z，q1, q2,L, qk是互不相同的素?cái)?shù)；(ⅲ) 若有某個(gè)qi = 2，用定理1推論判定之值；(ⅳ) 若qi 185。 2，利用定理2將的計(jì)算轉(zhuǎn)化為計(jì)算；(ⅴ) 重復(fù)以上步驟，直至求出每個(gè)；(ⅵ) 計(jì)算。例1 已知563是素?cái)?shù)，判定方程x2 186。 429 (mod 563)是否有解。解 利用已有的定理，有方程有解。例2 求所有的素?cái)?shù)p，使得 2206。QR(p)，3206。QR(p)。解 若 2206。QR(p)，則= 1，因此， (11)所以，由定理1推論和第五節(jié)定理3推論，有， (12)由式(12)中的第一組同余式，得到p 186。 1 (mod 8)； (13)由式(12)中的第二組同余式，得到p 186。 3 (mod 8)。 (14)(ⅰ) 若式(13)成立，并且3206。QR(p)。由定理2，有，因此p 186。 1 (mod 3)。由此及式(13)，利用孫子定理得到p 186。 1 (mod 24)。 (15)(ⅱ) 若式(14)成立，并且3206。QR(p)。由定理2，有，因此p 186。 2 (mod 3)。由此及式(14)，利用孫子定理得到p 186。 11 (mod 24)。 (16)由式(15)與(16)可知所求的素?cái)?shù)具有形式p = 24k + 1 或 p = 24k + 11，k206。Z。例３ 證明：形如8k + 7（k206。Z）的素?cái)?shù)有無(wú)窮多個(gè)。解 用反證法。假設(shè)只有有限個(gè)形如8k + 7（k206。Z）的素?cái)?shù)p1, p2, L, pt。記N = (p1p2Lpt)2 2。顯然，2N。設(shè)q是N的一個(gè)奇素因數(shù)，則(p1p2Lpt)2 186。 2 (mod q)，因此，由定理1推論，有q 186。 1或7(mod 8)。若N的所有奇素因數(shù)都具有8k + 1的形式，則N也是8k + 1的形式，但是，由于任何奇數(shù)的平方對(duì)模8與1同余，所以應(yīng)有N 186。 1 2 186。 1 (mod 8)。這個(gè)矛盾說(shuō)明，N至少有一個(gè)形如8k + 7的奇素因數(shù)q。顯然，q 185。 pi（1 163。 i 163。 t），這與個(gè)數(shù)有限的假設(shè)矛盾。這個(gè)矛盾說(shuō)明，形如8k + 7（k206。Z）的素?cái)?shù)有無(wú)窮多個(gè)。例4 證明：形如8k + 3（k206。Z）的素?cái)?shù)無(wú)窮多個(gè)。解 用反證法。假設(shè)只有有限個(gè)形如8k + 3（k206。Z）的素?cái)?shù)p1, p2, L, pt。記N = (p1p2Lpt)2 +2。設(shè)q是N的一個(gè)素因數(shù)，顯然q2。由于 2206。QR(q)，所以。考慮兩種可能：(ⅰ) ，則q 186。 1 (mod 4)并且q 186。 1或7 (mod 8)，這導(dǎo)出q 186。 1 (mod 8)。(ⅱ) ，則q 186。 3 (mod 4) 并且q 186。 3或5 (mod 8)，這導(dǎo)出q 186。 3 (mod 8)。這樣，q只能是8k + 1或8k + 3的形式。由于pi 186。 3 (mod3)，pi2 186。 1 (mod 8)（1 163。 i 163。 t），所以，N 186。 3 (mod 8)，因此，N的素因數(shù)不可能都是8k + 1的形式，即至少有一個(gè)q，q189。N，q具有8k + 3的形式。顯然q 185。 pi（1 163。 i 163。 t）。這與個(gè)數(shù)有限的假設(shè)矛盾。因此，形如8k + 3（k206。Z）的素?cái)?shù)無(wú)窮多個(gè)。習(xí) 題 六1. 已知769與1013是素?cái)?shù)，判定方程(ⅰ) x2 186。 1742 (mod 769)；(ⅱ) x2 186。 1503 (mod 1013)。是否有解。2. 求所有的素?cái)?shù)p，使得下面的方程有解：x2 186。 11 (mod p)。3. 求所有的素?cái)?shù)p，使得 2206。QR(p)，3206。QR(p)。4. 設(shè)(x, y) = 1，試求x2 3y2的奇素?cái)?shù)因數(shù)的一般形式。5. 證明：形如8k + 5（k206。Z）的素?cái)?shù)無(wú)窮多個(gè)。6. 證明：對(duì)于任意的奇素?cái)?shù)p，總存在整數(shù)n，使得p189。(n2 + 1)(n2 + 2)(n2 2)。第七節(jié) Jacobi符號(hào)在上一節(jié)中我們看到，對(duì)于奇素?cái)?shù)p，利用計(jì)算Legendre符號(hào)可以判定方程x2 186。 a (mod p) (1)是否有解。對(duì)于一般的正整數(shù)m，如果它的標(biāo)準(zhǔn)分解式是，那么，由第二節(jié)定理4和第三節(jié)定理可知，判定方程x2 186。 a (mod m) (2)是否有解，歸結(jié)為對(duì)形如方程(1)（p = pi，1 163。 i 163。 k）的可解性判定。因此，在理論上，利用Legendre符號(hào)可以判定方程(2)是否有解。但是，寫(xiě)出正整數(shù)的標(biāo)準(zhǔn)分解式常會(huì)遇到實(shí)際困難，所以利用Legendre符號(hào)判定方程(2)的可解性并不常是容易實(shí)現(xiàn)的。為此，本節(jié)中要介紹一個(gè)更為切實(shí)可行的方法。定義1 給定正奇數(shù)m 1，m = p1p2Lpk，其中pi（1163。 i 163。 k）是奇素?cái)?shù)，對(duì)于任意的整數(shù)a，定義，其中右端的（1163。 i 163。 k）是Legendre符號(hào)，稱是Jacobi符號(hào)。例如，取m = 45 = 335，則注1：當(dāng)m是奇素?cái)?shù)時(shí)，Jacobi符號(hào)就是Legendre符號(hào)。前者是后者的推廣。注2：如果m是奇素?cái)?shù)，當(dāng)= 1時(shí)，方程(2)有解。當(dāng)m不是奇素?cái)?shù)時(shí)，這個(gè)結(jié)論不一定成立。例如，方程x2 186。 5 (mod 9)無(wú)解，但是= 1。盡管如此，利用雅各比符號(hào)仍可對(duì)方程(2)的無(wú)解性給出判斷。事實(shí)上，如果方程(2)有解，m = p1p2Lpk，則對(duì)于每個(gè)pi（1163。 i 163。 k），當(dāng)p = pi時(shí)方程(1)有解，因此，由雅各比符號(hào)的定義可知= 1。這樣，若= 1，則方程(2)必?zé)o解。下面，我們研究雅各比符號(hào)的計(jì)算方法。定理1 使用定義1中的符號(hào)，下面的結(jié)論成立：(ⅰ) 若a 186。 a1 (mod m)，則； (3)(ⅱ) = 1；(ⅲ) 對(duì)于任意的整數(shù)a1, a2, L, at，有； (4)(ⅳ) 對(duì)于任意的整數(shù)a，b，(a, m) = 1，有。 (5)證明 (ⅰ) 由a 186。 a1 (mod m)，可知a 186。 a1 (mod pi)，1163。 i 163。 k，因此結(jié)論(ⅱ)，(ⅲ)，(ⅳ)的證明留作習(xí)題。引理 設(shè)ai 186。 1 (mod m)，1163。 i 163。 k，a = a1a2Lak，則(mod m)。 (6)證明 由假設(shè)條件，存在整數(shù)bi206。N， 使得ai = 1 + bim（1163。 i 163。 k），因此a 1 = a1a2Lak 1 = (1 + b1m)(1 + b2m)L (1 + bkm) 1= m(b1 + b2 + L + bk) + m2A，其中A是某個(gè)整數(shù)。于是證畢。定理2 設(shè)m = p1p2Lpk是奇數(shù)，其中p1, p2, Lpk是素?cái)?shù)，則下面的結(jié)論成立：(ⅰ) ；(ⅱ) 。證明 由定義1及第五節(jié)定理3，有，由此及式(6)推出結(jié)論(ⅰ)。由定義1及第六節(jié)定理1，有，由此及式(6)推出結(jié)論(ⅱ)。證畢。定理3 設(shè)m，n是大于1的奇整數(shù)，則。 (7)證明 若(m, n) 1，則由定義1可知式(7)成立。若(m, n) = 1，設(shè)m = p1p2Lpk ，n = q1q2Lpl ，其中pi，qj（1163。 i 163。 k，1163。 j 163。 l）都是素?cái)?shù)，(pi, qj) = 1（1163。 i 163。 k，1163。 j 163。 l），則由定義1及第六節(jié)定理2，有 （8）其中。由引理，因?yàn)?，我們?jiàn)到(mod 2)。將此式代入式(8），得到式(7)。證畢。 利用以上定理，我們可以很容易地計(jì)算Jacobi符號(hào)，特別是Legendre符號(hào)的數(shù)值。但是，必須注意，如同在定義1的注2中指出的，在判斷方程(2)的可解性時(shí)，Legendre符號(hào)和Jacobi的作用是不一樣的。對(duì)于一般的正奇數(shù)m來(lái)說(shuō)，= 1并不能保證方程(2)有解。例1 設(shè)a與b是正奇數(shù)，求的關(guān)系。解 我們有例2 已知3371是素?cái)?shù)，判斷方程x2 186。 12345 (mod 3371) (9)是否有解。解 利用Jacobi符號(hào)的性質(zhì)，有因此，方程(9)無(wú)解。注：在上面例題中，如果用計(jì)算Legendre符號(hào)的數(shù)值來(lái)判定方程的可解性，將比這里的方法繁復(fù)許多。習(xí) 題 七1. 證明定理的結(jié)論(ⅱ)，(ⅲ)，(ⅳ)。2. 已知3019是素?cái)?shù)，判定方程x2 186。 374 (mod 3019)是否有解。3. 設(shè)奇素?cái)?shù)為p = 4n + 1型，且d189。n，證明：= 1。4. 設(shè)p，q是兩個(gè)不同的奇素?cái)?shù)，且p = q + 4a，證明：。5. 設(shè)a 0，b 0，b為奇數(shù)，證明：6. 設(shè)a，b，c是正整數(shù)，(a, b) = 1，2b，b 4ac，求的關(guān)系。1. 若不給自己設(shè)限，則人生中就沒(méi)有限制你發(fā)揮的藩籬。2. 若不是心寬似海，哪有人生風(fēng)平浪靜。在紛雜的塵世里，為自己留下一片純靜的心靈空間，不管是潮起潮落，也不管是陰晴圓缺，你都可以免去浮躁，義無(wú)反顧，勇往直前，輕松自如地走好人生路上的每一步3. 花一些時(shí)間，總會(huì)看清一些事。用一些事情，總會(huì)看清一些人。有時(shí)候覺(jué)得自己像個(gè)神經(jīng)病。既糾結(jié)了自己，又打擾了別人。努力過(guò)后，才知道許多事情，堅(jiān)持堅(jiān)持，就過(guò)來(lái)了。4. 歲月是無(wú)情的，假如你丟給它的是一片空白，它還給你的也是一片空白。歲月是有情的，假如你奉獻(xiàn)給她的是一些色彩，它奉獻(xiàn)給你的也是一些色彩。你必須努力，當(dāng)有一天驀然回首時(shí)，你的回憶里才會(huì)多一些色彩斑斕，少一些蒼白無(wú)力。只有你自己才能把歲月描畫(huà)成一幅難以忘懷的人生畫(huà)卷。