【導(dǎo)讀】本節(jié)要介紹同余方程的基本概念及一次同余方程。在本章中，總假定m是正整數(shù)。a0是整系數(shù)多項(xiàng)式，稱。是關(guān)于未知數(shù)x的模m的同余方程，簡(jiǎn)稱為模m的同余方程。0，則稱為n次同余方程。凡對(duì)于模m同余的解，被視為同一個(gè)解。剩余系中的解的個(gè)數(shù)。由定義2，同余方程的解數(shù)不超過(guò)m。(ⅲ)設(shè)m是素?cái)?shù)，f=gh，g與h都是整系數(shù)多項(xiàng)式，因此，第一個(gè)結(jié)論可由第四章第一節(jié)定理1得出。若同余方程有解x0，則存在y0，使得x0與y0是方程的解，由式所確定的x都滿足方程。進(jìn)行逐個(gè)驗(yàn)證，以求出方程和的解；第二，設(shè)m?a，則又可繼續(xù)轉(zhuǎn)化成一個(gè)對(duì)于更小的模r的同余方程。但是由假設(shè)條件可知同余方程與都有且。所以這兩個(gè)同余方程等價(jià)。一些的同余方程，從而易于求解。計(jì)算量太大，不實(shí)用。解必要性是顯然的。下面證明充分性。由同余的基本性質(zhì)，得到式。

　　

