《数论算法》教案4章(二次同余方程与平方剩余).doc

《《数论算法》教案4章(二次同余方程与平方剩余).doc》由会员分享，可在线阅读，更多相关《《数论算法》教案4章(二次同余方程与平方剩余).doc（49页珍藏版）》请在三一文库上搜索。

1、第 4 章 二次同余方程与平方剩余内容1. 二次同余方程，平方剩余2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解4.1 一般二次同余方程(一) 二次同余方程bxc0（mod m），（a0（mod m） （1）(二) 化简设m，则方程（1）等价于同余方程问题归结为讨论同余方程bxc0（mod ）， （pa） （2）(三) 化为标准形式p2，方程（2）两边同乘以4a，44abx4ac0（mod ）4ac（mod ）变量代换，1 / 49y2axb （3）有4ac（mod ） （4）当p为奇素数时，方程（4）与（2）等价。即l 两者同时

2、有解或无解；有解时，对（4）的每个解，通过式（3）（x的一次同余方程，且（p, 2a）1，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解；反之亦然。l 两者解数相同。结论：只须讨论以下同余方程a（mod ） （5）【例】化简方程7x25x20（mod 9）为标准形式。（解）方程两边同乘以4a4×728，得196x2140x560（mod 9）配方 (14x5) 225560（mod 9）移项 (14x5) 281（mod 9）变量代换 y14x5得 y20（mod 9）（解之得y0, ±3，从而原方程的解为x(y5) (y5)2(y5)2y102y

3、17, 1, 54, 1, 2（mod 9）(四) 二次剩余【定义4.1.1】设m是正整数，a是整数，ma。若同余方程a（mod m） （6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。问题：（1） 设正整数a是模p的平方剩余，若记方程（6）中的解为x（mod m），那么此处的平方根（mod m）与通常的代数方程a的解有何区别？（2） 如何判断方程（6）有解？（3） 如何求方程（6）的解？(五) 例【例1】1是模4平方剩余，1是模4平方非剩余。【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。【例3】直接计算12，22，142得模1

4、5的平方剩余（实际上只要计算（12，22，72）1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例4】求满足方程E：x1（mod 7）的所有点。（解）对 x0，1，2，3，4，5，6分别解出y：0，1（mod 7），y1，6（mod 7）1，3（mod 7），无解2，4（mod 7），y2，5（mod 7）3，3（mod 7），无解4，6（mod 7），无解5，5（mod 7），无解6，6（mod 7），无解所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。说明：方程E：x1的图形称为椭圆曲线。4.2 模为奇素数的平方剩余与平方非剩余模为素

5、数的二次方程a（mod p）, (a, p)1 （1）因为，故方程（1）要么无解，要么有两个解。(一) 平方剩余的判断条件【定理4.2.1】（欧拉判别条件）设p是奇素数，(a, p)1，则（i）a是模p的平方剩余的充要条件是 1（mod p） （2）（ii）a是模p的平方非剩余的充要条件是 1（mod p） （3）并且当a是模p的平方剩余时，同余方程（1）恰有两个解。（证）先证pa时，式（2）或（3）有且仅有一个成立。由费马定理 1（mod p）10（mod p）0（mod p） （4）即 但 1或2且素数p>2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）

6、所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。（i）必要性。若a是模p的二次剩余，则必有使得a（mod p），因而有 （mod p）。即 （mod p）。由于pa，所以p，因此由欧拉定理知1（mod p）。即（2）式成立。充分性。已知 1（mod p），这时必有pa。故一次同余方程a（mod p）, (1bp1) （5）有唯一解，对既约剩余系(p1)/2，1，1，(p1)/2 （6）由式（6）给出的模p的既约剩余系中的每个j，当bj时，必有唯一的属于既约剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有。这样，既约剩余系（6）中的p1个数就可按j、xj作为一对，两两分

7、完。（b1b2，则相应的解x1x2，且除了±1之外，每个数的逆不是它本身）因此有由威尔逊定理知与式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。（ii）由已经证明的这两部分结论，立即推出第（ii）条成立。其次，若0（mod p）是方程（1）的解，则也是其解，且必有（mod p）。故当(a, p)1时，方程（1）要么无解，要么同时有两个解。（说明：本定理只是一个理论结果，当p>>1时，它并不是一个实用的判断方法）小结：对于任何整数a，方程（1）的解数可能为T(x2a；p)0, 1, 2【例1】设p19，验证定理4.2.1的证明过程。（解）由费马定理知，

