二次剩余理論試題及答案1、已知素?cái)?shù)P判別同余方程X2≡a(modP)是否有解。即計(jì)算fa]=1或-1。IP)2、已知a，求所有使及fa]=i或fa]=-1的P的一般形式。Ip) Ip)3、在[a[=1的條件下，如何求出x2≡a(m°dP)的解。若A為一個(gè)解，則另一個(gè)kP)解為-X1。上述已敘述了問(wèn)題(1)、(2)，現(xiàn)在只剩下解(3)解的方法。除了書(shū)上介紹的公方法，我們?cè)傺a(bǔ)充另一個(gè)方法即高斯逐步淘汰法。補(bǔ)充知識(shí)高斯逐步淘汰法：首先，不妨設(shè)0<a<p是0<X<P，故X2<p2，2 4因解同余方程x2≡a(modP)(1)相當(dāng)于不定方程X2=a+py故0<yX2—ax2p <——<—pp4因而在求y的值時(shí)，不必考慮大號(hào)的整數(shù)，這就大大縮小了討論的范圍。其次，任取素?cái)?shù)qWp，求出q的平方非剩余為a1,a2as并以v1,v2, Vs表示同余方程a+py≡a1(modq),a+py≡a2(modq)， a+py≡as(modq)的解，由于平方數(shù)一定為任何模的平方剩余，故若取y≡vi(modq)，則a+py是q的平方非剩余，因而a+py一定不是平方數(shù)。而不能有X2=a+py這樣可淘汰滿(mǎn)足y≡vi(modg)的各個(gè)y的值。取不同的q，淘汰y的值，直至留下的數(shù)較少是計(jì)算不太麻煩時(shí)，即可直接代入并求出(1)的解。例：解同余方程X2≡73(mod137),一(73)一 、，…一解???——=1,??小2三73(0。譏37)有二個(gè)解1137)因?yàn)閜=137，故0<y≤34取q=3,則2為3—平方非剩余。解同余方程73+137y≡3(mod3)得y≡2(mod3),從不大于34的正整數(shù)中淘汰形如y=2+3t的數(shù)，即有下面1,3,4,6,7,9,10,12,13,15,16,18,19,21,22,24,25,27,28,30,31,33,34。再取q=5,2,3為8的平方非剩余的同余方程73+137y≡2(mod5) ,73+137y≡3(mod5)解為y≡2(mod5),y≡0(mod5),再?gòu)那懊娴臄?shù)中淘汰形如y=2+5t和y=5t,有下面1,3,4,6,9,13,16,18,19,21,24,28,31,33,34。又取q=7,3,5,6為g的三個(gè)平方非剩余的同余方程73+137y≡3,5,6(mod7)的y≡0,4,6(mod7)淘汰y=4+7t,7t,6+7t,就只留下了1,3,9,16,19,24,31,33。將上述數(shù)代入137y+73=χ2及137×3+73=484=22故x≡±22(mod137)為本題同余方程的解。例1：設(shè)p=4n+3是素?cái)?shù)，試證當(dāng)q=2P+1也是素?cái)?shù)時(shí)，梅素?cái)?shù)MP不是素?cái)?shù)。q—1證：?/q=8n+7,24n+3=22三(2、一三1(modq)Iq)???q|24n+3-1,即q|MP,ΛMP不是素?cái)?shù)。例2：若3是素?cái)?shù)p平方剩余，問(wèn)p是什么形式的素?cái)?shù)?(3、解：???由反轉(zhuǎn)定律-=(—1)

Ip)P=I