【正文】 p??????? ????? 從而由第五節(jié)定理 3推出引理結(jié)論。證畢。 定理 1 下面的結(jié)論成立： (ⅰ ) 8 12)1(2)( ??? pp； (2) (ⅱ ) 若 n是奇數(shù)， (n, p) = l，則 ???? li pnipn 1 ][)1()( ， (3) 其中 21??pl 。 證明 使用引理中的符號(hào) rk， ai， bi， m與 t，由 2 11][ ????? pkrpnkpnk k， 133 及引理的證明過(guò)程 ， 看到 ，mpappnkpmpaipnkpmpabappnkpbapnkprpnkpnkpnmiilkmiililkmiitiimiilktiimiilklkklkpk?????????????????????????????????????????????????????121111111111111211222122)(21][][][][][ 因此 mpapnkppn mi ilk ????? ?? ?? 112 28 1)1( ][。 (4) 若 n = 2，則當(dāng) 1 ? k ?l時(shí)， 0 pnk 1， 所以 ][pnk= 0， 于是由式 (4)得到 812?p ? m (mod 2)。 (5) 若 2|? n則由式 (4)推出 ??lk pnk1 ][ ? m (mod 2)。 (6) 由式 (5)，式 (6)及引理，證得定理。證畢。 推論 設(shè) p是素?cái)?shù)，則 ??? ??? ??? 。當(dāng)， ，當(dāng)， )8( m o d31 )8( m o d112 )( ppp 定理 2(二次互反律 ) 設(shè) p與 q是不相同的兩個(gè)素?cái)?shù)，則 )()( 2 12 1)1( qppq qp ????? 。 134 證明 只需證明 2 12 1)1())(( ????? qpqppq 。 (7) 記2 12 1 11 ???? qqpp 。由定理１，有 ?? ?? ???? 11 11 ][][))(( 1 qkpkr qkppkqrqppq ，）（ 。 (8) 考察有序數(shù)對(duì) (u, v)所成的集合 S = { (u, v)； u = py， v = qx， 1 ? x ? p1， 1 ? y ? q1 } 顯然 S中有 p1q1 = 2121 ??? qp 個(gè)元素。由于 (p, q) = 1，所以，對(duì)于任何 (u, v)?S， u ? v記 S1 = { (u, v)； (u, v)?S， u v } S2 = { (u, v)； (u, v)?S， v u } 則 S1?S2 = ?， S1?S2 = S。 (9) 對(duì)于 (u, v)?S1， 有 u v，即 py xq， x qpy， 1 ? y ? q1， 因此 S1中有 ??11 ][qy qpy 個(gè)元素。同理， S2中有 ??11 ][px pqx 個(gè)元素，所以 ?? ?? ????? 11 11 ][][2 12 1 qkpk qkppkqqp 。 (10) 聯(lián)合式 (7)， 式 (8), 和式 (10)， 證得定理 。 證畢。 利用第五節(jié)和本節(jié)中的定理 ， 可以判定素?cái)?shù)模的二次同余方程的可解性 。 一般地，若 p是素?cái)?shù)，計(jì)算 Legendre符號(hào) (pn)可按以下步驟進(jìn)行： (ⅰ ) 求出 n0 ? n (mod p)， 1 ? n0 ? p； (ⅱ ) 將 n0寫(xiě)成 n0 = Q2q1q2? qk的形式，其中 Q?Z， q1, q2,? , qk是互不相同的素?cái)?shù)； 135 (ⅲ ) 若有某個(gè) qi = 2， 用定理 1推論判定 )(pqi之值； (ⅳ ) 若 qi ? 2，利用定理 2將 )(pqi的計(jì)算轉(zhuǎn)化為計(jì)算 )(iqp ； (ⅴ ) 重復(fù)以上步驟，直至求出每個(gè) )(pqi； (ⅵ ) 計(jì)算 ???kiipqpq1 )()(。 例 1 已知 563是素?cái)?shù)，判定方程 x2 ? 429 (mod 563)是否有解。 解 利用已有的定理，有 。1)1)(1(13411232135 6 3)1(115 6 3)1(35 6 3)1(5 6 3135 6 3115 6 335 6 3131135 6 34 2 9))()(()()()())()(()()(21563211321563211121563213?????????????????????? 方程有解。 例 2 求所有的素?cái)?shù) p，使得 ?2?QR(p)， 3?QR(p)。 解 若 ?2?QR(p)，則 )(2p?= 1， 因此， ??????????????????????12111211)()()()(pppp 或 ， (11) 所以 ，由定理 1推論和第五節(jié)定理 3推論，有 ??? ?????? ??? )8( m o d3 )4( m o d3)8( m o d1 )4( m o d1 pppp 或， (12) 由式 (12)中的第一組同余式，得到 136 p ? 1 (mod 8)； (13) 由式 (12)中的第二組同余式，得到 p ? 3 (mod 8)。 (14) (ⅰ ) 若式 (13)成立，并且 3?QR(p)。 由定理 2，有 )()()( 33)1(31 2 12 13 ppp p ???? ??? ， 因此 p ? 1 (mod 3)。由此及式 (13)，利用孫子定理得到 p ? 1 (mod 24)。 (15) (ⅱ ) 若式 (14)成立，并且 3?QR(p)。由定理 2，有 )()()( 33)1(31 2 12 13 ppp p ????? ??? ， 因此 p ? 2 (mod 3)。由此及式 (14)，利用孫子定 理得到 p ? 11 (mod 24)。 (16) 由式 (15)與 (16)可知所求的素?cái)?shù)具有形式 p = 24k ? 1 或 p = 24k ? 11， k?Z。 例３ 證明：形如 8k ? 7（ k?Z）的素?cái)?shù)有無(wú)窮多個(gè)。 解 用反證法。假設(shè)只有有限個(gè)形如 8k ? 7（ k?Z）的素?cái)?shù) p1, p2, ? , pt。記 N = (p1p2? pt)2 ? 2。 顯然， 2|? N。設(shè) q是 N的一個(gè)奇素因數(shù)，則 (p1p2? pt)2 ? 2 (mod q)， 因此，由定理 1推論，有 q ? 1或 7(mod 8)。 若 N的所有奇素因數(shù)都具有 8k ? 1的形式，則 N也是 8k ? 1的形式，但是，由于任何奇數(shù)的平方對(duì)模 8與 1同余，所以應(yīng)有 N ? 1 ? 2 ? ?1 (mod 8)。 這個(gè)矛盾說(shuō)明， N至少有一個(gè)形如 8k ? 7的奇素因數(shù) q。顯然， q ? pi（ 1 ? i ? t），這與個(gè)數(shù)有限的假設(shè)矛盾。這個(gè)矛盾說(shuō)明，形如 8k ? 7（ k?Z）的素?cái)?shù)有無(wú)窮多個(gè)。 例 4 證明：形如 8k ? 3（ k?Z）的素?cái)?shù)無(wú)窮多個(gè) 。 解 用反證法。假設(shè)只有有限個(gè) 形如 8k ? 3（ k?Z）的素?cái)?shù) p1, p2, ? , pt。記 137 N = (p1p2? pt)2 +2。 設(shè) q是 N的一個(gè)素因數(shù) ， 顯然 q2。由于 ?2?QR(q)， 所以 1212 ))(()( ???? qqq 。 考慮兩種可能： (ⅰ ) 1211 )()( ???qq ，則 q ? 1 (mod 4)并且 q ? 1或 7 (mod 8)， 這導(dǎo)出 q ? 1 (mod 8)。 (ⅱ ) 1211 )()( ?????qq ，則 q ? 3 (mod 4) 并且 q ? 3或 5 (mod 8)， 這導(dǎo)出 q ? 3 (mod 8)。 這樣， q只能是 8k ? 1或 8k ? 3的形式。由于 pi ? 3 (mod3)， pi2 ? 1 (mod 8)（ 1 ? i ? t） ， 所以， N ? 3 (mod 8)，因此， N的素因數(shù)不可能都是 8k ? 1的形式，即至少有一個(gè) q， q?N， q具有 8k ? 3的形式。顯然 q ? pi（ 1 ? i ? t）。這與個(gè)數(shù)有限的假設(shè)矛盾。因此，形如 8k ? 3（ k?Z）的素?cái)?shù)無(wú)窮多個(gè)。 習(xí) 題 六 1. 已知 769與 1013是 素?cái)?shù)，判定方程 (ⅰ ) x2 ? 1742 (mod 769)； (ⅱ ) x2 ? 1503 (mod 1013)。 是否有解。 2. 求所有的素?cái)?shù) p，使得下面的方程有解： x2 ? 11 (mod p)。 3. 求所有的素?cái)?shù) p，使得 ?2?QR(p)， ?3?QR(p)。 4. 設(shè) (x, y) = 1，試求 x2 ? 3y2的奇素?cái)?shù)因數(shù)的一般形式。 5. 證明：形如 8k ? 5（ k?Z）的素?cái)?shù)無(wú)窮多個(gè) 。 6. 證明：對(duì)于任意的奇素?cái)?shù) p，總存在整數(shù) n，使得 138 p?(n2 ? 1)(n2 ? 2)(n2 ? 2)。 第七節(jié) Jacobi符號(hào) 在上一節(jié)中我們看到，對(duì)于奇 素 數(shù) p， 利用計(jì)算 Legendre 符號(hào)可以判定方程 x2 ? a (mod p) (1) 是否有解。對(duì)于一般的正整數(shù) m， 如果它的標(biāo)準(zhǔn)分解式是 kkpppm ??? ?21 21? ， 那么，由第二節(jié)定理 4和第三節(jié)定理 可知，判定方程 x2 ? a (mod m) (2) 是否有解，歸結(jié)為對(duì)形如方程 (1)（ p = pi， 1 ? i ? 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 = p1p2? pk， 其中 pi（ 1? i ? k）是奇素?cái)?shù)，對(duì)于任意的整數(shù) a， 定義 )())(()( 21 kpapapama ?? ， 其中右端的 )(ipa （ 1? i ? k）是 Legendre符號(hào)，稱 )(ma 是 Jacobi符號(hào)。 例如，取 m = 45 = 3?3?5， 則 。，13235)1(5352832832845281)1(52523232452)()()())()(()()())()(()(215213815 2????????????????? 注 1：當(dāng) m是 奇 素?cái)?shù)時(shí)， Jacobi符號(hào)就是 Legendre符號(hào)。前者是后者的推廣。 139 注 2：如果 m是 奇 素?cái)?shù)，當(dāng) )(ma= 1時(shí)，方程 (2)有解。當(dāng) m不是奇 素?cái)?shù)時(shí)，這個(gè)結(jié)論不一定成立。例如，方程 x2 ? 5 (mod 9)無(wú)解，但是 ))(()( 353595 ? = 1。 盡管如此，利用雅各比符號(hào)仍可對(duì)方程 (2)的無(wú)解性給 出判斷。事實(shí)上，如果方程 (2)有解， m = p1p2? pk， 則對(duì)于每個(gè) pi（ 1? i ? k），當(dāng) p = pi時(shí)方程 (1)有解，因此，由雅各比符號(hào)的定義可知 )(ma = 1。 這樣，若)(ma = ?1，則方程 (2)必?zé)o解。 下面，我們研究雅各比符號(hào)的計(jì)算方法。 定理 1 使用定義 1中的符號(hào)，下面的結(jié)論成立： (ⅰ ) 若 a ? a1 (mod m)， 則 )()( 1mama ? ； (3) (ⅱ ) )(1m = 1； (ⅲ ) 對(duì)于任意的整數(shù) a1, a2, ? , at，有 )())(()( 2121 mamamam aaa tt