8、对任何a1, 2, , 18，都有1（mod 19）。方程1（mod 19）只有两个解，即x±1（mod 19）。从而必有±1（mod 19）（视1（mod 19），即）针对必要性：例如a17是模19的二次剩余，即存在6使得17（mod 19）。那么必有1（mod 19）针对充分性：例如a6，1（mod 19），验证6是二次剩余。解方程6（mod 19）, (1b18)当b1, 2, 3, 4, 5, , 17, 18（mod 19）时，方程有唯一解x6, 3, 2, 11, 5, , 16, 13（mod 19）其中 556（mod 19）即当b5时，x5。所以6是二次剩

9、余。又选a8，1（mod 19），验证：解方程8（mod 19）, (1b18)得 188， 248， 398， 428， 5138， 6148， 7128， 818，938， 10168， 11188， 1278，1358， 1468， 15178， 16108，17158， 181181218(18)( 24)( 39)( 513)( 614)( 712)( 1016)( 1118)( 1517)1（mod 19）【例2】判断137是否为模227的平方剩余。（解）首先，227是素数。其次，计算1（mod 227）所以，137是模227的平方非剩余。【推论】设p是奇素数，(a1, p)1，(

10、a2, p)1，则（i）若a1，a2都是模p的平方剩余，则a1a2是模p的平方剩余；（ii）若a1，a2都是模p的平方非剩余，则a1a2是模p的平方剩余；（iii）若a1是模p的平方剩余，a2是模p的平方非剩余，则a1a2是模p的平方非剩余。（证）因(二) 平方剩余的个数【定理4.2.2】设p是奇素数，则模p的既约剩余系中平方剩余与平方非剩余的个数各为(p1)2，且(p1)2个平方剩余恰与序列12，22，中的一个数同余。（证）由定理4.2.1，模p的平方剩余个数等于方程1（mod p）的解数。但由定理3.4.5知，方程的解数为，即平方剩余的个数是，且平方非剩余的个数是(p1)。其次，可以证明当

11、1k1，1k2，且k1k2时，有 mod p。故结论成立。（定理3.4.5：设p为素数，n为正整数，np。则同余方程0 mod p有n个解被除所得余式的所有系数都是p的倍数）4.3 勒让德符号目的：快速判断整数a是否为素数p的平方剩余。(一) 勒让德符号【定义4.3.1】设p是素数，定义勒让德（Legendre）符号为：L(a, p)【推论】整数a是素数p的平方剩余的充要条件是1。（证）由定义4.3.1。因此，判断平方剩余转化为计算勒让德符号的值。【例1】直接计算，得11（注：本例仍是利用平方剩余而得到勒让德符号值）问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。(二) （勒让德符号

12、的）性质【性质1】（欧拉判别法则）设p是奇素数，则对任意整数a，有（mod p）（证）由定理4.2.1即知。【性质2】1（证）显然（因为方程x21（mod p）始终有解x±1（mod p），或者由性质1立得）。【性质3】。（证）由性质1即得。【例2】1，1【推论】（证）p1（mod 4） p4k11p3（mod 4） p4k31另一种描述：设素数p>2，则1是模p的二次剩余的充分必要条件是p1（mod 4）。【性质4】（证）因x2ap（mod p） x2a（mod p）【推论】若ab（mod p），则【性质5】（证）因【推论1】【推论2】当pa时，1讨论：确定a是否是模p的平方

13、剩余就变为如何计算Legendre符号的值。上述性质可以用来计算，并由算术基本定理，设a 的分解式为±， （t0, 1）则（t0, 1）故只要能计算出，就可以计算出任意的，其中是小于p的素数。已经解决的计算：剩余的问题：，的计算。解决这些问题的基础是下面的二次互反律（Gauss定理）。【性质6】【例3】1，1，故2是模17的平方剩余，但不是模19的平方剩余。【推论】p为奇素数，则（证）因为当p8k1时k(8k2)偶数当p8k3时(2k1)(4k1)奇数【例4】由于3171（mod 8），593（mod 8），故1，1，即2是模31的平方剩余，但不是模59的平方剩余。【性质7】（二次互

