基础数论讲义(第一层次)

1数论2一、整数问题例题1已知正整数,kn，且1,41knknkn。证明：21,211nk讲解：用反证法，若不然，设21,211nk，则21,2221,2221,21,1nknknknnkknk2241441,41,,211,21knnnknnknnknnkn21nkn，又1,21knnkn，矛盾，得证。注意问题：例题2已知三个正整数,,,2xyzxyz，若1,1,1xyzyzxzxy，试求所有满足条件的整数解。讲解：首先,,xyz两两互质，事实上，设,,1,1,1,,1xydxyzddxy同理，,1,,1yzzx。其次，1111,133,2,,21,221,21,43,3,3,3,5,,,2,3,5xyzyzzxxyxyzxyyzzxxyzxyyzzxyzxxzyyzyzyyyyyyzxyz又又例题3试确定使72bab整除baba2的全部正整数对).,(ba解：.7)7()(222abbabababab)7(722abbab（i）若072ab则有：22277.abbbab矛盾；（ii）若072ab则.77722ababab72b，1b或.2b当1b时，题设成为8a整除57)8(717,17aaa有得293578a，21a或49a当2b时，aa7494由于)94(2470aa知：4794aa无整数解；（iii）若072ab则27,7kakb其中Zk此时baba2除以72bab商恰为k，题设条件满足。3综上：所有满足条件的正整数对为2(,)(21,1),(49,1)(7,7)abkk)(Nk例题4求所有的正整数n、m，满足5471mnn+=-．解原方程等价于32(1)(1)7mnnnn-+++=．显然，1n．当2n时，3221(1)()11,11nnnnnnn-+=-++++．设3217,17abnnnn-+=++=，其中,abN．于是，2(1)(71)(1)()71bannnn--=-+=-．因此，(71)|(71)ba--，即(71,71)71abb--=-．又因为(,)(71,71)71abab--=-，得到(,)bab=，即()akbkN．则32177(1)akbknnnn-+===++．当1k=时，有3211nnnn-+=++，2n=．当2k时，有32322432(1)(1)(1)(1)330knnnnnnnnnnnn，矛盾．综上所述，2,2nm==是原方程的唯一一组解．评注在解决与多项式有关的数论问题时，代数变形（如因式分解，配方）非常重要。引题1设1,,amn均是正整数，试证(,)(1,1)1.mnmnaaa证明用带余除法，当m=n时，结论显然成立，设mn且,0,mqnrrn则有21(1)()1mnmnmnmqnraaaaaa于是，(1,1)(1,1).mnnraaaa如果r=0，则有(,)(1,1)(1,1)(1,0)11,mnnrnnmnaaaaaaa即结论成立。若r不为零，不妨设11121221,0,,0,,nqrrrrrqrrrr21111,0,kkkkkkkkkrqrrrrrqr，于是有(,)(,)kmnnrr，所以1(,)(1,1)(1,1)11.krrnrrmnaaaaaa例题3证明：对每个正整数,n存在大于1且两两互质的整数01,,...,nkkk，使得011nkkk4是两个连续整数的乘积。（第37届美国数学奥林匹克）。讲解：注意到恒等式4222111aaaaaa，若1,n取011,3kk，则01112kk，假设存在大于1且两两互质的整数01,,...,nkkk，使得0111,nnnnkkkaaaN，令22211011,,...1,1nnnnnnnnnkaakkkkaaaa则221,21,21nnnnnaaaaa，所以由假设01,,...,nkkkn+1，k两两互质，且22422201111111nnnnnnnnnkkkaaaaaaaa。得证。1、例题3求使22007nn为完全平方数的自然数n的最大值。解：设222007nnk，∵nN，∴224200720072kn∴2242007k为完全平方数（否则nN）设22242007kP，2222007PkPk，设2Pka，2Pkb∴22007ab，2abP，因为要求n的最大值，所以先求P的最大值。（∵20072Pn）2200722aabaP∴设2212007,1,20072faaaafa在21,2007，在22007,2007，2max200712fa∴2maxmax200712007,100600922PPn例题6已知）（证明nn24,124。解显然，1(mod4),n故n不是完全平方数，从而,nZ若,ndndnnd且，这就表明d和n/d是两个不等的因子，从而n的因数是两两相对的，故有偶数个。5设,dn只需要证明()nddd，注意到（24，n）=1，2ndnddd，所以只需要证明22224()1(1)241dndnd。因为d为奇数，设d=2k+1,则22214(1)81,(24,)131(mod3)dkkdddd又不整除所以231.d又（3，8）=1，从而2241.d这样n的每一对因子都被24整除，结论成立。例题7．设,,abcZ使得222|abcabc，证明：存在无穷多个正整数n，使得|nnnabcabc证明设()mmmmabcSmN．可知数列mS满足递推公式321()()mmmmSabcSabbccaSabcS．（牛顿幂和公式）①由于222|abcabc，2222()()2()abcabcabbcca，可以得到|2()abcabbcca．②下面证明：若|mabcS，则3|mabcS．（1）abc为奇数，由②得|abcabbcca．又因为|mabcS，所以21|[()()]mmmabcabcSabbccaSabcS，即3|mabcS．（2）abc为偶数，因为a和1ma，b和1mb，c和1mc奇偶性相同，所以abc和111mmmabc奇偶性相同，1mS也是偶数，结合②，有1|()mabcabbccaS，又因为|mabcS，所以21|[()()]mmmabcabcSabbccaSabcS，即3|mabcS．因为1S能被abc整除，所以4710,,SSS也能被abc整除，符合要求的n有无穷多个．5、证明：存在无限多个正整数对,mn，使得11,mnnm为正整数首先1,2mn成立，设11nmkmn，11nnknmm，∴1nnm是整数。6令1nnrm，∴111nnknrmrr，11111nnnrkrnrrn，所以若,mn满足，则,rn也满足。∵21mrnnnmn＞＜，∴rm＞，所以有无穷多组满足。例9、设M为正整数，22,1SnnZMnM证明：形如,,ababSab的数两两不同。讲解：假设,,,,,abcdSabcdac，不妨设221MacdbM，则可设1,,1,,,,,,cbpappdpqcqabqdqdadaqadqqq则，222222211,1110200MqpbbqMMqqqqqdaqMqqMqMqqMq，矛盾，得证。例11、设,,,abcd为整数，且0,abcdacbdbdacbdac。求证：abcd不是质数。讲解：假设abcdp为质数，22221acbdbdacbdacbbddaacc，把pcdab代入（1）并整理得222222222,,bcbbddppcdbcbcabcdppbcŒ，222222222,22,,0,,,pbbddbbddabcdpbbddabcdbbdadcdbdaabcdbdbcdbbdcdbbdd矛盾，得证。已知例题12正整数,,,duvw，满足,,uvw互不相同，且320dduvuwvwuvw，求证：d不是质数，且求d的最小值解：假设d为质数，∵,,uvw互不相同，∴6uvw＞，uvuwvw＞11，∴3116dd＞，7∴3d＞，∴d为奇质数，易知2duvw，∵2d，设du，且'udu若dvw，则,vw中至少有一个不小于d，∴1vwd，∴1uvuwvwduvwd23＞＞d＞d，矛盾，∴dvw∴原方程化为2'12'dduvwvwu，易知2'1du，∴12'1,'2dudu，又3vw，则有1'2pduvvwuwduvwu2233p＞3d＞p，矛盾。∴d不是质数。再求d的最小值∵当,,uvw分别为1，2，3时，原方程无解∴216,14uvwuvuwvw，∴31416dd，∴5d，又d不为质数，∴6d若6d，原方程化为36620uvuwvwuvw∴62,3uvwuvw，设3u，且3'uu，则原方程进一步化为363'1'uvwvwu∴31'vwu，∵3'36,3uvwvw＜，∴14u＜，∴有3vw或12u若12u，有122,2vwvwvw，矛盾。若3vw，设3v，3'vv，则123''''''uvwuvuvw，∴''312uvw＜，''3uv＜，∴''12uv，，或21，∵''3uv，''2uv，∴原方程变为1265w，无解，∴8d当8d时，,,2,4,7uvw，满足题意，∴min8d注：利用ab，则ba，逐渐缩小取值范围二、同余例1、求证：有无穷多个,n使得21002nn。202012525120,2,251,21mod25,22mod255knn证明：8210066221006254122mod100,21006260mod100,10021006,nkknkk20k+n又，，时，2因为正整数k有无穷多个,所以，满足条件的正整数n有无穷多个。例2、证明：对任给的质数3p，总存在无穷多个正整数,n使得23nnpn。讲解：2,3,1pp，由费玛小定理，11(1)(1)(21),31,(21),31,pppkpkp