夏建新--初等数论.docVIP

初等数论 江苏省南菁高级中学 夏建新 一、整除 ⑴带余除法：对于任一整数a和任一非零整数b，必有惟一的一对整数q和r，使得a＝bq＋r，0≤r＜b，且q和r由上述条件惟一确定。 　若r＝0，则称b | a。 ⑵部分性质： ①若c | b，b | a，则c | a ②若c | a，d | b，则cd | ab ③若c | a，c | b，则c |（ka＋nb）；若c | a，c b，则c （a＋b） ④若ma | mb，则a | b ⑤若a＞0，b＞0，b | a，则b≤a ⑥若n∈N*，则（a－b）|（an－bn）。若n为奇数，则（a＋b）|（an＋bn）。若n为偶数，则（a＋b）|（an－bn） ⑦任意n个连续正整数的乘积必能被n！整除。 ＝1 ⑧若a | m，b | m，则[a，b] | m ⑨m[a，b]＝[ma，mb] ⑩费尔马小定理：p是素数，则p|ap－a 若另上条件（a，p）＝1，则p|ap－1－1 例1、求所有的正整数n，使得8n＋n可以被2n＋n整除。（2009年日本数学奥林匹克） 例2、设n≥m≥1，m、n为整数，证明：·C为整数。（2000年普特南） 例3、求所有的正整数n，使n能被所有不大于的正整数整除。 例4、已知a，b，c为两两互质的正整数，且a2|(b3＋c3)，b2|(a3＋c3)，c2|(a3＋b3)，求a，b，c的值．（2011年东南数学奥林匹克） 例5、求有序三元正整数组（a，b，c）的个数，其中[a，b]＝1000，[b，c]＝2000，[a，c]＝2000。（[x，y]表示x、y的最小公倍数） 例6、证明：对所有的非负整数n，7＋1至少是2n＋3个质数（不一定互不相同）的乘积。（2007年第36届美国数学奥林匹克） 例7、是否存在奇数n（n≥3）及n个互不相同的质数p1，p2，…，pn，使得pi＋pi＋1（i＝1，2，…，n，pn＋1＝p1）都是完全平方数？请证明你的结论。（2011年中国西部数学奥林匹克） 二、同余 1、定义：设m是正整数，叫做模，若m|（a－b），称a，b对模m同余，记作a≡b（mod m） 2、性质：①a≡a（mod m） ②若a≡b（mod m），则b≡a（mod m） ③若a≡b（mod m），b≡c（mod m），则a≡c（mod m） ④若a≡b（mod m），c≡d（mod m），则a±c≡b±d（mod m），ac≡bd（mod m） ⑤若n|m，a≡b（mod m），则a≡b（mod n） ⑥若（m，n）＝1，a≡b（mod m），a≡b（mod n），则a≡b（mod mn） ⑦若a≡b（mod m），n∈N*，则a n≡b n（mod m） ⑧若ac≡bc（mod m），（c，m）＝d，则a≡b（mod ） ⑨费尔马小定理：p是素数，则a p≡a（mod p） 若另上条件（a，p）＝1，则a p－1≡1（mod p） 3、剩余类：把关于模m同余的数归于一类，每类称为一个模m的剩余类。 剩余类的结构很简单，设A是余数为r的剩余类，则A＝{qm＋r|m是模，r是余数，q＝0，±1，±2，…} 设A1、A2、…、Am是模m的m个剩余类，从Ai中取一数ai，则a1，a2，…，am称为模m的一个完全剩余系，简称m的完系。 例8、证明：不存在正整数x，y满足x3＋y3＝22009。（2009年巴西数学奥林匹克） 例9、证明：对任意质数p，存在无限多个形如2 n－n的数被p整除。 例10、已知p是奇素数，证明：（第36届加拿大数学奥林匹克） 例11、求所有的素数对（p，q），使得pq|5p＋5q．（2009年CMO） 例12、试确定具有下述性质的所有正整数n：集合M＝{n，n＋1，n＋2，n＋3，n＋4，n＋5}可以分成两个不相交的非空子集，使得一个子集中所有元素的积等于另一子集的所有元素之积。（第12届IMO） 三、不定方程 例13、将棱长为某整数的正方体切割成99个小正方体，其中98个是棱长为1的正方体，另一个正方体的棱长也是整数，求原正方体的棱长。 例14、求所有满足方程3×2m＋1＝n2的正整数对(m，n)（2009年新加坡数学奥林匹克） 例15、求所有的正整数a、b、c，其中1＜a＜b＜c，使得(a－1)(b－1)(c－1)是abc－1的约数。（第33届IMO） 四、其它 1、高斯函数 ⑴定义：[x]表示不超过x的最大整数，通常称y＝[x]为取整函数，也称高斯函数，记{x}＝x－[x]，y＝{x}称为x的小数部分函数。 ⑵性质：①[x]＋{x}＝x　　　　x－1＜[x]x＜[x]＋1，0{x}＜1 ②y＝[x]x1≤x2，则[x1]≤[x2] ③若n∈Z，则[x＋n]＝[x]＋