14、反律，高斯定理）pq且均为奇素数，则另一表示形式：说明1：符号和分别刻画了二次同余方程q（mod p）和p（mod q）是否有解，即q是否是模p的二次剩余和p是否是模q的二次剩余，其中正好是模与剩余互换了位置，而性质7恰好刻画了两者之间的关系，故称为二次互反律。说明2：由欧拉提出，高斯首先证明。已有一百五十多个不同的证明。由二次互反律引伸出来的工作，导致了代数数论的发展和类域论的形成。【推论】（i）设奇素数p、q中至少有一个模4为1，则方程q（mod p）有解方程p（mod q）有解（ii） 若pq3（mod 4），则方程q（mod p）有解方程p（mod q）无解（证）（i）设p1（mod

15、4），即p4k1，则（ii）此时，p4s3，q4t3，则【例5】判断3是否是模17的平方剩余。（解）1所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）【例6】判断同余方程137（mod 227）是否有解。（解）已知137与227均为奇素数，所以1所以，方程无解。另法：1【例7】判断同余方程1（mod 365）是否有解，若有解，求解数。（解）由于3655·73，所以1（mod 365） 1所以方程有解，且解数为4。【例8】判断同余方程2（mod 3599）是否有解，若有解，求解数。（解）由于359959·61，所以2（mod 3599）

16、 因为593（mod 8），即1，故方程2（mod 59）无解，从而原方程无解。【例9】证明形如4k1的素数有无穷多。（证）反证法：不然，形如4k1的素数为有限个，设为，令4b1即a 也形如4k1且a（i1,2, k）。所以a 为合数，设其素因数p 为奇数，则1所以1为模p平方剩余。由性质3的推论，p1（mod 4），即p也是形如4k1的素数。（【推论】）但显然p（i1, 2, k），矛盾（否则，且由pa知p1）。4.4 二次互反律的证明(一) 证明(二) 应用【例1】求所有奇素数p，它以3为其平方剩余。（解）即求所有奇素数p，使得1。易知p3。由二次互反律因为以及（排除偶数）知1 或 即p1

17、（mod 12）或p1（mod 12）故3是模p二次剩余 p±1（mod 12）【例2】设p为奇素数，d是整数。若1，则p一定不能表示为的形式。（证）用反证法。设p有表达式，则由p是素数可知(x, p)(y, p)1。这是因为若(x, p)1，则必有 但由1知(d, p)1，所以py2，进而py。那么p2x2，p2y2 p2x2dy2p矛盾。（即(x, p)(y, p)1成立）由(x, p)(y, p)1知，±1，±1，从而1与题设矛盾。【性质8】同余方程的解数是。【问题】求所有奇素数p，它以5或2为其平方剩余。4.5 雅可比符号（1） 问题：在计算勒让德符号时，

18、若a为奇数，但非素数，如何快速计算。（2） 目的：为了快速计算勒让德符号。(一) 雅可比符号【定义4.5.1】设m是奇素数的连乘积（可以重复），对任意整数a，定义雅可比（Jacobi）符号为：J(a, m)说明：（1） 上式右端的为勒让德符号，即J(a, m)（2） 雅可比符号形式上是勒让德符号符号的推广。但与勒让德符号意义不同。（3） 两者的本质区别：勒让德符号可用来判断平方剩余，但雅可比符号却不能。即当k1时，如果J(a, m)1，则方程a（mod m）无解（因为至少存在一个，使得1，即方程a（mod ）无解，从而原方程a（mod m）也无解），但当J(a, m)1时，方程a（mod m）

19、则不一定有解。（4） 当k1时，J(a, m) L(a, m)，即此时勒让德符号的值与雅可比符号的值相等。（5） 因此，求勒让德符号的值转化为计算雅可比符号。【例1】由定义4.5.1(1)(1)1但可以验证2是模9的平方非剩余。又如当奇素数p3（mod 4）时，由勒让德符号的性质知，1是模P的非平方剩余，即方程1（mod p）无解，从而方程1（mod ）也无解。即1是模的平方非剩余。但若取m，则总有(1)(1)1问题：如何快速计算雅可比符号的值，以帮助加速勒让德符号的求值过程，从而加速判断平方剩余。(二) （雅可比符号的）性质【性质1】若(a, m)1，则J(a, m)±1；若(a,

20、 m)1，则J(a, m)0。（证）因(a, m)1时，至少有某个，即0，从而0。【例2】a15，m39，则J(a, m)00【性质2】1（证）J(1, m)1【性质3】（证）因为1故 m1（mod 4），即m1（mod 4）（mod 2）所以J(1, m) 【推论】（证）m1 mod 4 m4k113 mod 4 m4k31【例3】1，1【性质4】（证）首先，由m和maa（mod m）知maa（mod ）其次，由雅可比符号和勒让德符号性质知【推论】若ab（mod m），则（证）显然【性质5】（证）因····【推论1】【推论2】当(m, a)1时，1【性