2?(P1,注意到P>3,P只能為p≡+1(mod3)且(P]=

I3)P三1(mod4)P三—1(mod4)1—1(P[=1只能下列情況R三1(mod3)p三1(mod4)P三-1(mod3)P三-1(mod4)??p三1(mod12)或p三-1(mod12)例3：證明形如4m+1的素?cái)?shù)有無(wú)窮多個(gè)。證：假設(shè)形如4m+1的素?cái)?shù)只有有限個(gè)，設(shè)為PI…Pk,顯然(2pI…Pk)2+1的最小素因數(shù)p是奇數(shù)，且p與pI…pk不同，設(shè)P為4m+3形的素?cái)?shù)，但P整除(2PI…Pk)2+1,表明(2PI…pk)2+1≡0(modP).. /、 (—I? p-1 一即X2≡(-1)(modP)有解，即［-1‰1,但一三(-1)2三(-1)2m+1=-1矛盾，(PJ(P)???p為4m+1形，這與4m+1的素?cái)?shù)只有k個(gè)矛盾。例4：證明不定方程X2+23?=17無(wú)解。證：只要證X2≡17(mod23)無(wú)解即可，?.?17≡1(mod4)旦(23)(2316(17)，17、-(3)2工

(17)(17)3)=-13[21(17)(???X2≡17(mod23)無(wú)解，即原方程無(wú)解。例5設(shè)X為整數(shù)，證明形如X2+1的整數(shù)的所有奇因數(shù)都有4h+1的形式，(其中h為整數(shù))證：設(shè)2n+1是整數(shù)X2+1的任一奇素因數(shù)，于是有X2+1三0(mod2n+1),艮口X2三-1(mod2n+1).可以證明，這時(shí)X2三0(mod2n+1)，否則有1三0(mod2n+1)，這是不可能的。因此，由2n+1是奇素?cái)?shù)，便有(X2,2n+1)=1。從而(X,2n+1)=1，這樣由費(fèi)馬定理，有X2n三1(mod2n+1)。但是X2n=(X2)n三(-1)n(mod2n+1),因此有(-1)n三1(mod2n+1).由此可知，n必為偶數(shù)，記n=2h便有2n+1=4h+1.這樣便證明了整數(shù)X2+1的的所有奇素因數(shù)形式必為4h+1形式。又由于兩個(gè)4h+1形式的數(shù)的乘積仍為4h+1形式的數(shù)，故X2+i形式的數(shù)的奇因數(shù)必為4h+1形式的數(shù)。證2：由上面可知，-1是模2n+1的平方剩余，即(」)=1(2n+1),其中2n+1是奇素?cái)?shù)。由定理3知2n+1三1(mod4)從而2n三0(mod4)，故n三0(mod2)，所以n是偶數(shù)，其余同上。例6：證明：形如P三1(mod8)的素?cái)?shù)有無(wú)窮多個(gè)。證：設(shè)N是任意正整數(shù)，P,P,...,P是不超過(guò)N的一切形如P=1(mod8)的素?cái)?shù)。12 s記q=(2p1p2...Ps)4+1。顯然q的任意素因數(shù)Q異于2,且X=2pIp2...Ps是同余式X4+1=0(moda)的解。由a=1(mod8)?又由于是Pi(i=1,2,...,S)不是q的因數(shù)，故α≠P1(i=1,2,...,S)，從而a>N。因此形如P=1(mod8)的素?cái)?shù)有無(wú)窮多個(gè)。例7：解如下二次同余式X2=11(mod125)解：(1)125=53。先解X2三11=1(mod5)。它的一個(gè)解是x=1。再解X2=11(mod52)。令X=1+5y，則有(1+5y)2=11(mod52).化簡(jiǎn)得(1+10y)=11(mod52)，得到y(tǒng)=1(mod5),從而有5y=5(mod52)，1+5y=6(mod52)，所以X2=11(mod52)的一個(gè)解為X=6,最后解X2=11(mod53)。設(shè)X=6+52Z。代入有(6+52z)2=11(mod53)，化簡(jiǎn)得12.52Z=-25(mod53).艮^12Z三-1(mod5).它的一個(gè)解是Z=2.因此X=6+25.2=56是同余式X2三ιι(mod)125的一個(gè)解,所以由定理,X2三11(mod)125的兩個(gè)解是X三56(mod)125,X三-56(mod)125.例8:判斷同余方程X2三286(mod443)是否有解。解：286=2X143，433是素?cái)?shù)，(143，443)=1奇數(shù)143不是素?cái)?shù)，但可用判定可比符號(hào)計(jì)算的生勒讓德符號(hào)