王进明初等数论习题详细解答2013.5第九版(可打印版).doc 33页

'王进明初等数论习题及作业解答P17习题1-11，2(2)(3),3，7，11，12为作业。1．已知两整数相除，得商12，余数26，又知被除数、除数、商及余数之和为454．求被除数.解：b=30,被除数a=12b+26=360.这题的后面部分是小学数学的典型问题之一——“和倍”问题：商为12,表明被除数减去余数后是除数的12倍，被除数减去余数后与除数相加的和是除数的（12+1）倍，即是除数的13倍.2．证明：(1)　当n∈Z且时，r只可能是0,1,8;证：把n按被9除的余数分类，即：若n=3k,k∈Z，则,r=0；若n=3k+1,k∈Z，则,r=1；若n=3k－1,k∈Z，则,r=8.(2)当n∈Z时，的值是整数。证　因为=，只需证明分子是6的倍数。=.由k!　必整除k个连续整数知：6,6|.或证：2!|,必为偶数.故只需证3|.若3|n,显然3|；若n为3k+1,k∈Z，则n－1是3的倍数，得知为3的倍数；若n为3k－1,k∈Z，则2n－1=2(3k－1)－1=6k-3,2n－1是3的倍数.综上所述，必是6的倍数,故命题得证。又证：=02+12+22+…+(n-1)2,整数的平方和必为整数。当n∈Z－时，-n∈Z+,从而同样推得为整数，故命题得证。(3)　若n为非负整数，则133|(11n+2+122n+1)． 证明：利用11n+2+122n+1=121×11n+12×144n=133×11n+12×(144n－11n)及例5的结论．(4)当m，n，l∈N+时，的值总是整数证明：=由k!必整除k个连续整数知：,n!|，从而由和的整除性即证得命题。(5)当a，b∈Z且a≠－b，n是双数时，；(6)当a，b∈Z且a≠－b，n是单数时，．解：利用例5结论：若a≠b，则．令b=－b*,即得。或解：　a=(a+b)－b，(5)　当n为双数时，由二项式展开，证得。(6)当n为单数时类似可得。3．已知a1，a2，a3，a4，a5，b∈Z,且，说明这六个数不能都是奇数．解：若这六个数都是奇数，设，则，因为，所以8|4,,　而，，，即等式左边被8除余5,　而右边被8除余1,故不可能这六个数都是奇数。4．能否在下式的各□内填入加号或减号，使下式成立；能的话给出一种填法，否则，说明理由。1□2□3□4□5□6□7□8□9=10不能，因为等式左边有单数个单数，它们的和差只能是奇数，而等式右边10为偶数。或解：无论各□内填入加号或减号，1□2□3□4□5□6□7□8□9+1+2+3+4+5+6+7+8+9总是偶数，而1+2+3+4+5+6+7+8+9=45,因此的结果1□2□3□4□5□6□7□8□9一定是奇数。5．已知：a，b，c均为奇数．证明无有理根。证：若有有理根，记为互质，代入方程有 即，这是不可能的，因为p,q互质，二者不可能同时为偶数。若p为偶数，则为偶数，但是奇数，它们的和不可能为0;若q为偶数，则为偶数，但是奇数，它们的和也不可能为0。6．在黑板上写出三个整数，然后擦去一个，换成其他两数之和加1，继续这样操作下去，最后得到三个数为35，47，83．问原来所写的三个数能否是2，4，6?解：不能．因为原来所写的三个数若是2，4，6，每次操作后剩下的三个数是两偶一奇．7．将1-—99这99个自然数依次写成一排，得一多位数A＝1234567891011…979899，求A除以2或5、4或25、8或125、3或9、11的余数分别是多少?解：由数的整除特征，2和5看末位，∴A除以2余1，A除以5余4；4和25看末两位，∴A除以4余3，A除以25余24；8和125看末三位，∴A除以8余3，且除以125余24；3和9看各位数字的和，1＋2＋3＋4＋5＋6＋7＋8＋9=45，A所有数字的和等于450,∴A除以3和9都余0，A除以11的余数利用定理1.4,计算奇数位数字之和－A的偶数位数字之和．奇数位数字之和1+3+5+7+9+(0+1+…+9)×9，偶数位数字之和2+4+6+8+(1+2+…+9)×10，两者之差为－40，原数除以11的余数就是－40除以11的余数：4.8．四位数7x2y能同时被2，3，5整除，求这样的四位数．解：同时被2，5整除，个位为0，再考虑被3整除，有4个：7020，7320，7620，7920．9．从5,6,7,8,9这五个数字中选出四个不同的数字组成一个四位数，它能同时被3,5,7整除，那么这些四位数中最大的一个是多少？被5整除，个位必为5.5+6+7+8=26,5+6+7+9=27,5+6+8+9=28,5+7+8+9=29中唯27能被3整除，故选出的四个不同的数字是5,6,7,9,但不同排序有9765,9675,7965,7695,6975,6795,从最大的开始试除，得9765=7×1395，那么要求的就是9765了。10．11．1至1001各数按以下的格式排列成表，像表中所示的那样用—个正方形框住其中的9个数，要使9个数的和等于(1)2001，(2)2529，(3)1989，能否办到?如能办到，写出框里的最小数与最大数．如办不到，说明理由．解：设框里居中心的数为x,则9个数的和等于9x.(1)9不能整除2001，∴和等于2001办不到；(2)9x=2529，x=281，是所在行第一个数，∴和等于2529办不到；(3)9x=1989，x=221，和等于1989能办到，框里的最大数为x+8=229，最小数为x－8=213．12．证明：7(或11或13)的特征是：7(或11或13)整除 解答：因为7×11×13=1001。（谐“一千零一夜”）而=7×11×13××1000．或　∴附）广西师范大学赵继源主编的《初等数论》习题1—1中的部分题目(与上面相同或相似的题目不列，以下各章节同)3．已知a，b，c中，有一个是2001，有一个是2002，有一个是2003，试判断(a—1)×(b—2)×(c—3)的奇偶性，并说明理由．6．9.是否存在自然数a和b，使a2－b2=2002成立?11．证明：当n∈Z时，6|n(n＋1)(2n＋1)．12．已知：，f(0)，f(－1)，f(1)，x均为整数．证明：解答：3．偶数．因为a，b，c中，有三个奇数，所以a－1，c－3中至少有一个是偶数．6．只需，即，先考虑有5组解9．不存在．利用a2－b2=(a－b)(a+b)，而a－b，a+b的奇偶性相同．而2002=2×1001.11．用数学归纳法或n(n+1)(2n+1)=n(n+1)(n+2)+(n－1)n(n+1)，利用整除的基本性质(13)．12．由f(0)，f(－1)，f(1)，x均为整数可得c,a+b,a－b均为整数.进而知2a，2b为整数.分类讨论(k∈Z):x=2k时，由2a，2b为整数f(x)显然为整数;x=2k+1时，f(2k+1)=4ak(k+1)+2bk+a+b+c,可知f(x)仍然为整数。习题1-21.用试除法确定下列各数中哪些是质数？哪些是合数？1987，2027，2461，17357解：,≈45.022,用质数试除到43，可知两者是质数，≈49.61,用质数顺次试除，试除时，用数的整除特征考虑：2，3，5显然不能整除它，由上节第12题结论，357－17=340，340不能被7，11，13整除，再用17，23考虑，2461÷23=107,2461是合数。用类似思路顺次试除17357，到17，得分解式17357=17×1021，17357是合数。2.当n是什么正整数时，，+8n2+4n+1,=n4－18n2+45,=n4+n2+1,的值是质数？是合数？ 解：，当n=1时，是质数；当n>1时，是合数。+=(n+1)2(n3+3n2+2n+1)。n无论是什么正整数时，n+1>1，∴总是合数。=令n2－3=1或n2－15=1知仅当n=2或n=4时，为质数，n为其它正整数时，是合数。∵　n4+n2+1=n4+2n2+1－n2=(n2+n+1)(n2－n+1)，令n2+n+1=1或n2－n+1=1知仅当n=1时，=n4+n2+1为质数，n>1时，是合数。，∴当n=2时为质数，n为其它正整数时是合数。3.试证：(1)一切大于3的质数，不是形如6n+1就是6n－1的数(n∈N)；　(2)任意多个形如6n+1的数的乘积仍是形如6n+1的数；　(3)形如6n－1的数中含有无限多个质数.证：(1)因为形如6n或6n±2或6n+3为合数；所以结论成立；　(2)先证明两个形如6n+1的数的乘积仍是形如6n+1的数：，显然，，结论成立。然后用数学归纳法可得一般性结论。(3)若形如6n－1的数中只有k个质数：p1,p2,…,pk。令N=6p1p2…pk－1，N为形如6n－1的数，由假设N必为合数，且必有一个形如6n－1的质因数p（否则就全是形如6n+1的数，由(2)中结论，乘积必为形如6n+1的数，与N的形式不符）,因此p为p1,p2,…,pk中的某一个，于是，p|1,矛盾。4.设m>1，当m|时，m必为质数.证：若m为合数，m最小的大于1的约数必为质数，设为p,p是2,3,…,m－1中一个数。显然p|(m－1)!且p|[(m－1)!+1]，于是，p|1,矛盾。5.是否有1999个连续的自然数,它们之中恰好只有一个是质数？证：显然存在1998个连续的自然数都是合数,　比如1999!+2,1999!+3,…,1999!+1999.现在设a1,a2,…，a1998是任意1998个连续的合数,若比a1小的最大的质数是p，则p,p+1,p+2,,…，p+1998就是题目所要求的1999个连续的自然数。这里的p可以如下确定：比a1小1的不是质数,就考虑比a1小2的，还不是，就考虑小3的,…，直到是质数为止，这个质数即为p。事实上，p后面的合数不少于1998个，所以可从p后面选1998个都是合数。 附）广西师范大学　赵继源主编的《初等数论》习题1—2中的部分题目(与以上相同的不列)1.判断下列各数中哪些是质数？109，20032.求证：对任意n∈Z+，必有n个连续的自然数都是合数.4.求证：当n∈Z+时，4n3+6n2+4n+1是合数.5.求a，使a，a+4，a+14都是质数.6.已知两个质数p和q满足关系式3p+5q=31.求p/(3q+1)的值.7.已知p>3，且p和2p+1都是质数，问4p+1是质数还是合数？8.由超级计算机运算得到的结果（2859433－1）是一个质数，试问：（2859433+1）是质数还是合数？请说明理由.9.已知：质数p、q使得表达式（2p+1）/q及(2q-3)/p都是自然数，求p、q的值.10.试证：形如4n-1的数中包含有无穷多个质数.（此题在王进明教材中为例題）11.（1）若n是合数，证明：2n-1也是合数；（2）有人认为下列各和数：1+2+4，1+2+4+8，1+2+4+8+16，…交替为质数与合数，你认为对吗？12.已知：质数p≥5，且是质数，证明：4p+1必是合数.习题1-2解答1.,109用质数试除到7,,2003用质数试除到43，可知两者是质数，17357=17×1021是合数.试除时，用数的整除特征考虑：2，3，5显然不能整除它，由上节第8题结论，357－17=340，340不能被7，11，13整除，再用17考虑，得分解式。2.为作一般性证明，可如下构造n个连续自然数：（n+1）！+2，（n+1）！+3，…，（n+1）！+n+1显然它们每个都是合数.4.利用4n3+6n2+4n+1=(2n+1)(2n2+2n+1),n∈Z+,n≥1,2n+1和2n2+2n+1皆为大于1的数.5.a=3.思路：分类讨论(k∈Z):∵a=3k+1时，a+14是3的倍数，a=3k+2时，a+4是3的倍数。∴必有a=3k，即a为3的倍数。而a是质数,只有a=3时，三个数全是质数。6.条件为一个不定方程,可知13得p不是3的倍数，p=3k+1，3|2p+1，所以，p=3k+2，3|4p+1.或解：4p，4p+1，4p+2是三个连续整数，必有一个被3整除，由题设，只有3|4p+1.8.合数.2859433不可能是3的倍数，连续三个自然数中必有一个是3的倍数.即（2859433+1）。另一种解法：由习题1—1第1题（2）的结论，（2+1）|（2859433+1）．9.设，h、k必为奇数,，而k不能为3,故只有k=1,这样2q－3=p,代入，同时质数p、q大于3.所以,只能有h=3,因而得q=5,p=7.10.先证：一切大于2的质数，不是形如4n+1就是形如4n－1的数；再证任意多个形如4n+1的数仍是形如4n+1的数；最后用数学归纳法验证.若形如4n－1的质数只有有限个：p1,p2,…,pk。令N=4p1p2…pk－1，N为形如4n－1的数，由假设N必为合数，且必有一个形如4n－1的质因数p（否则就全是形如4n+1的数，乘积必为形如4n+1的数）,因此p为p1,p2,…,pk中在某一个，于是，p|1,矛盾。11.（1）n是合数,设n=st,2n-1=2st-1=（2s-1）［（2s）t-1+（2s）t-2+…+2s+1］.（2）1+2+22+…+2n-1=2n-1.当n=14，15时，214-1，215-1均为合数，∴不对.12.　取模为6分类讨论p，即设p=6q+r（r=0，1，2，3，4，5）.由质数p≥5，若p=6q,6q+2,6q+3或6q+4,p皆为合数,不可能.若p=6q+1, 则2p+1=12q+3也是合数,故在题设条件下,只有p=6q+5,此时4p+1=24q+21,是合数.实际上，这题与第7题完全相同。质数p>3ó质数p≥5，可用前面的方法简单求解。习题1-31.求：（1）（30，45，84），［30，45，84］；（2）（21n+4，14n+3）（其中n∈N）；解：（1）(30，45，84)=(30，15，24)=(0，15，9)=3,［30，45，84］=［90，84］=6［15，14］=6×15×14=1260.（2）-2（21n+4）+(14n+3）=1,故（21n+4，14n+3）=12.当n∈N时，求证：证：n=2k时，k∈Z,(n-1,n+1）=(2k-1,2k+1)=(-2,2k+1)=1;即2|n时,(n-1,n+1)=1；n=2k+1时，k∈Z,(n-1,n+1）=(n-1,2）=(2k,2)=2.3.用辗转相除法求（4453,5767）,并写出相应的裴蜀等式。解：竖式：01234q1322P114922Q0137174453×22+5767×(－17)=－73，∴　5767×17－4453×22=73或由推得4．已知24|,　求a,b.解：6274200=261425×24,　故只需24|，即=0,24,36,48,72,96.又解：24=3×8，3,8互质，故只需3|,8|，即3|（a+b）；又8|，8|200,故只需8|，从而必为8的倍数，3,8同时考虑，故答案是00，24，48，72,96.5．求证：lg2，是无理数．证∵　0=lg1t，证明：整数集合{x|x=u+ms－tv，0≤u≤ms－t－1,0≤v≤mt－1}为模ms的一个完全剩余系。证：首先确定集合元素的u有ms－t种取法，而u每次取定之后要加不同的ms－tv，v有mt种取法，因此元素总数为ms－t×mt=ms。然后可以验证题设的集合元素就是0到ms－1的ms个数，它们构成ms的非负最小完全剩余系。证毕。8.计算欧拉函数值：；　；　；　解：ϕ(1236)=ϕ(12×103),103是质数，因此ϕ(1236)=(22-2)(3－1)(103－1)=408.ϕ(1218)=ϕ(6×203)=ϕ(2×3×7×29)=2×6×28=336=(3－1)(23－1)(29-1)=1122ϕ(4200)=ϕ(23×3×52×7)=(23-22)(3－1)(52－5)(7－1)=9609.设为大于2的整数，证明为偶数。证：若m的质因数至少有一奇数，由公式，可知=为偶数。若m的质因数一个奇数也没有，而m大于2，必有m=，此时=,也是偶数。 或证：设m=p1α1p2α2…pkαk，∵m>2，∴至少存在i，αi>1或存在j，pj是奇数，∴p1α1-p1α1-1，…，pkαk-pkαk-1中至少有一个为偶数，知φ（m）必为偶数中又证：则必有一个pi为奇数，因为如果m是质数，大于2的质数是奇数，是偶数；如果m是合数，pi中最多只有一个是2,那么至少有一个为奇数，10.　11(略)附）广西师范大学赵继源主编的《初等数论》将完全剩余系与简化剩余系分开在2-2,2-3两节,下面是广西师范大学赵继源主编的《初等数论》习题2-3中的部分题目1.乘幂20，21，22，…，29能否构成模11的一个简化剩余系？解：i>j时，2i－2j=2j(2i－j－1),112j,通过验证可知，对任何i，j，也有11(2i－j－1)，φ(11)=10，而20，21，22，…，29为10个不同的整数，所以它们构成模11的一个简化剩余系2.列表求出模m为10，11，12，…，18等值时的最小简化剩余系及相应的φ(m).m最小简化剩余系φ(m)10137941112345678910101215711413123456789101112121413591113615124781113148161357911131581712345678910111213141516161815711131763.证明定理2.7：简化剩余系的充分必要条件。证明:（必要性）∵x1，x2，…，xk是模m的简化剩余系，∴k=φ(m)，且当i≠j时，xixj（modm），（xi，m）=1，i=1，2，…，φ(m).（充分性）k=φ（m），∴x1，x2，…，xk共有φ（m）个.又xixj（modm），（i≠j，1≤i，j≤k），（xi，m）=1（i=1，2，…，k），∴x1，x2，…，xk各属于φ(m)个不同的且与m互质的剩余类，∴x1，x2，…，xk是模m的简化剩余系.4.验证：（1）8，16，24，32，40，48是模7的简化剩余系；（2）11，13，77，99是模10的简化剩余系.解：（1）∵（4，7）=1，可化为2，4，6，8，5，12，又5≡12（mod7），∴8，16，24，32，40，48不是模7的简化剩余系。（2）10的最小简化剩余系是1,3,7,9。11，13，77，99分别与1,3,7,9关于模10同余。∴11，13，77，99是模10的简化剩余系.5.当m取下列各值时，计算φ（m）的值. 25，32，40，48，60，120，100，200，4200，9450.答案：φ（25）=20，φ（32）=16，φ（40）=16，φ（48）=16，φ（60）=16，φ（120）=32，φ（100）=40，φ（200）=80，φ（4200）=960，φ（9450）=2160.6.若φ（m）是奇数，试求m的值.　解：(参看下一题)m=1或m=2.7.当m>2时，证明φ（m）是偶数.8.试证：使φ(m)=14的数m不存在.证：φ(m)=14=2×7=p1α1-1…pkαk-1(p1－1)…(pk－1)，2,7是质数，所以必有p1=2，p1=7，这是不可能的。9.已知φ(m)=4，求m.解：设m=p1α1p2α2…pkαk，由φ(m)=(p1α1-p1α1-1)…(pkαk-pkαk-1)，φ(m)=4=4×1=22，得m=5，φ(m)=5－1=4，或m=8=23，φ(m)=22或m=10=5×2，φ(m)=4×1，或m=12.10.如果n=2m，（2，m）=1，那么φ（n）=φ（m）.解　∵（2，m）=1，∴φ（n）=φ（2m）=φ（2）φ（m）=φ（m）.11.若m是奇数，则φ（4m）=2φ（m）.证：∵m是奇数，∴（4，m）=1，则φ（4m）=φ（4）φ（m）.∵φ（4）=2，∴φ（4m）=2φ（m）.12.（1）分母是正整数n的既约真分数的个数是多少？为什么？（2）分母不大于n的既约真分数的个数是多少？为什么？解：（1）φ（n）.（2）φ（2）+φ（3）+…+φ（n）.习题2-31.举例说明欧拉定理中（a，m）=1是不可缺少的条件.解：当a=2，m=4时，(4)=2，此时22≡0（mod4），可见（a，m）=1是欧拉定理的不可缺少的条件.2.设p，q是两个大于3的质数，求证：p2≡q2（mod24）.证：24=3×8，（3，8）=1.由条件，(p，3)=(q，3)=1，由费尔马小定理有p2≡1（mod3），q2≡1（mod3）.∴p2≡q2（mod3）.又∵p，q必为奇数，设p=2k+1，p2=4k(k+1)+1,有p2≡1（mod8），类似可得q2≡1（mod8）.∴p2≡q2（mod8）.∴p2≡q2（mod24）.3.设p是大于5的质数，求证：p4≡1（mod240）.证：240=3×5×16，由条件，(p，3)=(p，5)=1，∴p4≡1（mod5），p4≡（p2）2≡1（mod3）.又p为奇质数，从而2|（p2+1），8|（p2-1），∴16|（p4-1），即p4≡1（mod16）.而（3，5）=（3，16）=（5，16）=1.∴p4≡1（mod240）.4.如果今天是星期一，从今天起再过天是星期几？解：由欧拉定理，106≡1(mod7)，由普通除法知1010被6除余4,即1010=6k+4,k∈Z,故=,而62≡1(mod7),∴64≡1（mod7）再过天是星期二.5.求下列各题的非负最小余数：（1）84965除以13；（2）541347除以17；（3）477385除以19；（4）7891432除以18；（5）(127156+34)28除以111.答案：（1）8.（2）10.（3）16.（4）1.（5）70.解：（1）84965除以13；（13，8）=1,∴812≡1（mod13），84965=(812)413×89≡1×(-1)4×8（mod 13）或解：82≡－1（mod13），84965=(82)2482×8≡(-1)2482×8≡8（mod13）。6.已知a=18，m=77，求使ax≡1（modm）成立的最小自然数x.答案：x=30.,由定理知，1860≡1(mod77),且满足要求的最小自然数x必为60 的正约数：1,2,3,4,5,6,10,12,15,20,30,　由验算可知x=30.　事实上,由欧拉定理知，186≡1（mod7），1810≡1（mod11）,6与10的最小公倍数是30,故有1860≡1(mod77),而182≡16(mod77),183≡57(mod77),182≡162≡25(mod77),185≡57×16≡65(mod77),186≡(183)2≡572(mod77),1810≡185×182≡65×16≡1040≡39(mod77),(略)7.设（m，n）=1，证明：m+n≡1(modmn).证：∵(m,n)=1，∴n≡1（modm），而m≡0（modm），∴m+n≡1（modm）.对称可得m+n≡1(modn).　由同余性质可得m+n≡1（modmn）.广西师大本其他题目：5.已知p是质数，（a，p）=1，求证：（1）当a是奇数时，ap-1+(p－1)a≡0（modp）；（2）当a是偶数时，ap-1－(p－1)a≡0（modp）.证：（1）由p是质数，（a，p）=1，a为奇数，有ap-1≡1（modp）.(p－1)a≡－1（modp），∴ap-1+(p－1)a≡1－1≡0（modp）.（2）由条件，ap-1≡1（modp）,(p－1)a≡1（modp），∴ap-1－(p－1)≡1－1≡0（modp）.6.已知p，q是两相异的质数，且ap-1≡1（modq），aq-1≡1（modp），求证：apq≡a（modpq）.证：∵ap≡a（modp），∴apq≡(ap)q≡aq≡a（modp）；同理，apq≡(aq)p≡ap≡a（modq），而（p，q）=1，故apq≡a（modpq）.7.如果（a，m）=1，x≡ba（modm），那么ax≡b（modm）.8.设A是十进制数44444444的各位数字之和，B又是A的各位数字之和，求B的各位数字之和.9.当x∈Z时，求证：（1）2730|x13-x；（2）24|x（x+2）（25x2-1）.解答：7.∵x≡ba(modm)，∴ax≡aba≡ab(modm).∵(a，m)=1，a=1(modm)，∴ax≡b（modm）.8.设B的各位数字之和为C，∵lg44444444=4444lg4444<4444×4=17776，即44444444的位数小于17776，∴A≤9×17776=159984，B<1+9×5=46，C≤4+6=10.又∵（7，9）=1，(9)=6，4444=6×740+4，44444444≡74444≡74≡(－2)4≡7（mod9），∴B的各位数字之和为7.9.（1）∵2730=2×3×5×7×13，2，3，5，7，13两两互质，x13-x=x（x12-1），∴当2|x或2|x时都有x（x12-1）≡0（mod2），x（x12-1）≡0（mod13）.又∵x13-x=x（x6-1）（x6+1），∴当7|x或7|x时都有x（x6-1）（x6+1）≡0（mod7）.而x13-x=x（x4-1）（x8+x4+1），∴当5|x或5|x时，都有x（x4-1）（x8+x4+1）≡0（mod5）.又x13-x=x（x2-1）（x2+1）（x8+x4+1），∴当3|x或3|x时，都有x（x2 -1）（x2+1）（x8+x4+1）≡0（mod3）.∴2730|x13-x.（2）解法一，同上。解法二：x（x+2）（25x2-1）=24x3（x+2）+x（x+2）（x2-1）,x（x+2）（x2-1）=x（x-1）（x+1）（x+2），四个连续自然数的乘积必能被4!=24整除，证得。10.设质数p>3，x∈Z，试证：6p|xp-x.11.p是不等于2和5的质数，k是自然数，证明：.解答：10.∵质数p>3，∴（6，p）=1，xp-x=x（xp-1-1）≡0（modp）.又p-1是偶数，∴x（xp-1-1）≡x（x2-1）…（modp）.于是，当2|x或2|x时，x（x2-1）≡0（mod2）；当3|x或3|x时，x（x2-1）≡0（mod3）.故x（xp-1-1）≡0（mod6）.从而6|p（xp-x）.11..由条件，（10，p）=1，∴10p-1≡1（modp）.∴（10p-1）k≡1（modp）.∴.(王进明与赵继源本三、四章编排顺序相反)习题3-1(P157)1．试写出三个模数是20的一次同余方程，分别使它有唯一解，无解，有四个解。解：7x≡50（mod20）有唯一解，8x+5≡0（mod20）无解，4x≡0（mod20）有四个解。2.下列同余方程是否有解？为什么？如果有解，不出其所有解。（1）7x+4≡0（mod25）；（2）12x+1≡0（mod9）；（3）34x≡1（mod51）；（4）42x≡8（mod138）；（5）174x≡65（mod1309）.解：（1）（7,25）=1,有唯一解。7x≡-4（mod25）由欧拉定理，ϕ(25)=20,故x≡719×(-4)≡3（mod25）,化简过程：72≡-1（mod25）故719×(-4)≡718×7(-4)≡(-1)×7(-4)≡28≡3（mod25）.用同余变形法解：.（2）（12,9）=31,同余方程无解；（3）（34，51）=171,同余方程无解；（4）138=2×3×23,（42,138）=6不能整除8,同余方程无解；（5）174=2×3×29,1309=7×11×17,(174,1309)=1.此题数字大，应该用大衍求一术。n1234567q07111021P17815158331489x≡489×65=31785≡369（mod1309）3.求下列一次同余方程的所有解：（1）3x≡1（mod17）；（2）1215x≡560（mod2755）； （3）47x≡89（mod111）；（4）38x≡6（mod106）；（5）11x≡6（mod13）.（6）3x≡5（mod29）；（7）5x≡6（mod24）（8）66x≡14（mod74）；解：（1）（3,17）=1,有唯一解。由3x≡1+17（mod17）得，x≡6（mod17）；（2）（1215，2755）=5(243,551)=5(35,19×29),方程恰有5解，先解243x≡112（mod551）:这个系数相当大，故应该用大衍求一术。辗转相除过程的竖式略，由如下表格n123456789q023121411P12792534161195356知x≡112×356≡200（mod551）,故原方程有解x≡200751,1302,1853和2404（mod2755）.（3）(47，111)=1,方程恰有一解x≡89（mod111）；由欧拉定理，ϕ(111)=72,故x≡4771×(89)≡94（mod111）,用同余变形法解：（mod111）（4）38x≡6（mod106）；先解19x≡3（mod53）.用同余变形法解有（mod53）原同余方程的解有两个：x≡42（mod106），x≡95（mod106）（5）11x≡6（mod13）.（mod13）（6）3x≡5－29=－24（mod29）,∴　x≡－8=21（mod29）；（7）5x≡6+24=30（mod24）,∴　x≡6（mod24）（8）66x≡14（mod74）；先解33x≡7（mod37）；≡26（mod37）原同余方程的解有两个：x≡26（mod74）,x≡63（mod74）。下面是广西师大本中要求按指定方法求解的题目，可自行练习：4.化为不定方程解下列同余方程（王进明本第四章讲不定方程，此题建议用同余变形法）：（1）20x≡4（mod30）；（2）57x≡87（mod105）；（3）4x≡11（mod15）；5.利用欧拉定理解下列同余方程：（1）6x≡22（mod36）；（2）3x≡10（mod29）；（3）258x≡131（mod348）；（4）11x≡7（mod13）；（5）3x≡2（mod17）；（6）243x≡102（mod551）.6.用求组合数的方法解下列同余方程：（1）5x≡13（mod43）；（2）9x≡4（mod2401）；王进明本习题３.２(P169)　赵继源本习题4-3(P154) 　解略2.　a取什么值时，下面的同余方程组有解？解：因为(18,21)=3,3|8－5，所以有解；(18,35)=1,所以总是有解。因此，要使题设的同余方程组有解，只需有解。而这里，(21,35)=7，由定理可知，只需a≡8≡1(mod7).即x=1+7t(t为整数)，题设的同余方程组总有解。3.解下列同余方程组：(1),(2)(4)(5)解：(1)方法一：设x=5+11y,代入第一个同余方程，得11y≡3－5(mod7)，得y≡3(mod7)所以同余方程组的解是x≡38(mod77)。方法二：用孙子定理解，M=77，M1=11，M2=7，令11M1′≡1(mod7)，得M1′≡2(mod7)，7M2′≡1(mod11)，得M2′≡－3(mod11)，所以同余方程组的解是x≡11×2×3+7×(－3)×5≡－39≡38(mod77).(2)方法一：设x=7+24y,代入第一个同余方程，得24y≡6－7(mod13)，得y≡7(mod13)所以同余方程组的解是x≡7+24×7≡175(mod312)。方法二：用孙子定理解，M=312，M1=24，M2=13，令24M1′≡1(mod13)，得M1′≡6≡－7(mod13)，13M2′≡1(mod24)，得M2′≡13(mod24)，所以同余方程组的解是x≡24×(－7)×6+13×13×7≡－1008+1183≡175(mod312).４.求解下列各题（我国古代数学家杨辉1275年所写《续古摘奇算法》中的三个例题）：（1）七数剩一，八数剩一，九数剩三，问本数；（2）十一数余三，十二数余二，十三数余一，问本数；　　　（王进明攺了几个数）（3）二数余一，五数余二，七数余三，九数余四，问本数. 解：（1）方法一：设x=1+56y,代入第二个同余方程，得56y≡3－1(mod13)，（56－54）y≡2(mod13)得y≡1(mod13)y，所以，同余方程组的解是x≡57(mod504)。方法二：用孙子定理解。（2）　用孙子定理解，M=1716，M1=156，M2=143，M3=132，令156M1′≡1(mod11)，得2M1′≡12(mod11)，M1′≡6(mod11)；143M2′≡1(mod12)，得－M2′≡1(mod12)，M2′≡－1(mod12)；132M3′≡1(mod13)，得2M2′≡－12(mod13)，M2′≡－6(mod13)所以同余方程组的解是x≡156×6×3+143×(－1)×2+132×(－6)×1≡14(mod17).法二：观察法。或累加试除法。5.　求相邻的四个整数，它们依次可被整除。解：由题意得即即用孙子定理解，M=11025，M1=1225，M2=9，令1225M1′≡1(mod9)，得M1′＝1；9M2′≡1(mod1225)，1225＝9×136+1，∴9×(－136)+1225＝1，即M2′＝－136所以x≡1225×1×2+9×(－136)×(－13)＝18362≡7337　(mod11025).所求的四个连续整数为29348，29349，29350，29351.6.　求模11的一个完全剩余系，使其中每个数被2，3，5，7除后的余数分别为1，－1，1，－1。解：先求x,满足:等价于可解得再依次解　　……（略）以下为赵本的第4题： 5．.解下列同余方程组：（1）x≡8（mod15），（2）x≡6（mod11），x≡3（mod10），x≡3（mod8），x≡1（mod8）；x≡11（mod20）；（3）x≡2（mod35），（4）4x≡90（mod105），x≡9（mod14），5x≡18（mod63），x≡7（mod20）；7x≡10（mod50），3x≡12（mod22）解：（1）化为用孙子定理解，M=120，M1=40，M2=24，M3=15，令40M1′≡1(mod3)，得M1′≡1(mod3)；24M2′≡1(mod5)，得－M2′≡1(mod5)，M2′≡－1(mod5)；15M3′≡1(mod8)，得－M2′≡1(mod8)，M2′≡－1(mod8)所以同余方程组的解是x≡40×2+24×(－1)×3+15×(－1)×1≡－7(mod120).（3）化为用孙子定理解，M=140，M1=4，M2=35，令4M1′≡1(mod35)，得M1′≡9(mod35)；35M2′≡1(mod4)，得－M2′≡1(mod4)，M2′≡－1(mod4)；所以同余方程组的解是x≡4×9×2+35×(－1)×3≡－33≡107(mod140).7.设韩信所辖某部士兵共26641人，在一次战斗中损失近百人.休整时清查：1～3报数余1，1～5报数余3，1～7报数余4.问损失了多少人？解：设还有士兵x人，由题设，得同余方程组由口诀，x≡70+21×3+15×4≡193+105×251≡26548(mod105)26641－26548=93人。损失了93人。 设损失了x人，得同余方程组化为由口诀，x=21×3+15×2=93。损失了93人。8.求7的倍数，使它分别被2，3，4，5，6除时，余数都是1.解：设所求为7x,[2，3，4，5，6]=60，由题设，得,用大衍求一术得x≡43(mod60),7x=7×43=301，故，所求为301+420t,t为整数。9.求三个连续的自然数，使它们从小到大依次被15，17，19整除（写出其中最小的一组）.解：由题设，得同余方程组化为标准形式为用孙子定理解，M=321，M1=19，M2=17，令19M1′≡1(mod17)，得M1′≡9(mod17)，17M2′≡1(mod19)，得M2′≡9(mod19)，所以同余方程组的解是x≡19×(－8)×9+17×9×10≡162(mod321).本题所求的三个连续的自然数是162×15，162×15+1，162×15+2，即2430，2431，2432。下面是不定方程内容（王进明本为第四章，习题这里没做）（赵继源本）习题3-11．解下列不定方程：（1）7x－15y=31；（2）11x+15y=7；（3）17x+40y=280；（4）525x+231y=42；（5）764x+631y=527；（6）133x－105y=217.解：（1）辗转相除得15=7×2＋1,∴1=15－7×2=7×(－2)－15×(－1)，∴因此原方程的一个解是x0＝－2×31＝－62，y0＝－1×31＝－31;原方程的通解为（2）辗转相除得15=11×1＋4,11=4×2＋3,4=3+1∴1=4－3=4－(11－4×2)=4×3－11=(15－11×1)×3－11=15×3+11×(－4)，∴因此原方程的一个解是x0＝－4×7＝－28，y0＝3×7＝21;原方程的通解为（3）用分离整数法：观察可知y=－10时，x=36+4=40.∴原方程的通解为2.解下列不定方程：（1）8x-18y+10z=16；（2）4x-9y+5z=8；（3）39x-24y+9z=78； （4）4x+10y+14z+6t=20；（5）7x-5y+4z-3t=51.3.解下列不定方程组：（1）x+2y+3z=10，（2）5x+7y+3z=25，x-2y+5z=4；3x-y-6z=2；（3）4x-10y+z=6，（4）10x+7y+z=84，x-4y-z=5；x-14y+z=-60；4.求下列不定方程的正整数解：（1）5x－14y=11；（2）4x+7y=41；（3）3x+2y+8z=21.5.21世纪有这样的年份，这个年份减去22等于它各个数字和的495倍，求这年份.6.设大物三值七，中物三值五，小物三值二，共物一百三十八，共值一百三十八，问物大中小各几何？7.买2元6角钱的东西，要用1元、5角、2角、1角的四种钱币去付，若每种钱币都得用，则共有多少种付法？8.把239分成两个正整数之和，一个数必是17的倍数，另一个数必是24的倍数，求这两位数.9.一个两位数，各位数字和的5倍比原来大10，求这个两位数.10.某人1981年时的年龄恰好等于他出生那一年的年号的各位数字之和，这个人是在哪一年出生的？11.一个四位数，它的个位数上数比十位数字多2，且此数与将其数字首尾颠倒过来所得的四位数之和为11770，求此四位数.习题3-21．求x2+y2=z2中0y>z>0），使x-y，y-z，x-z都是平方数.1．b11122234a24635745x315355214579y48121220282440z5173713295325412.设x-y=a2，y-z=b2，x-z=c2，则a2+b2=c2，因此给出a，b的值即可求得x，y，z.3.已知直角三角形斜边与一直角边的差为9，三边的长互质且和小于88，求此直角三角形的三边的长.4.试证：不定方程x4-4y4=z2没有正整数解.3.设直角三角形的三边的长为x,y,z.则由定理，x=a2－b2,y=2ab,z=a2+b2,由题目得a2+b2－(a2－b2)=9或a2+b2－2ab=9,前者无整数解，后者(a－b)2=9,a－b=3.a=4,b=1,则x=15，y=8，z=17或a=5,b=2,则x=21，y=20，z=29.a=7,b=4,则三边的长的和大于88。4.因为z4=(x4-4y4)2=x8－8x4y4+16y8=(x4+4y4)2－(2xy)4，即(2xy)4+z4=(x4+4y4)2，就是说，如果x4-4y4=z2有正整数解，则u4+v4=w2有正整数解，与已证定理矛盾，故无正整数解.5.试证：每个正整数n都可以写为n=x2+y2-z2，这里x，y，z都是整数.6.求方程x2－dy2=1，当d=0、d=－1、d<－1时的非负整数解.7.试证：2x2+y2+3z2=10t2无正整数解.5.适当取正整数x，使n-x2=m为一正奇数，设y=m+12，因为y2-m=m-1()22=z2， 得n-x2=y2－z2.6.当d=0时，x=1，y为任意非负整数；当d=-1时，x=1，y=0和x=0，y=1；当d<-1时，x=1，y=0.7.∵y2+3z2是偶数，∴y与z必同奇同偶.若y与z同为奇数，则2x2+y2+3z2被8除和10t2被8除的余数不相等，故y与z一定同为偶数.令y=2y1，z=2z1，代入原式得，x2+2y21+6z21=5t，同样，x和t同奇同偶，也同样排除x和t同奇，令x=2x1，t=2t1，代入得，2x21+y21+3z21=10t21，由于0