21、质6】（证）因为1 1（mod 64）而对任何奇数q，都有1（mod 8）（i1,2, k），故（mod 8）（mod 2）所以 J(2, m) 【推论】m为奇数，则（证）因为当m8k1时k(8k2)偶数当m8k3时(2k1)(4k1)奇数【例4】1，1。【性质7】（二次互反律，高斯定理）设m、n都是奇数，则或 【性质8】、a为整数，则（证）设，则左边J(n, ) J(a, )·J(a, )右边这样，计算勒让德符号的值就转化为了计算雅可比符号的值。而后者的求值要比前者快了许多。【例5】用雅可比符号计算：(i) L(51, 71) (ii) L(35, 97)(iii) L(313,

22、401) (iiii) L(165, 503)（解）(i) 1(ii) 1(iii) 1(iv) 1【例6】同余方程286（mod 563）是否有解。（解）563为素数，计算勒让德符号1所以，原方程无解。【例7】判断同余方程88（mod 105）是否有解。（解）1053·5·7为合数，直接计算雅可比符号1所以，原方程无解。（因为原方程等价于方程组，而方程组有解的充分必要条件是勒让德符号1。但1，说明、三者中至少有一个为1，即方程组中至少有一个方程无解，从而原方程无解）。再次说明雅可比符号可以用来否定方程有解，但不能肯定方程有解。【例8】求同余方程38（mod 385）的解数

23、。（解）3857·5·11为合数，直接计算雅可比符号11并不能肯定原方程是否有解。所以，还须判断方程组中的每个方程是否有解。故再计算勒让德符号1，因此方程38（mod 5）无解，最终说明原方程解数为零。4.6 模p平方根（1） 目的：解同余方程a（mod p），p为素数且pa （1）（2） 方法：逐步迭代设p1s。(一) 理论基础理论基础：a是模p的平方剩余的充要条件（欧拉定理）Z1（mod p）若t>1则（偶数）±1（mod p）若1（mod p）且t2，继续开方；否则，构造N，使1（mod p）又可以继续开方。其中N为模p的平方非剩余（即）。目标：构造，

24、使得：a（mod p）从而得方程（1）的解：x±（mod p）(二) 算法将偶数p1表为p1s，t1，s为奇数。（1）选模p的平方非剩余N，即1，令b（mod p），则有1（mod p）1（mod p）即b是模p的次单位根，但非模p的次单位根。（2）计算： （mod p）则y满足方程： 1（mod p）（因1（mod p）即y是模p的次单位根。（3）若t1，则x（mod p）满足方程a（mod p）（此时p12s，a（mod p）。即方程已经解出）否则，t2，寻找，使得y满足方程1（mod p）即y是模p的次单位根。（a）若1（mod p）令0，（mod p），则即为所求。（b）若1

25、（mod p）令1，b（mod p），则即为所求。（因(1)(1)1（mod p）（4）若t2，则x（mod p）满足方程a（mod p）（此时p1s，a（mod p）否则，t3，寻找，使得y满足方程1（mod p）即y是模p的次单位根。（a）若1（mod p）令0， （mod p），则即为所求。（b）若1（mod p）令1，（mod p），则即为所求。依次类推（k1）设找到整数满足1（mod p）即y是模p的次单位根：1（mod p）（k2）若tk，则x（mod p）满足方程a（mod p）否则，tk1，寻找整数，使得y满足方程1（mod p）即y是模p的次单位根。（a）若1（mod p）令

26、0，（mod p），则即为所求。（b）若1（mod p）令1，（mod p），则即为所求。最后，kt1：（mod p）满足方程：a（mod p），p为素数且pa(三) 例【例1】用上述方法解同余方程186（mod 401）（解）a186，p401。判断：p401为素数，且（用雅可比符号计算）1·11或（用勒让德符号计算）1·(1) ·(1)1故原方程有解。准备：p14011400·25，其中t4，s25。（1）由上边计算，1，即N3是模401的平方非剩余。令b268（mod 401）。（2）计算103（mod 401）235（mod 401）（3）因为1

