专题3.3 选择合适的模+黄海良.docx

《专题3.3 选择合适的模+黄海良.docx》由会员分享，可在线阅读，更多相关《专题3.3 选择合适的模+黄海良.docx（3页珍藏版）》请在第一文库网上搜索。

1、3.3选择合适的模如果两个整数a、b被正整数m除，有相同的余数，那么称a与b对模m同余，记为:a=b(modm).选择合适的模，是利用同余理论处理问题的关键，可以帮助解决一类指数形式的数的问题，也可较快判断含有字母的式子是否为素数，用来判断末尾或末几位的数字，还可被用来构造抽屉解决一些组合问题.例1试问:220+1与2刈+1是否都为素数？【分析】希望找到正整数m,使得220+1三0(modm),即220”三1(modm).注意到2011为奇数，从而上式成立的一个充分条件是2三-1(modm),取m=3即可.另外，因为2010为偶数，要找到正整数m,使得2刈三1(modm),只要将底数扩大，使指

2、数变成奇数，即可类似处理：220K)三1(modm)4,5-1(modm),取m=5即可.【解】因为2-1(mod3),所以220+1三(-D20+1三1+1三0(mod3).从而Z?。+1为合数.因为4三-1(mod5),所以2刈+1=41005+1三(-1)1005+1三-1+1三0(mod5),从而223+1为合数.【注】对于指数形式的数，或者用含有字母的式子表示的数，判断其是否为素数，可选择适当的模，考察其余数的规律.例2设P是素数，q=4+1也是素数，试求p+q的值.【分析】用最小的素因数2、3等来试验，夕=4+/+1也是素数的必要条件是不含素因数2、3.由于模2并不能得到好的结果，

3、所以考虑模3.【解】S=4p+p411p+p4+12+p4(mod3),且广三0,1(mod3),则p4=0,1(mod3).若p三1(mod3),则qp4+2+20(mod3),又由于4=4+p4+43,与q为素数矛盾；若小三0(mod3),则p=3.此时夕=4+/+4=149为素数，因此p+q=152.例3求证:对任意非负整数n,数3+2x不是一个完全平方数.【证明】当n为偶数时，不妨设n=2m,其中m为非负整数，则3”=9”三1(mod8)；当n为奇数时，设n=2m+1,则3m=39,h3(mod8),故对任意正整数n,都有3+2x17”三3或5(mod8),但完全平方数三0,1或4(m

4、od8),所以数3”+2x17不是一个完全平方数.【注】判断一个数是不是完全平方数，我们也可以用“模”的方法，例如，我们有经验:偶数的平方是4的倍数，奇数的平方除以4余1,所以若一个整数模4同余2或3,则它一定不是完全平方数.类似的还有很多，需要不断积累总结.本题较容易选择模4,也能够直接对n为偶数进行排除，对n为奇数是无法直接得到，需再选择其他数作模,此时会选择模8,发现这样才能完成证明，当然，直接选择模8将一步到位，无需分类讨论，更为简洁，这也体现了“选择合适的模”的重要性！例4设P为大于3的素数，且对某个正整数n,数p”是一个20位数.证明:数p的20个数码中，至少有3个数码相同.【分析

5、】我们知道一个正整数与它的各位数码和模9同余，因此研究数码时常用到模9.【证明】若Pn的20个数码中没有3个数码相同，则0,1,2,，9中每一个数码恰好各出现2次.于是p三2x(0+1+9)=900(mod9),所以P是3的倍数，这与P是大于3的素数矛盾，得证.例5已知正整数p、q都是素数，且7p+q,pq+11也都是素数.求p+q.【分析】由于p、q、7p+q、pq+11都是素数，且7p+q7,pq+1111,所以，可用最小的素因数2、3来尝试.先考虑模2,rpq(mod2),贝j7p+夕7+1三0(mod2),矛盾.于是p、q中至少有一个为偶数.进而类似分析，发现p、q中至少有一个为3.【

6、解】当P三4三1(mod2)时，1p+q1+i0(mod2).但7p+q272,与7p+q是素数矛盾，所以，p、q中至少有一个为偶数.又p、q都为素数，则p=2或q=2.(1)当p=2时,14+q和2q+11都是素数.若q(mod3),M14+14+10(mod3),矛盾；若q-(mod3),则2q+11三一2+1m0(mod3),矛盾.所以，2p+11都是素数.若Pm1(mod3),贝j7p+2m7+2m0(mod3),矛盾；若P三T(mod3),贝U2p+11-2+110(mod3),矛盾.所以，p0(mod3).但P是素数，故q=3.经检验，p=2,q=3或p=3,q=2符合条件.所以p

7、+q=5.例6称具有+16仍2形式的数为“好数”，其中a,b都是整数.(1)证明：100,2010都是“好数”(2)证明:存在正整数X,y,使得X+y是“好数”，而：x+y不是“好数”【解】(1)由+16仍2形式的数为“好数”,将100与2010表示成“好数”的形式即可证明结论的正确性,注意IOO=Io2+Six。?,2010=432+16112；(2)由于指数161太大，考虑用同余来解决问题；由161=7X23,所以可以考虑模7,而/+161除以7的余数可以是0,1,2,3,可知构造:x、y时，最好让x+y对模7余3即可.又由于p(p+1)M+(P+1)=(P+1)(P+1)=(P+1尸2是

8、完全平方数，所以可以令X=Sts6+1),y=3,61+b则X+,=(3+1严=(3+1)力2+61()2是好数，结合3三5(mod7)(这可由3三一1(mod7),知3三(T)三-2(mod7)得至J),JW33,6,+3,6,+13(51)+63(mod7),所以x+y不是好数.【注】选择适当的模对于问题处理的难易影响很大.练习3.31、试求:最小的素数，使得对于某个整数n,这个素数能整除+5n+23.2、设a1,n1,定义优为一个完全方鼎.证明：当P是一个素数时，22+3不是完全方幕.3、已知a、b是两个整数,证明a与b同奇偶,当且仅当存在整数c,d使得a2+b2+c2+=d2.4、证明

9、:对于任意正整数n22,都存在一个正整数m,使得m可以被同时表示成2个，3个，n个正整数的平方和.5、是否存在一个2的鼎，其每位上的数字均非零，且可以按不同的次序重新排列各位数字得到另一个数也是2的鼎？证明你的结论.练习3.3答案1设/GD=?+5+23,因为/()三1(mod2),/()1(mod3),/()-1,2(mod5),f(ri)1,3,i2(mod7),/(n)1,3,4,6(mod11),f(n)-2,3,4,-5,t6(mod13),且/(-2)=17,所以满足条件的最小的素数为17.2 .当p=2时，232=13不是一个完全方累，当p=5时，25+3=275也不是完全方幕.

10、现设p=2女+105,则有2+3。=2a+,+32i+,=(2+3)(22a-22*,3+22a232-+32a),由于2+3”有因数5,故若+3。是完全方暴，则必须至少还有一个因数5,但由于3三-2(mod5),且22a-22-,3+22a-232-.+32*22a-22-,(-2)+22a-2(-2)2-.+(-2)2i=22i+22i+.+22a=(2A+1)22A=p2X(mod5),因pw5,P又为素数，故没有因子5,从而51(22*-22*-,3+22*-232-+32),由此知2+3不是完全方嘉.3 .显然a与b不同奇偶等价于a?+b21(mod4).如果/+c2+j=J2,且a

11、与b不同奇偶，则(d-c)(d+c)=d?-/三2(mod4),而d-c,d+c同奇偶，所以不可能有d2-C22(mod4),矛盾，从而a与b同奇偶，反之如果a与b同奇偶，则/+/+1三1,3(mod4).若/+从+=42+1,则取c=2%,d=2A+1(k为整数，后同)即可满足a?+从+1=d若+/+1=4Z+3,则取c=24+1,d=2k+2,即可满足a2+b2+=d2.4 .引理任意m210都可以表示成为/+从/的形式，其中a、bC都是正整数.引理的证明(1)如果m为偶数，则m=2g=(3g)2+(41)2-(5q-1)2;(2)如果m为奇数，则m=2q+1=(3q-I)2+(4q-4)

12、2-(5q-I)2.回到原问题当n=2时，取IO=F+3?即可；假设=A2时，存在一个正整数m1()可以被同时表示成为2个，3个，k个正整数的平方和，那么由引理，我们有a2+b2-c2=m=2+22=b22+2=-=2+22+.+2,令/%=m+/210,则有z=2+b2=aI2+22+c2=bI2+b22+2+c2=2+22+.+i2+c2,从而命题成立.5 .不存在.若存在，设n位数满足要求M=23由于M中无数字0,故任意重新排列M的各位数字所得的新数仍是n位数.设其中一种排列M=2,不妨设M,则,又M与M，都为n位数，则有f4+3.考虑模9,有“三”(mod9),即2J2(mod9).因为(2%)=1,所以2Ym1(mod9),由i=1,2或3,故2“羊1(mod9)=2,矛盾.