数论算法教案 5章(二次同余方程与平方剩余)

PAGE/NUMPAGES二次同余方程与平方剩余 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 二次同余方程，平方剩余模为奇素数的平方剩余勒让德符号、雅可比符号二次同余方程的求解要点二次同余方程有解的判断与求解一般二次同余方程二次同余方程＋bx＋c≡0（modm），（a0（modm））（1）化简设m＝，则方程（1）等价于同余方程组＋bx＋c≡0（mod），（pa）（2）化为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形式p≠2，方程（2）两边同乘以4a，4＋4abx＋4ac≡0（mod）≡－4ac（mod）变量代换，y＝2ax＋b（3）有≡－4ac（mod）（4）当p为奇素数时，方程（4）与（2）等价。即两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（x的一次同余方程，且（p,2a）＝1，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解；反之亦然。两者解数相同。结论：只须讨论方程≡a（mod）（5）【例5.1.1】化简方程7x2＋5x－2≡0（mod9）为标准形式。（解）方程两边同乘以4a＝4×7＝28，得196x2＋140x－56≡0（mod9）配方(14x＋5)2－25－56≡0（mod9）移项(14x＋5)2≡81（mod9）变量代换y＝14x＋5得y2≡0（mod9）（解之得y＝0,±3，从而原方程的解为x≡(y－5)≡(y－5)≡2(y－5)≡2y－10≡2y－1≡－7,－1,5≡－4,－1,2（mod9））平方剩余【定义5.1.1】设m是正整数，a是整数，ma。若同余方程≡a（modm）（6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。【例】1是模4平方剩余，－1是模4平方非剩余。【例】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：设正整数a是模p的平方剩余，若记方程（6）中的解为x≡（modm），那么此处的平方根（modm）与通常的代数方程＝a的解有何区别？如何判断方程（6）有解？如何求方程（6）的解？例【例5.1.2】求以15为模的所有平方剩余和平方非剩余。（解）直接计算12，22，…，142得模15的平方剩余（实际只需计算12，22，…，72）1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例5.1.3】求满足方程E：≡＋x＋1（mod7）的所有整点（即坐标为整数的点）。（解）对x＝0，1，2，3，4，5，6分别解出y：＝0，≡1（mod7），y≡1，6（mod7）＝1，≡3（mod7），无解＝2，≡4（mod7），y≡2，5（mod7）＝3，≡3（mod7），无解＝4，≡6（mod7），无解＝5，≡5（mod7），无解＝6，≡6（mod7），无解所以，满足方程的点为（0,1），（0,6），（2,2），（2,5）。附：方程E：≡＋x＋1的图形称为椭圆曲线。模为奇素数的平方剩余与平方非剩余方程≡a（modp）,(a,p)＝1（1）结论：方程（1）要么无解，要么有两个解（因为＝）。（p＝时，方程恰好1个解）平方剩余的判断条件【定理5.2.1】（欧拉判别条件）设p是奇素数，(a,p)＝1，则（i）a是模p的平方剩余的充要条件是≡1（modp）（2）（ii）a是模p的平方非剩余的充要条件是≡－1（modp）（3）并且当a是模p的平方剩余时，同余方程（1）恰有两个解。（证）先证pa时，式（2）或（3）有且仅有一个成立。由费马定理≡1（modp）－1≡0（modp）≡0（modp）（4）即＝但＝1或2且p＞2。p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）由式（4）知式（2）或（3）有且仅有一式成立。（i）必要性：a是模p的二次剩余有使得≡a（modp），≡（modp）。即（modp）。由于pap，由欧拉定理≡1（modp）。充分性：≡1（modp）pa。故一次同余方程≡a（modp）,(1≤b≤p－1)（5）有唯一解，对既约剩余系（6）设b＝j时方程（5）的解（）。若a不是模p的二次剩余A中各数可按j、xj配对，两两分完。（b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它本身）即（威尔逊定理）与式（2）矛盾必有某个，使a是模p的二次剩余。（ii）显然（由（i）的证明即知）其次，若0（modp）是方程（1）的解，则－也是其解，且必有－（modp）。故当(a,p)＝1时，方程（1）要么无解，要么同时有两个解。（说明：本定理只是一个理论结果，当p>>1时，它并不是一个实用的判断方法）小结：对于任何整数a，方程（1）的解数可能为＝0,1,2【例5.2.1】设p＝19，验证定理5.2.1的证明过程。（解）由费马定理≡1（mod19），a＝1,2,…,18方程≡1（mod19）只有两个解，即x≡±1（mod19）。≡±1（mod19）（视≡1（mod19），即）针对必要性：【例】a＝17是模19的二次剩余，即存在≡6使得≡17（mod19）。有≡≡≡1（mod19）【2】≡2（mod19）无解，即a＝2是模19的二次非剩余。则≡－1（mod19）针对充分性：【例】a＝6，≡≡1（mod19），验证6是二次剩余。解方程≡6（mod19）,(1≤b≤18)b123456789101112131415161718x63211511814813其中5•5≡6（mod19）所以6是二次剩余。又选a＝8，≡≡－1（mod19），验证：解方程≡8（mod19）,1≤b≤18b123456789101112131415161718x8492131412131618756171015111•2•…•18≡(1•8)(2•4)(3•9)(5•13)(6•14)(7•12)(10•16)(11•18)(15•17)≡≡－1（mod19）【例2】判断137是否为模227的平方剩余。（解）首先，227是素数。其次，计算≡－1（mod227）所以，137是模227的平方非剩余。【推论】设p是奇素数，(a1,p)＝1，(a2,p)＝1，则（i）若a1，a2都是模p的平方剩余，则a1a2是模p的平方剩余；（ii）若a1，a2都是模p的平方非剩余，则a1a2是模p的平方剩余；（iii）若a1是模p的平方剩余，a2是模p的平方非剩余，则a1a2是模p的平方非剩余。（证）因＝平方剩余的个数【定理5.2.2】设p是奇素数，则模p的既约剩余系中平方剩余与平方非剩余的个数各为(p－1)／2，且(p－1)／2个平方剩余恰与序列12，22，…，中的一个数同余。（证）由定理5.2.1，模p的平方剩余个数等于方程≡1（modp）的解数。但由定理4.4.5知，方程的解数为，即平方剩余的个数是，且平方非剩余的个数是(p－1)－＝。其次，可以证明当1≤k1≤，1≤k2≤，且k1≠k2时，有modp。故结论成立。（定理4.4.5：设p为素数，n为正整数，n≤p。则同余方程＝≡0modp有n个解被除所得余式的所有系数都是p的倍数）勒让德符号目的：快速判断整数a是否为素数p的平方剩余。勒让德符号【定义5.3.1】设p是素数，定义勒让德（Legendre）符号为：L(a,p)＝＝【推论】整数a是素数p的平方剩余的充要条件是＝1。（证）由定义5.3.1。意义：判断平方剩余转化为计算勒让德符号的值。【例5.3.1】计算勒让德符号的值。其中a＝0,1,2,…,16。（解）直接计算：＝1＝－1（注：本例仍是利用平方剩余而得到勒让德符号值）问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。（勒让德符号的）性质【性质1】（欧拉判别法则）设p是奇素数，则对任意整数a，有＝（modp）（证）由定理5.2.1即知。【性质2】＝1（证）显然（因为方程x2≡1（modp）始终有解x≡±1（modp），或者由性质1立得）。【性质3】＝。（证）由性质1即得。【例2】＝1，＝－1【推论】＝（证）p≡1（mod4）p＝4k＋1＝＝＝1p≡3（mod4）p＝4k＋3＝＝＝－1另一种描述：设素数p>2，则－1是模p的二次剩余的充分必要条件是p≡1（mod4）。【性质4】＝（证）因x2≡a＋p（modp）x2≡a（modp）【推论】若a≡b（modp），则＝【性质5】＝（证）因＝＝＝【推论1】＝【推论2】当pa时，＝1讨论：确定a是否是模p的平方剩余就变为如何计算Legendre符号的值。上述性质可以用来计算，并由算术基本定理，设a的分解式为＝±＝，（t＝0,1）则＝（t＝0,1）故只要能计算出，，就可以计算出任意的，其中是小于p的素数。已经解决的计算：剩余的问题：，的计算。解决这些问题的基础是下面的二次互反律（Gauss定理）。【性质6】＝【例3】＝＝＝1，＝＝＝－1，故2是模17的平方剩余，但不是模19的平方剩余。【推论】p为奇素数，则＝（证）因为当p＝8k＋1时＝＝＝k(8k＋2)＝偶数当p＝8k＋3时＝＝(2k＋1)(4k＋1)＝奇数【例4】由于31≡7≡－1（mod8），59≡3（mod8），故＝1，＝－1，即2是模31的平方剩余，但不是模59的平方剩余。【性质7】（二次互反律，高斯定理）p≠q且均为奇素数，则＝另一 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示形式：＝说明1：符号和分别刻画了二次同余方程≡q（modp）和≡p（modq）是否有解，即q是否是模p的二次剩余和p是否是模q的二次剩余，其中正好是模与剩余互换了位置，而性质7恰好刻画了两者之间的关系，故称为二次互反律。说明2：由欧拉提出，高斯首先证明。已有一百五十多个不同的证明。由二次互反律引伸出来的工作，导致了代数数论的发展和类域论的形成。【推论】（i）设奇素数p、q中至少有一个模4为1，则方程≡q（modp）有解方程≡p（modq）有解（ii）若p≡q≡3（mod4），则方程≡q（modp）有解方程≡p（modq）无解（证）（i）设p≡1（mod4），即p＝4k＋1，则＝＝＝（ii）此时，p＝4s＋3，q＝4t＋3，则＝＝＝－【例5】判断3是否是模17的平方剩余。（解）＝＝＝－1所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）【例6】判断同余方程≡137（mod227）是否有解。（解）已知137与227均为奇素数，所以＝＝＝＝＝＝＝＝－1所以，方程无解。另法：＝＝＝－＝＝＝－1【例7】判断同余方程≡－1（mod365）是否有解，若有解，求解数。（解）由于365＝5·73，所以≡－1（mod365）＝＝1所以方程有解，且解数为4。【例8】判断同余方程≡2（mod3599）是否有解，若有解，求解数。（解）由于3599＝59·61，所以≡2（mod3599）因为59≡3（mod8），即＝－1，故方程≡2（mod59）无解，从而原方程无解。【例9】证明形如4k＋1的素数有无穷多。（证）反证法：不然，形如4k＋1的素数为有限个，设为，，…，，令＝＝4b＋1即a也形如4k＋1且a＞（i＝1,2,…,k）。所以a为合数，设其素因数p为奇数，则＝＝＝1所以－1为模p平方剩余。由性质3的推论，p≡1（mod4），即p也是形如4k＋1的素数。（【推论】＝）但显然p≠（i＝1,2,…,k），矛盾（否则，，且由p│a知p│1）。应用【例1】求所有奇素数p，它以3为其平方剩余。（解）即求所有奇素数p，使得＝1。易知p＞3。由二次互反律＝因为＝以及＝（排除偶数）知＝1或即p≡1（mod12）或p≡－1（mod12）故3是模p二次剩余p≡±1（mod12）【例2】设p为奇素数，d是整数。若＝－1，则p一定不能表示为的形式。（证）用反证法。设p有表达式，则由p是素数可知(x,p)＝(y,p)＝1。这是因为若(x,p)≠1，则必有但由＝－1知(d,p)＝1，所以p│y2，进而p│y。那么p2│x2，p2│y2p2│x2－dy2＝p矛盾。（即(x,p)＝(y,p)＝1成立）由(x,p)＝(y,p)＝1知，＝±1，＝±1，从而＝＝＝＝＝1与题设矛盾。【性质8】同余方程的解数是。【问题】求所有奇素数p，它以5或－2为其平方剩余。雅可比符号问题：在计算勒让德符号时，若a为奇数，但非素数，如何快速计算。目的：为了快速计算勒让德符号。雅可比符号【定义5.5.1】设m＝…是奇素数的连乘积（可以重复），对任意整数a，定义雅可比（Jacobi）符号为：J(a,m)＝＝说明：上式右端的为勒让德符号，即J(a,m)＝＝＝雅可比符号形式上是勒让德符号符号的推广。但与勒让德符号意义不同。两者的本质区别：勒让德符号可用来判断平方剩余，但雅可比符号却不能。即当k＞1时，如果J(a,m)＝－1，则方程≡a（modm）无解（因为至少存在一个，使得＝－1，即方程≡a（mod）无解，从而原方程≡a（modm）也无解），但当J(a,m)＝1时，方程≡a（modm）则不一定有解。当k＝1时，J(a,m)＝L(a,m)，即此时勒让德符号的值与雅可比符号的值相等。因此，求勒让德符号的值转化为计算雅可比符号。【例1】由定义5.5.1＝＝(－1)(－1)＝1但可以验证2是模9的平方非剩余。又如当奇素数p≡3（mod4）时，由勒让德符号的性质知，－1是模P的非平方剩余，即方程≡－1（modp）无解，从而方程≡－1（mod）也无解。即－1是模的平方非剩余。但若取m＝，则总有＝＝(－1)(－1)＝1问题：如何快速计算雅可比符号的值，以帮助加速勒让德符号的求值过程，从而加速判断平方剩余。（雅可比符号的）性质【性质1】若(a,m)＝1，则J(a,m)＝＝±1；若(a,m)＞1，则J(a,m)＝＝0。（证）因(a,m)＞1时，至少有某个，即＝0，从而＝0。【例2】a＝15，m＝39，则J(a,m)＝＝＝＝＝0＝0【性质2】＝1（证）J(1,m)＝＝＝1【性质3】＝（证）因为＝＝＝1＋＋＋…故m≡1＋（mod4），即m－1≡（mod4）≡（mod2）所以J(－1,m)＝＝＝＝【推论】＝（证）m≡1mod4m＝4k＋1＝＝＝1≡3mod4m＝4k＋3＝＝＝－1【例3】＝1，＝－1【性质4】＝（证）首先，由m＝和m＋a≡a（modm）知m＋a≡a（mod）其次，由雅可比符号和勒让德符号性质知＝＝＝【推论】若a≡b（modm），则＝（证）显然【性质5】＝（证）因＝＝··…·＝…·…＝【推论1】＝【推论2】当(m,a)＝1时，＝1【性质6】＝（证）因为＝＝＝1＋＋＋…＋∴－1≡（mod64）而对任何奇数q，都有≡1（mod8）（i＝1,2,…,k），故≡（mod8）≡（mod2）所以J(2,m)＝＝…＝＝【推论】m为奇数，则＝（证）因为当m＝8k＋1时＝＝＝k(8k＋2)＝偶数当m＝8k＋3时＝＝(2k＋1)(4k＋1)＝奇数【例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,401)(iiii)L(165,503)（解）(i)＝＝－＝－＝－＝－＝－＝－1(ii)＝＝＝＝＝－＝－＝1(iii)＝＝＝＝＝＝1(iv)＝＝＝＝＝－1【例6】同余方程≡286（mod563）是否有解。（解）563为素数，计算勒让德符号＝＝＝＝＝＝－1所以，原方程无解。【例7】判断同余方程≡88（mod105）是否有解。（解）105＝3·5·7为合数，直接计算雅可比符号＝＝＝－＝＝＝－1所以，原方程无解。（因为原方程等价于方程组，而方程组有解的充分必要条件是勒让德符号＝＝＝1。但＝＝－1，说明、、三者中至少有一个为－1，即方程组中至少有一个方程无解，从而原方程无解）。再次说明雅可比符号可以用来否定方程有解，但不能肯定方程有解。【例8】求同余方程≡38（mod385）的解数。（解）385＝7·5·11为合数，直接计算雅可比符号＝＝＝＝＝－＝1＝1并不能肯定原方程是否有解。所以，还须判断方程组中的每个方程是否有解。故再计算勒让德符号＝＝－1，因此方程≡38（mod5）无解，最终说明原方程解数为零。模p平方根目的：解同余方程≡a（modp），p为素数且pa（1）方法：逐步迭代设p－1＝s。理论基础理论基础：a是模p的平方剩余的充要条件（欧拉定理）Z＝≡1（modp）若t>1则（＝偶数）≡≡±1（modp）若≡1（modp）且t＞2，继续开方；否则，构造N，使≡1（modp）又可以继续开方。其中N为模p的平方非剩余（即）。目标：构造，使得：≡a（modp）从而得方程（1）的解：x≡±（modp）算法将偶数p－1表为p－1＝s，t≥1，s为奇数。（1）选模p的平方非剩余N，即＝－1，令b≡（modp），则有＝＝＝≡1（modp）＝＝≡－1（modp）即b是模p的次单位根，但非模p的次单位根。（2）计算：≡（modp）则y＝满足方程：≡1（modp）（因＝＝＝≡1（modp））即y＝是模p的次单位根。（3）若t＝1，则x＝＝≡（modp）满足方程≡a（modp）（此时p－1＝2s，＝＝≡a（modp）。即方程已经解出）否则，t≥2，寻找，使得y＝满足方程≡1（modp）即y＝是模p的次单位根。（a）若≡1（modp）令＝0，＝≡（modp），则即为所求。（b）若≡－1（modp）令＝1，＝＝b（modp），则即为所求。（因＝＝＝≡(－1)(－1)≡1（modp））（4）若t＝2，则x＝＝＝≡（modp）满足方程≡a（modp）（此时p－1＝s，≡≡≡a（modp））否则，t≥3，寻找，使得y＝满足方程≡1（modp）即y＝是模p的次单位根。（a）若≡1（modp）令＝0，＝≡（modp），则即为所求。（b）若≡－1（modp）令＝1，＝≡（modp），则即为所求。……依次类推（k＋1）设找到整数满足≡1（modp）即y＝是模p的次单位根：≡1（modp）（k＋2）若t＝k，则x≡≡（modp）满足方程≡a（modp）否则，t≥k＋1，寻找整数，使得y＝满足方程≡1（modp）即y＝是模p的次单位根。（a）若≡1（modp）令＝0，≡＝（modp），则即为所求。（b）若≡－1（modp）令＝1，≡＝（modp），则即为所求。最后，k＝t－1：＝≡≡…………≡≡（modp）满足方程：≡a（modp），p为素数且pa例【例1】用上述方法解同余方程≡186（mod401）（解）a＝186，p＝401。判断：p＝401为素数，且（用雅可比符号计算）＝＝1·1＝1或（用勒让德符号计算）＝＝1·(－1)·(－1)＝1故原方程有解。准备：p－1＝401－1＝400＝·25，其中t＝4，s＝25。（1）由上边计算，＝－1，即N＝3是模401的平方非剩余。令b≡≡≡268（mod401）。（2）计算≡≡≡103（mod401）≡≡≡235（mod401）（3）因为≡≡≡－1（mod401）故令＝1，≡≡103·268≡336（mod401）。（此时，，）（4）因为≡≡1（mod401）故令＝0，≡336（mod401）。（此时，）（5）因为≡235·≡－1（mod401）故令＝1，≡≡336·≡304（mod401）。（此时，）则≡≡304（mod401）满足原方程。（验证，＝92416＝186（mod401））【例2】设p是形为4k＋3的素数，若方程≡a（modp）有非零解，则其解为x≡±（modp）（解）因为p＝4k＋3，故q＝为奇数，而方程≡a（modp）有解，则a是模p的二次剩余，从而有≡1（modp）即≡1（modp）已知原方程有非零解，即（a,p）＝1，故有≡a（modp）即≡≡a（modp）∴x≡±≡±≡±（modp）【例3】设p≠q均为形如4k＋3的素数，且＝＝1，求解同余方程：≡a（modpq）（解）首先≡a（modpq）而两个方程的解分别为（modp）和（modq）利用中国剩余定理解联立方程得原方程的解为（（modp））uq±（（modq））vp（modpq）其中，≡1（modp），vp≡1（modq）【例3】解同余方程≡3（mod253）。（解）253＝11·23，11≠23，二者均为形如4k＋3的素数，且＝＝1，解方程≡3（mod11），得≡±≡±5（mod11）解方程≡3（mod23），得≡±≡±7（mod23）利用中国剩余定理解联立方程M＝11·23＝253，，＝11，计算＝1（mod11），＝21（mod23）∴≡±5·23·1±7·11·21（mod253）≡±115±99≡±16，±39，（mod253）合数的情形方程≡a（modm），（a,m）＝1（1）＝≡a（mod），（a,p）＝1，＞1（3）P为奇素数【定理5.7.1】设p是奇素数，则（3）有解＝1。且有解时，（3）的解数为2。（证）必要性≡a（mod）有解≡a（modp）有解＝1充分性：设＝1，则存在整数x≡（modp）使得≡a（modp）令f(x)＝－a，则＝2x，＝（2，p）＝1，故方程（3）的解数为2。【推论】同余方程（3）的解数为T＝1＋P＝2≡a（mod），（a,2）＝1，＞1（4）（当α＝1时，方程≡a≡1（mod2）有一个解x≡1（mod2））【定理5.7.2】设＞1，则同余方程（4）有解的必要条件是当＝2时，a≡1（mod4）；当≥3时，a≡1（mod8）。若上述条件成立，则（4）有解。且当＝2时，解数是2；当≥3时，解数是4。（证）必要性：若（4）有解，则存在整数z，使得≡a（mod）由（a,2）＝1知（z,2）＝1，记z＝1＋2t，则上式可表为a≡1＋4t(t＋1)（mod）（5）（注：＝＝1＋4t＋4）所以当＝2时，a≡1（mod4）。而当≥3时，由（5）知a≡1＋4t(t＋1)（mod＝8）又由2│t(t＋1)知，a≡1（mod8）。充分性：（i）当＝2时，a≡1（mod4），方程≡a≡1（mod）显然有两个解x≡1，3（mod）（ii）当≥3时，a≡1（mod8）。此时，若＝3，易验证方程≡a≡1（mod）（6）的解为x≡±1，±5（mod），即＝±(1＋)，＝0,±1,±2…或＝±(＋)，＝0,±1,±2…（7）其中，x3＝1,5。若＝4，方程为≡a（mod）（8）令≡a（mod）（由第三章结论，希望从方程（6）的解的值（7）中去找方程（8）的解，即确定）即＋2()＋≡a（mod）亦即＋≡a（mod）≡a－（mod）所以≡（mod2）≡（mod2）（注意≡1（mod2））或＝＋2，＝0,±1,±2…代入（7），方程（8）的解可表为（＝±(＋)，＝0,±1,±2…（7））＝±(＋)，＝＋2，＝0,±1,±2…＝±(＋＋)，＝0,±1,±2…或＝±(＋)，＝0,±1,±2…其中＝＋，且≡1（mod2）。（因为a≡≡1（mod8），故＝整数，从而为偶数）……………………依次类推，对于α≥4，设同余方程≡a（mod）（9）的解为＝±(＋)，＝0,±1,±2…（10）或≡±(＋)（mod），＝0,1且≡1（mod2）。为了从方程（9）的上述解的值（10）中找出方程≡a（mod）（11）的解，令≡a（mod）即＋2()＋≡a（mod）亦即＋≡a（mod）≡a－（mod）（12）所以≡（mod2）≡（mod2）或＝＋2，＝0,±1,±2…代入（10）式，方程（11）的解可表为（＝±(＋)，＝0,±1,±2…（10））＝±(＋)，＝＋2，＝0,±1,±2…即＝±(＋＋)，＝0,±1,±2…或＝±(＋)，＝0,±1,±2…其中＝＋，且≡1（mod2）。（因为由式（12）可知＝整数，从而为偶数）【例1】解方程≡57（mod64）。（解）64＝，即＝6。因57≡1（mod8），故方程有4个解。＝3时，解的值为x＝±(1＋)，＝0,±1,±2…（13）（解的表示：x≡1，3，5，7（mod8），或x≡±1，±5≡±7，±3（mod8）或x≡±(1＋4t)≡±(3＋4t)（mod8），t＝0,1还可表为：x≡±1，±3≡±7，±5（mod8）或x≡±(1＋2t)≡±(5＋2t)（mod8），t＝0,1此时方程为≡57≡1（mod8））（＝1）＝4时，在式（13）的所有值中找方程≡57（mod）（14）的解。为此，令≡57（mod）则＋2·1·(4)＋≡57（mod）即＋·1·≡57（mod）·1·≡57－（mod）1·≡≡1（mod2）≡≡1（mod2）或＝＋2＝1＋2，＝0,±1,±2…代入（13）式得方程（14）的解为（x＝±(1＋)，＝0,±1,±2…（13））x＝±(1＋·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（mod2）≡≡0（mod2）或＝0＋2＝2，＝0,±1,±2…故方程≡57（mod）的解为x＝±(5＋·0＋)＝±(5＋)，＝0,±1,±2…或x≡±(5＋)（mod），＝0,1或x≡±5，±21≡±5，±11（mod）（＝5）＝6时，令≡57（mod），则＋2·5·()＋≡57（mod）·5·≡57－（mod）5·≡≡1（mod2）≡≡1（mod2）或＝1＋2，＝0,±1,±2…故方程≡57（mod）的解为＝±(5＋·1＋)＝±(21＋)，＝0,±1,±2…或(21＋)（mod），＝0,1或≡±21，±53≡±11，±21（mod）（＝21）解同余方程总结方法一般方程方程f(x)≡0（modm）化为等价方程组其中＝解素数幂方程f(x)≡0（mod），p为素数deg(f)＝2，＝1，p＝2或奇素数的解法deg(f)＝2，≥2，p＝2或奇素数的解法deg(f)＞2，若已知＝1时的解，求≥2时的解问题（1）m的分解（2）deg(f)＞2，＝1时的解法习题4求满足下列方程的所有整点：（1）E：（mod7）；（2）E：（mod7）；（3）E：（mod17）；（4）E：（mod17）。利用欧拉判别条件判断：（1）－8是否是模53的二次剩余；（2）8是否是模67的二次剩余。求下列同余方程的解数：（1）≡2（mod67）；（2）≡－2（mod67）；（3）≡2（mod37）；（4）≡－2（mod37）；（5）≡1（mod221）；（6）≡－1（mod427）；计算下列勒让德符号：（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）；（9）；（10）；（11）；（12）。判断下列同余方程是否有解，若有解，请求其解数：（1）≡7（mod227）；（2）≡249（mod257）（3）≡79（mod433）；（4）≡365（mod389）（5）≡11（mod511）；（6）≡2495（mod5249）；（7）11≡－6（mod91）；（8）5≡－14（mod6193）。解下列同余方程：（1）－6≡0（mod56）；（2）＋4≡0（mod32）按要求完成下列问题：求以－3为其二次剩余的全体素数；求以±3为其二次剩余的全体素数；求以±3为其二次非剩余的全体素数；求以3为二次剩余、以－3为二次非剩余的全体素数；求以－3为二次剩余、以3为二次非剩余的全体素数；求以3为二次非剩余、以2为二次剩余的全体素数（即以3为正的最小二次非剩余的全体素数）。完成以下问题：求满足＝1的全体素数；求满足＝1的全体素数；求，，的素因数分解式；判断方程≡25（mod1013）是否有解。设素数＝4m＋1，d│m。证明：＝1。设是奇素数，pa。证明：存在整数u和v，使得≡0（mod）的充分必要条件是－a是模的二次剩余。其中＝1。设是奇素数，证明：模的所有二次剩余的乘积对模的剩余是；模的所有二次非剩余的乘积对模的剩余是；模的所有二次剩余之和对模的剩余是1（当＝3时）或0（当＞3时）；所有模的二次非剩余之和是多少？证明下列形式的素数均有无穷多个：（1）8k－1，8k＋3，8k－3；（2）3k＋1，6k＋1，12k＋1，12k＋7；（3）十进制表示末尾为9的数。设的素因数为，证明：≡1（mod12）。设是奇素数，且≡1（mod4）。证明：1,2,…,(－1)/2中模的二次剩余与非剩余的个数均为个(－1)/4；1,2,…,－1中有(－1)/4个偶数为模的二次剩余，(－1)/4个奇数为模的二次剩余；1,2,…,－1中有(－1)/4个偶数为模的二次非剩余，(－1)/4个奇数为模的二次非剩余；1,2,…,－1中全体模的二次剩余之和等于(－1)/4；1,2,…,－1中全体模的二次非剩余之和等于(－1)/4。设是奇素数。把集合分为两个非空子集和，且满足：属于同一个子集中的两个数的乘积必与中的某个数同余于模，属于不同子集的两个数的乘积必与中的某个数同余于模。证明：由中的所以模的二次剩余组成，则由其中的所以模的二次非剩余组成，且各有个数。利用雅可比符号性质计算：（1）；（2）；（3）；（4）设为奇素数，证明：方程≡－4（mod）有解的充分必要条件是≡1（mod4）。设为素数且≡3（mod4），证明2＋1是素数的充分必要条件是。设素数≥3且a。证明：＝0。设素数≥3且pa。证明：＝＝－1。设xmodm表示x遍历模数m的完全剩余系，证明：（1）若(a,m)=(b,m)＝1，则；（2）(a,m)＝1时，＝0（3）设为整系数多项式，则当＝1时，有；；设为奇素数，证明以下等式：（1）若≡1（mod4），则＝0；（2）若≡3（mod4），则；（3）若≡1（mod4），则；（4）若≡3（mod4），则。设a，b为正整数，b为奇数。证明对Jacobi符号有公式设a，b，c为正整数，b为奇数，＝1且。证明对Jacobi符号有公式证明：（1）若为奇素数，为的素因数，则。（2）不用计算，证明：，，。证明：对于任给的n＞1，存在m＞0，使同余方程的解数大于n。设，是不同的奇素数，≥1（），≥0，求同余方程的解数。设是模数的不同素因数的个数，求同余方程的解数。设，为任意整数，求同余方程的解数。其中是不同的奇素数。设正整数＞1，为任意整数，求同余方程的解数。把同余方程写为。当时，利用把同余方程化为同余方程组的方法，给出一种求的全部解的具体方法。并用以求解和的情形。其中是不同的奇素数，≥（），≥0。友情提示： 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 范本是经验性极强的领域，本范文无法思考和涵盖全面，供参考!最好找专业人士起草或审核后使用。