27、（mod 401）故令1，103·268336（mod 401）。（此时，）（4）因为1（mod 401）故令0，336（mod 401）。（此时，）（5）因为235·1（mod 401）故令1，336·304（mod 401）。（此时，）则304（mod 401）满足原方程。（验证，92416186（mod 401）【例2】设p是形为4k3的素数，若方程a（mod p）有非零解，则其解为x±（mod p）（解）因为p4k3，故q为奇数，而方程a（mod p）有解，则a是模p的二次剩余，从而有1（mod p）即 1（mod p）已知原方程有非零解，即（a

28、, p）1，故有a（mod p）即a（mod p） x±±±（mod p）【例3】设pq均为形如4k3的素数，且1，求解同余方程：a（mod pq）（解）首先a（mod pq）而两个方程的解分别为（mod p）和（mod q）利用中国剩余定理解联立方程得原方程的解为（mod p）uq±（mod q）vp （mod pq）其中，1（mod p）， vp1（mod q）【例3】解同余方程3（mod 253）。（解）25311·23，1123，二者均为形如4k3的素数，且1，解方程 3（mod 11），得±±5（mod 11）解方

29、程3（mod 23），得±±7（mod 23）利用中国剩余定理解联立方程M11·23253，11，计算1（mod 11），21（mod 23） ±5·23·1±7·11·21（mod 253）±115±99±16，±39，（mod 253）4.7 合数的情形方程a（mod m），（a, m）1 （1）a（mod ），（a, p）1 ，1 （3）(一) P为奇素数【定理4.7.1】设p是奇素数，则（3）有解1。且有解时，（3）的解数为2。（证）必要性a（mod ）有解

30、a（mod p）有解1充分性：设1，则存在整数x（mod p）使得a（mod p）令f(x)a，则2x，（2，p）1，故方程（3）的解数为2。【推论】同余方程（3）的解数为T1(二) P2a（mod ），（a, 2）1 ，1 （4）（当1时，方程a1（mod 2）有一个解x1（mod 2）【定理4.7.2】设1，则同余方程（4）有解的必要条件是（i） 当2时，a1（mod 4）；（ii） 当3时，a1（mod 8）。若上述条件成立，则（4）有解。且当2时，解数是2；当3时，解数是4。（证）必要性：若（4）有解，则存在整数z，使得a（mod ）由（a, 2）1知（z, 2）1，记z12t，则上式

31、可表为a14t(t1) （mod ） （5）（注：14t4）所以当2时，a1（mod 4）。而当3时，由（5）知a14t(t1) （mod 8）又由2t(t1)知，a1（mod 8）。充分性：（i）当2时，a1（mod 4），方程a1（mod ）显然有两个解 x1，3（mod ）（ii）当3时，a1（mod 8）。此时，若3，易验证方程a1（mod ） （6）的解为 x±1，±5（mod ），即±(1)，0, ±1, ±2或 ±()，0, ±1, ±2 （7）其中，x31, 5。若4，方程为a（mod ） （8）令

32、 a（mod ）（由第三章结论，希望从方程（6）的解的值（7）中去找方程（8）的解，即确定）即 2()a（mod ）亦即 a（mod ）a（mod ）所以 （mod 2）（mod 2）（注意1（mod 2）或2，0, ±1, ±2代入（7），方程（8）的解可表为（±()，0, ±1, ±2 （7）±()，2，0, ±1, ±2±()，0, ±1, ±2或 ±()，0, ±1, ±2其中，且1（mod 2）。（因为a1（mod 8），故整数，从而为偶数）依次

33、类推，对于4，设同余方程a（mod ） （9）的解为±()，0, ±1, ±2 （10）或±()（mod ），0, 1且1（mod 2）。为了从方程（9）的上述解的值（10）中找出方程a（mod ） （11）的解，令a（mod ）即2()a（mod ）亦即a（mod ）a（mod ） （12）所以（mod 2）（mod 2）或2，0, ±1, ±2代入（10）式，方程（11）的解可表为（±()，0, ±1, ±2 （10）±()，2，0, ±1, ±2即 ±()，0

