二次剩余理论试题及答案

二次剩余理论试题及答案1、已知素数P判别同余方程X2≡a(modP)是否有解。即计算fa]=1或-1。IP)2、已知a，求所有使及fa]=i或fa]=-1的P的一般形式。Ip) Ip)3、在[a[=1的条件下，如何求出x2≡a(m°dP)的解。若A为一个解，则另一个kP)解为-X1。上述已叙述了问题(1)、(2)，现在只剩下解(3)解的方法。除了书上介绍的公方法，我们再补充另一个方法即高斯逐步淘汰法。补充知识高斯逐步淘汰法：首先，不妨设0<a<p是0<X<P，故X2<p2，2 4因解同余方程x2≡a(modP)(1)相当于不定方程X2=a+py故0<yX2—ax2p <——<—pp4因而在求y的值时，不必考虑大号的整数，这就大大缩小了讨论的范围。其次，任取素数qWp，求出q的平方非剩余为a1,a2as并以v1,v2, Vs表示同余方程a+py≡a1(modq),a+py≡a2(modq)， a+py≡as(modq)的解，由于平方数一定为任何模的平方剩余，故若取y≡vi(modq)，则a+py是q的平方非剩余，因而a+py一定不是平方数。而不能有X2=a+py这样可淘汰满足y≡vi(modg)的各个y的值。取不同的q，淘汰y的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出(1)的解。例：解同余方程X2≡73(mod137),一(73)一 、，…一解•・•——=1,・・小2三73(0。讥37)有二个解1137)因为p=137，故0<y≤34取q=3,则2为3—平方非剩余。解同余方程73+137y≡3(mod3)得y≡2(mod3),从不大于34的正整数中淘汰形如y=2+3t的数，即有下面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),再从前面的数中淘汰形如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的三个平方非剩余的同余方程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。将上述数代入137y+73=χ2及137×3+73=484=22故x≡±22(mod137)为本题同余方程的解。例1：设p=4n+3是素数，试证当q=2P+1也是素数时，梅素数MP不是素数。q—1证：•/q=8n+7,24n+3=22三(2、一三1(modq)Iq)・•・q|24n+3-1,即q|MP,ΛMP不是素数。例2：若3是素数p平方剩余，问p是什么形式的素数?(3、解：•・•由反转定律-=(—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的素数有无穷多个。证：假设形如4m+1的素数只有有限个，设为PI…Pk,显然(2pI…Pk)2+1的最小素因数p是奇数，且p与pI…pk不同，设P为4m+3形的素数，但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的素数只有k个矛盾。例4：证明不定方程X2+23ʃ=17无解。证：只要证X2≡17(mod23)无解即可，∙.∙17≡1(mod4)旦(23)(2316(17)，17、-(3)2工

(17)(17)3)=-13[21(17)(・•・X2≡17(mod23)无解，即原方程无解。例5设X为整数，证明形如X2+1的整数的所有奇因数都有4h+1的形式，(其中h为整数)证：设2n+1是整数X2+1的任一奇素因数，于是有X2+1三0(mod2n+1),艮口X2三-1(mod2n+1).可以证明，这时X2三0(mod2n+1)，否则有1三0(mod2n+1)，这是不可能的。因此，由2n+1是奇素数，便有(X2,2n+1)=1。从而(X,2n+1)=1，这样由费马定理，有X2n三1(mod2n+1)。但是X2n=(X2)n三(-1)n(mod2n+1),因此有(-1)n三1(mod2n+1).由此可知，n必为偶数，记n=2h便有2n+1=4h+1.这样便证明了整数X2+1的的所有奇素因数形式必为4h+1形式。又由于两个4h+1形式的数的乘积仍为4h+1形式的数，故X2+i形式的数的奇因数必为4h+1形式的数。证2：由上面可知，-1是模2n+1的平方剩余，即(」)=1(2n+1),其中2n+1是奇素数。由定理3知2n+1三1(mod4)从而2n三0(mod4)，故n三0(mod2)，所以n是偶数，其余同上。例6：证明：形如P三1(mod8)的素数有无穷多个。证：设N是任意正整数，P,P,...,P是不超过N的一切形如P=1(mod8)的素数。12 s记q=(2p1p2...Ps)4+1。显然q的任意素因数Q异于2,且X=2pIp2...Ps是同余式X4+1=0(moda)的解。由a=1(mod8)•又由于是Pi(i=1,2,...,S)不是q的因数，故α≠P1(i=1,2,...,S)，从而a>N。因此形如P=1(mod8)的素数有无穷多个。例7：解如下二次同余式X2=11(mod125)解：(1)125=53。先解X2三11=1(mod5)。它的一个解是x=1。再解X2=11(mod52)。令X=1+5y，则有(1+5y)2=11(mod52).化简得(1+10y)=11(mod52)，得到y=1(mod5),从而有5y=5(mod52)，1+5y=6(mod52)，所以X2=11(mod52)的一个解为X=6,最后解X2=11(mod53)。设X=6+52Z。代入有(6+52z)2=11(mod53)，化简得12.52Z=-25(mod53).艮^12Z三-1(mod5).它的一个解是Z=2.因此X=6+25.2=56是同余式X2三ιι(mod)125的一个解,所以由定理,X2三11(mod)125的两个解是X三56(mod)125,X三-56(mod)125.例8:判断同余方程X2三286(mod443)是否有解。解：286=2X143，433是素数，(143，443)=1奇数143不是素数，但可用判定可比符号计算的生勒让德符号