2012年数学夏令营——初等数论讲义 - 杭州奥林教育学校

2012年数学夏令营——初等数论讲义 - 杭州奥林教育学校 Aolinedu 数学夏令营 初 等 数 论 (2012杭州奥林教育数学夏令营讲义) 第一部分 一、整除的基本性质 1、 d,a和d,a同时成立的充要条件是，对任意的x，x?Z，有d,ax，ax。 12121122 2、a,b和b,a同时成立的充要条件是,a,,,b,?0。 3、设a,b。若b?0，则,a,?,b,。不等于0的整数只能有有限个除数; 4、 设ax，my=1。那么，m,ab的充要条件是m,b。一般地，对正整数h，k， hkhm,ab的充要条件是m,b。 二、带余除法 带余数除法的基本形式) 对任给的整数a?0和b，一定存在唯一的一对整数q和r，满足 b,qa，r， 0?r,,a,。 (1) 上式中的q称为是b被a除所得的部分商，r称为是b被a除所得的最小非负余数。此外，b被a整除的充要条件是r=0。 三、最大公约数和最小公倍数 性质1 (i) a，a，…，a的最大公约数与这些数的次序无关，即若a，a，…，a是12k11121ka，a，…，a的一个重新排列，则(a，a，…，a)=(a，a，…，a)。 12k12k11121k (ii) 任意改变a，a，…，a的正负号，它们的最大公约数不变。事实上，总有 12k (a，a，…，a)=(,a,，,a,，…，,a,)。 12k12k (iii) 若a,a，则(a，a，…，a，a)= (a，a，…，a)。 ,,,1kk12k1k12k1 (iv) 对任意整数x有，(a，a),(a，a，ax)。一般的有， 12121 (a，a，…，a)=(a，a，ax，…，a)。 12k121k (v) 设正整数m,(a，a，…，a)，则有m(a/m，a/m，…，a/m)= (a，a，…，a)。12k12k12k特别的， (a/(a，a)，a/(a，a)),1，及(a/D，a/D，…，a/D)=1，其中D=(a，a，…，a)。 11221212k12k 2、裴属定理 存在整数x,y使得 xaybab，,(,) 四、素数与唯一分解 1、素数有无限多个。 ,,,12snppp,...2、 标准分解式:每个大于1的正整数都可以唯一的表成 n12s的形状，其中是素数，而是正整数，这叫做的素因子标nppp,,,？,,,,,...,12s12s 准分解式。 第二部分 一、高斯函数 1、 [][]1,xxx,,， Aolinedu 数学夏令营 2、若 xyxy,,,[][] 、若n为整数， 3[][]nxnx，,， 4、 [][][][][]1xyxyxy，,，,，， 5、若 xyxyxy,,,,0,0[][][] []xx6、若n为整数， [][],nn x[]7、若x为实数，n为正整数，则在不超过x的正整数中，n的倍数共有 n nnn,,，18、设是素数，如果，则pn,，，， (!)[][]...[]pp,n,p2,ppp 12n,1[nx],[x]，[x，]，[x，]，？，[x，]恒等式 nnn二、欧拉函数 kk,11、若p为素数，则若p为合数，则 ,()2,pp,,,,()1,()(1),ppppp,,,, 1nn,()2、不超过n且与n互质的所有正整数的和为则; 23、若 (,)1()()(),ababab,,,,,, 111,,,t124、 npppnn,,,,,？？,,()(1)(1)(1),12tppp12k n,()5、设d为n的正约数，则不大于n且与n有最大公因数d的正整数个数为，同d n,,()(),,dn时; ,,ddndn abab,,,()()6、若 三、积性函数 设n为一个正整数，分别用 所有正约数的和,所有正约数乘积. TnSnPnn(),(),()表示的所有约数个数, 1,，1ttiTn()p,12,TnSnPnn()(1);()();(),，,, ,,ip,1ii,,11i 第三部分 一、基本概念 Aolinedu 数学夏令营 1.定义:若整数a,b被整数m(m?1)除的余数相同,则称a同余于b模m,或a,b对模m同 余.记为a?b(modm). 2.性质(?)a?b(modm)m|a-b,即a=b+mk,k?Z. , (?)若a?b(modm),b?c(modm),则a?c(modm). (?)若a?b(modm),a?b(modm)， 1212 则a?a?b?b(modm),aa?bb(modm) 12112122 nn-1nn-1(?)设f(x)=ax+ax+…+ax+a,g(x)=bx+bx+…+bx+b是两个整系数多项式,nn-110nn-110满足a?b(modm)(0?i?n).若a?b(modm),则f(a)?f(b)(modm). ii m(?)ac?bc(modm)a?b(mod), ,(c,m) (?)若m?1,(a,m)=1,则存在整数c使得ac?1(modm). -1称c为a对模m的逆或倒数,记为c=a(modm) ,(mod)abm,1a,b(?)同时成立(mod[m,m]). ,,12a,b(modm)2, (?)若a?b(modm),a?b(modm),且(m,m)=1,则a?b(modmm). 121212 剩余 二、剩余类与剩余系 、设m为正整数，把全体整数按对模m的余数分成m类，相应m个集合记为:1 K,K,…,K,其中K={qm+r|q?Z,0?余数r?m-1}称为模m的一个剩余类。 01m-1r 性质:对任意a、b?Z，则a、b?Ka?b(modm). ,r 2、完全剩余系:设K,K,…,K为模m的全部剩余类，从每个K里任取一个a，得01m-1rr m个数a,a,…,a组成的数组，叫做模m的一个完全剩余系。0,1,2,…,m-1叫做模m的最01m-1 小非负完全剩余系。 性质(?)m个整数构成模m的一完全剩余系两两对模m不同余。 , (?)若(a,m)=1，则x与ax+b同时跑遍模m的完全剩余系。 3、既约剩余系:如果K里的每一个数都与m互质，则K叫与m互质的剩余类，在rr与模m互质的全部剩余类中，从每一类任取一个数所做成的数组，叫做模m的一个既约剩 余系。 性质(?)K与模m互质K中有一个数与m互质; ,rr Aolinedu 数学夏令营 (?)与模m互质的剩余类的个数等于; ,(m) ?)若(a,m)=1,则x与ax+b同时跑遍模m的既约剩余系。 ( d,(?)设(a,p)=1,则d是a对于模p的阶ao?1(modp),且 0 do-11,a,…,a对模p两两不同余. Φ(p)-1特别地,d=Φ(p)1,a,…,a构成模p的一个既约剩余系. ,o 三、重要定理 φ(m)1、Euler定理:设整数m>1,且(a,m)=1.则有a?1(modm). p2、Fermat定理:设p是素数,则对任意正整数a有a?a(modp). 证明:若p|a,则显然成立.若(p,a)=1,则a,2a,…,(p-1)a对modp余数各不相同(若 p|(m-n)a(n0，设于是有故给出PELL方程的一,,,，,,xymxym,,xmy,,,()1,,, n组解，又x>0,y>0,所以不同的n给出的也不同，即知,给出无穷多组解x>0,y>0。反之， nn,,，xym,,,,,方程的任意解x>0,y>0可以表示为的形状，否则因为, nnn，1,,,,，,xymxymxym，,，，故存在某个数n>,，使得，两边乘以得00 22nnuvm,,1,1(),，,xym,,uvmxym，,，(),，设，显然 故u，v是 1,,,,方程的解，，而uvmuvmuuv，,,,,,,,,,1,0121,0,0 uvm， ,,，xym，与最小性矛盾。 uvm，,,00 22说明, 佩尔方程的变形为，其解为 xmy,,,1x,x,y,y(n,1,2,3...)nn 1,2n,12n,1,，，,x[(xmy)(xmy)]n1111,,2其解为 ,12n,12n,1,，,,,y[(xmy)(xmy)]n1111,2m, 第五部分 21(求出满足以下两个条件的最大的正整数:,1,n可以表示成两个连续整n Aolinedu 数学夏令营 279n，数的立方之差,,2,是平方数. 答案:181. 3322解:由条件可设～化简后可得. (1)mmn，,,3(21)(21)(21)mnn，,,， 21n,21n，由于和是两个连续的奇数～它们互质～因此它们其中之一是平方数～ 21n，21n,另一个是某个平方数的3倍. 若是平方数～则是某个平方数的3倍～ 21n，21n,这意味着模3余2～而这与平方数模3余0或1矛盾. 因此是平方数. 22结合条件2～可设～～其中是正奇数. 21np,,279nq，,pq, 22qpqp,，,由于～且均为偶数～故 80()(),,,,，qpqpqp . 2()()24042qqpqp,,，，,，, 2q,79n,181因此～即. 经检验满足题目条件～故所求最大的为nq,21n,,1812 181. abab,abc,,2. 设正整数最大公约数为1，且，证明是一个完全平方,cab, 数。 nn,，，n,2[(35)]13. 证明。 2mnmnmn,:()4(1)，， 4. 求所有的正整数。 5 设是整系数多项式，且(素数)，证明不存在整数fx()fffp(1)(2)(3),,, m,。 fmp()2, xfxpxfxpxfxp,,,,,,1(),2(),3(),证明 由题设由此可得 (1)(2)(3)()()(1)(2)(3)()xxxfxpfxpxxxgx,,,,,,,,,, g(x)是整系数多项式，假如存在整数m，使得 fmp()2, pfmpmmmgm,,,,,,()(1)(2)(3)() 若则 mp,,1,mmm,,,,,21,3,1,或者上式将不能成立.同理 mmgmp,,2,3,().以及都不可能是 abc,,abcbaccab,,,1,1,1abc,,6. 已知满足，求的值。 1(求所有n?N*使得它恰有16个正因数1=d54,则d=27,d=54,d=p,仅一解p=71. 789 共有2个解n=54?37=1998或54?71=3834. 7. 令表示正整数n的所有正约数的和，证明存在无穷多个正整数n使fn() 得。 fnn()2012, n21002，n 8. 求证:有无穷多个使得。 n,，， 1,,2020knn，,证明:？,，,,,？,？,2525120,2,251,21mod25,22mod25，，，，，，，，,,5,, 220k+nnk，100662又，，时，？254122mod100,2100626,？,,？，，,，nk2，，，，，， 21006k， ,？，，0mod100,10021006,k因为正整数k有无穷多个,所以，，，，， 满足条件的正整数n有无穷多个。 ，9. 设表示不大于n的质数的个数，证明，总存,()n,,,,nNknkN,()(),在n个连续正整数，其中恰有k个质数。 210 证明存在无穷多个正整数n使得( (1)!nn， 2n，122令nypellyyn，,,,,15,,,(2,1),5,22显然这是一个方程为其一解又 5显然5,y,2y互不相同,切都小于n,而Pell方程有无穷多组解，所以命题成立。 abc,,abc,,11. 正整数的最大公约数为1，对于数组()进行如下变换:每一步将数组种的一个数加上另一个数的整数倍，求证至多经过5步可以得到(1,0,0)，(0,1,0)，(0,0,1)这三个数组之一。 n{x}: x1,3[5],,，xxx12. 数列，证明对于任意的。 nx,2nnnn01，，2n 21n，103n13. 是否存在正整数n，使得，且。 22(mod),n 2102n提示:有已知。设(2n,102)=d.。 21(mod102),21(mod102),,以及 Aolinedu 数学夏令营 dn221(mod102)1721(mod17),,,,d。同理可得 21n，82422(mod4)nn,,,。矛盾。 3714. 设质数p,q满足，求p,q的值。 ppqq,,, 733提示:由函数的单调性可知pq,。当q大于11时，由 fxxx(),, 222，矛盾。所以。由此得q=3。 q,11pqqqqq，，,，，,112 54mnn+=-7115. 求所有的正整数n、m，满足( 32m解 原方程等价于( (1)(1)7nnnn-+++= 显然，( n,1 322当时，( nnnnnnn-+=-++>++>1(1)()11,11n,2 32abnnnn-+=++=17,17设，其中(于是， abN,,， ba2 ( (1)(71)(1)()71nnnn--=-+=- baabb因此，，即( (71)|(71)--(71,71)71--=- abab(,)bab=(,)又因为，得到，即( (71,71)71--=-akbkN,,()， 32akbk则( nnnn-+===++177(1) 32nnnn-+=++11当时，有，( k=1n=2当时，有 k,2 32322432k ， (1)(1)(1)(1)330nnnnnnnnnnnn,，,，，,,，,，，,,,,,, nm==2,2矛盾(综上所述，是原方程的唯一一组解( 44216 证明方程没有正整数解。 xyz，, 证明 设是满足方程的一组解的最小值。 首先我们证明和zx(,,)xyzy000000 24442互质(若和有一个相同的素因子，则，因此(这样pxyz，,pzxyp000000xyz442000也是方程的一组解，这与的最小性矛盾，因此和(,,)zxyxyz，,0002ppp Aolinedu 数学夏令营 2,xmn,20,22222ymn,,(,,)xyz互质，于是就是勾股方程的本原解，所以可设，其中mn,,0000 ,22zmn,，0, 是正整数，，(),1，和一奇一偶( mn,mnmn, xnn22220ymn,,得知m是奇数且n是偶数，由于()(),m，所以m和都从0222 nn22是平方数(因为m和mrs,,,互质)，即有，其中r和s是互质的正整数(于22 2224422222222222ymnrs,,,,4ysr，,(2)()ysr，,(2)()ys,2是，，即(这样0000 22,yab,,0,2222sab,r和也是勾股方程的本原解，所以又有，其中，a和abab,,,(,)1, ,222rab,，, b一奇一偶( 222442由于，则a，b也是平方数，从而有，于是，sab,afbg,,,fgr，, 2222亦即是说(f,g,r)也是原方程的解，留意到，这与的最rmmnz,,，,z0 442小性矛盾，从而方程没有正整数解( xyz，, abab,17. 求所有满足方程的非负整数解 2，,35 abab, 解 (1)当02,,,,,，,,abab,0325,方程无解。(2)当ab,,0, aaaa当ba,,，,，,015,,152因对所有的正整数有2,所以无解。 ,,ababaab当b0,，,,，对23532两边模得到2(mod3), ,ababb又2,,221(mod3),，所以2所以为偶数。b 若为奇数，则有，两边模aa,38有 bab,,1abbabab,,,，11222，,,,,,,,339155(mod8)而 5255(mod8),矛盾 故为偶数，设a=2p,a-b=2q,则有a 222()qppq,5,,,23 qpm,235,, ,,qpnqmnmnm55，,,，,，,，232333(31) , ,mnpq，,,2(), Aolinedu 数学夏令营 mqqpqp,，,,,,,,,,302112,2555m p两边模得到所以，420(mod4),2,,p 当时，p,22q=1,a=4,b=， qpqp 当时pq,,,,,,321215(mod8),5,两边mod8,5或为偶数 p再两边得到矛盾mod3,1(1)1(mod3),.,,, ppqq(72)(72),,18. 求所有的素数p,q，使得为整数。 pq 19.(1)证明，若p(n)表示 n的各位上的数字之积，则p(n)< n。 n5(2)存在唯一的n位十进制数，能被整除，其各位上的数字都属于{1，2，3，，5}。 4 20. 如果一个正整数的十进制表示是一个数字块及紧跟在它后面的一个完全相同的块组成，则称这个数为二重数，例如360360，证明有无穷多个二重数十完全平方数。