34、, ±1, ±2或±()，0, ±1, ±2其中，且1（mod 2）。（因为由式（12）可知整数，从而为偶数）【例1】解方程57（mod 64）。（解）64，即6。因571（mod 8），故方程有4个解。3时，解的值为x±(1)，0, ±1, ±2 （13）（解的表示：x1，3，5，7（mod 8），或 x±1，±5±7，±3（mod 8）或 x±(14t)±(34 t)（mod 8），t 0, 1还可表为： x±1，±3±7

35、，±5（mod 8）或 x±(12t)±(52 t)（mod 8），t 0, 1此时方程为571（mod 8）（1）4时，在式（13）的所有值中找方程 57（mod ） （14）的解。为此，令 57（mod ）则2·1· (4)57（mod ）即·1·57（mod ）·1·57（mod ）1·1（mod 2）1（mod 2）或212，0, ±1, ±2代入（13）式得方程（14）的解为（x±(1)，0, ±1, ±2 （13）x±(1&

36、#183;1)±(5)，0, ±1, ±2或 x±(5)（mod ），0, 1或 x±5，±13±3，±5（mod ）（5）5时，令 57（mod ），则2·5· ()57（mod ）·5·57（mod ）5·0（mod 2）0（mod 2）或 022，0, ±1, ±2故方程 57（mod ）的解为x±(5·0)±(5)，0, ±1, ±2或 x±(5)（mod ），0, 1或 x&#

37、177;5，±21±5，±11（mod ）（5）6时，令 57（mod ），则2·5· ()57（mod ）·5·57（mod ）5·1（mod 2）1（mod 2）或12，0, ±1, ±2故方程 57（mod ）的解为±(5·1)±(21)，0, ±1, ±2或(21)（mod ），0, 1或±21，±53±11，±21（mod ）（21）4.8 解同余方程总结(一) 方法（1） 一般方程方程 f(x)

38、 0（mod m）化为等价方程组其中（2） 解素数幂方程f(x)0（mod ）， p为素数（3） deg(f)2，1，p2或奇素数的解法（4） deg(f)2，2，p2或奇素数的解法（5） deg(f)2，若已知1时的解，求2时的解(二) 问题（1）m的分解（2）deg(f)2，1时的解法习题41 求满足下列方程的所有整点：（1）E：（mod 7）；（2）E：（mod 7）；（3）E：（mod 17）；（4）E：（mod 17）。2 利用欧拉判别条件判断：（1）8是否是模53的二次剩余；（2）8是否是模67的二次剩余。3 求下列同余方程的解数：（1）2（mod 67）；（2）2（mod 67）

39、；（3）2（mod 37）； （4）2（mod 37）；（5）1（mod 221）； （6）1（mod 427）；4 计算下列勒让德符号：（1）； （2）； （3）；（4）； （5）； （6）；（7）； （8）； （9）；（10）； （11）； （12）。5 判断下列同余方程是否有解，若有解，请求其解数：（1）7（mod 227）； （2）249（mod 257）（3）79（mod 433）； （4）365（mod 389）（5）11（mod 511）；（6）2495（mod 5249）；（7）116（mod 91）； （8）514（mod 6193）。6 解下列同余方程：（1）60（mod

40、56）；（2）40（mod 32）7 按要求完成下列问题：（1） 求以3为其二次剩余的全体素数；（2） 求以±3为其二次剩余的全体素数；（3） 求以±3为其二次非剩余的全体素数；（4） 求以3为二次剩余、以3为二次非剩余的全体素数；（5） 求以3为二次剩余、以3为二次非剩余的全体素数；8 求以3为二次非剩余、以2为二次剩余的全体素数（即以3为正的最小二次非剩余的全体素数）。9 完成以下问题：（1） 求满足1的全体素数；（2） 求满足1的全体素数；（3） 求，的素因数分解式；（4） 判断方程25（mod 1013）是否有解。10 设素数4m1，dm。证明： 1。11 设是奇素数，pa。证明：存在整数u和v，使得0（mod ）的充分必要条件是a是模的二次剩余。其中1。12 设是奇素数，证明：（1） 模的所有二次剩余的乘积对模的剩余是；（2） 模的所有二次非剩余的乘积对模的剩余是；（3） 模的所有二次剩余之和对模的剩余是1（当3时）或0（当3时）；（4） 所有模的二次非剩余之和是多少？13 证明下列形式的素数均有无穷多个：（1）8k1，8k