当前位置:首页 >> 学科竞赛 >>

夏建新--初等数论


2012 年江苏省高中数学奥林匹克夏令营

初等数论
江苏省南菁高级中学 夏建新 一、整除 ?带余除法:对于任一整数 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 ⑥若 n∈N*,则(a-b)|(a -b ) 。若 n 为奇数,则(a+b)|(an+bn) 。若 n 为偶数,则(a+b) n n |(a -b ) ⑦任意 n 个连续正整数的乘积必能被 n!整除。 ?当(a,b)=1 时,称 a、b 互素(互质) 。有: ①已知(a,c)=1,若 a | bc,则 a | b;若 a | b,c | b,则 ac | b ②p 为质数,若 p | ab,则 p | a 或 p | b ③[a,b]· (a,b)=ab ④(a,b)=(a,b-ac)=(a-bc,b)对任何整数 c 成立 ⑤(裴蜀定理)存在整数 x、y,使 ax+by=(a,b) ⑥m(a,b)=(ma,mb) ⑧若 a | m,b | m,则[a,b] | m ⑦若(a,b)=d,则 ( , ⑨m[a,b]=[ma,mb]

a b ) =1 d d

⑩费尔马小定理:p 是素数,则 p|ap-a - 若另上条件(a,p)=1,则 p|ap 1-1 例 1、求所有的正整数 n,使得 8n+n 可以被 2n+n 整除。 (2009 年日本数学奥林匹克) (m,n) 例 2、设 n?m?1,m、n 为整数,证明: ·Cm为整数。 (2000 年普特南) n n 例 3、求所有的正整数 n,使 n 能被所有不大于 n的正整数整除。 例 4、 已知 a, c 为两两互质的正整数, a2|(b3+c3), 2|(a3+c3), 2|(a3+b3), a, c 的值. b, 且 b c 求 b, (2011 年东南数学奥林匹克) 例 5、求有序三元正整数组(a,b,c)的个数,其中[a,b]=1000,[b,c]=2000,[a,c]=2000。 ([x,y]表示 x、y 的最小公倍数) 例 6、证明:对所有的非负整数 n,77 +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

2012 年江苏省高中数学奥林匹克夏令营

⑤若 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) n n ⑦若 a≡b(mod m) ,n∈N*,则 a ≡b (mod m) ⑧若 ac≡bc(mod m)(c,m)=d,则 a≡b(mod , m ) d

⑨费尔马小定理: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 年巴西数学奥林匹克) n 例 9、证明:对任意质数 p,存在无限多个形如 2 -n 的数被 p 整除。 例 10、已知 p 是奇素数,证明:

?k
k ?1

p ?1

2 p ?1

?

p( p ? 1) (mod p 2 ) (第 36 届加拿大数学奥林匹克) 2

例 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]+n,{x+n}={x} na a ④ [x]+[y]?[x+y]?[x]+[y]+1。特别地,? ??n? ?(n∈N*) ? b ? ?b? ⑤若 x,y>0,则[xy]?[x][y]。特别地,[ x]n?[x](n∈N*) x [x] ⑥若 n∈N*,则? ?=? ? ?n? ? n ? x x x ?在 n!的素因数分解的标准式中,素因数 p 的最高次幂的次数为:? ?+? 2?+? 3?+… ?p? ?p ? ?p ? 例 16、[x]表示不超过 x 的最大整数,{x}=x-[x]。解方程[x] {x}=2005x(2005 年第 15 届泛非数学 奥林匹克)
n

2012 年江苏省高中数学奥林匹克夏令营

例 17、设 n 是正整数,a=[ n](其中,[x]表示不超过 x 的最大整数) 。求同时满足下列条件的 n 的 3 2 最大值:?n 不是完全平方数; ?a |n (第三届北方数学奥林匹克) 2、数的进位制: ?给定一个 m 位正整数 A, 其各位上的数字分别记为 an,an-1,…,a1,a0, 此数可简记为 A= anan-1…a1a0 (其中 an≠0)即 A=an· n+an-1· n 1+…+a1· 10 10 10+a0,其中 ai∈{0,1,2,…,9},i=0,1,2,3,…,n,an≠0. A 可简记为:A=(anan-1…a1a0)10,对于 10 进制正整数,通常将下角码 10 省略不写,括号也不写。 ?整数的表示除十进制外,二进制、八进制等 p 进位制的记数法已被广泛采用。p 进制记数法的基 本原则是:“逢 p 进 1”。 一般地,正整数 A 的进位制表示:给定一个自然数 p,将任一正整数 A 唯一地表示成上述形式: - A=an·n+an-1·n 1+…+a1· 0,其中 ai∈{0,1,2,…, p-1},i=0,1,2,3,…,n,an≠0.n 为十进制数, p p p+a 可简记为:A=(anan-1…a1a0) p. ?十进制数化为 p 进制数的方法:除以 p 将余数倒过来写即可。 - ?p(非 10)进制数化为十进制数:直接化,(anan-1…a1a0) p=an·n+an-1·n 1+…+a1· 0. p p p+a ?不同进位制之间相互转化常用十进制进行过渡。 a1 a2 a3 a4 例 18、记集合 T={0,1,2,3,4,5,6},M={ + 2+ 3+ 4|ai∈T,i=1,2,3,4},将 M 中的 7 7 7 7 元素按从大到小的顺序排列,则第 2005 个数是
n n


(2005 年全国高中数学联赛)

例 19、对于正整数 n,令 fn=[2 2008]+[2 2009].求证:数列 f1,f2,…中有无穷多个奇数和无 穷多个偶数.([x]表示不超过 x 的最大整数) (2008 年第七届中国女子数学奥林匹克)

练习
1、求正整数 n,使得[log31]+[log32]+[log33]+[log34]+…+[log3n]=2007,其中[x]表示不超过 x 的 最大整数. (2007 年上海市 TI 杯高二年级数学竞赛) 2、n 为正整数,证明:120|n(n2-1)(n2-5n+26) 3、对哪些 n∈N*,存在 a,b∈Q\Z 使得 a+b 和 an+bn 都是整数? (克罗地亚)

3l 3m 3n } ? { 4 } ? { 4 } ,其中{x}=x-[x], 104 10 10 而[x]表示不超过 x 的最大整数.求这种三角形周长的最小值. (2003 年全国高中数学联合竞赛)
4、设三角形的三边分别是整数 l,m,n,且 l>m>n,已知 { 10n-1 5、设 n 是一个正整数,定义: (n)= = 111?111 ,例如(1)=1, (2)=11, (3)=111. ? ?? ? ? 9
n个1

(1)设 m 是一个非负数.证明:(3m)可以被 3m 整除,而不能被 3m 1 整除. (2)证明 n 能被 27 整除当且仅当(n)能被 27 整除(2008 年日本东京大学入学考试题) 6、证明存在正整数 n 使 1987|11…199…988…877…7
n个 n个 n个 n个



7、证明:?如果正整数 n 使方程 x3-3xy2+y3=n 有一组整数解(x,y) ,则这个方程至少有三组整 数解。?当 n=2891 时,上述方程无整数解。 (23 届 IMO) x x x 8、设 n 是正整数,记 n!=1×2×…×n。求方程? ? +? ? +…+? ? =2011 的所有正整数解 1!? ?2!? 11!? ? ? ([a]表示不超过 a 的最大整数)(2011 年北京市中学生数学竞赛复赛) 。

2012 年江苏省高中数学奥林匹克夏令营

9、在三进制中,数 x 的表示是 12112211122211112222,则 x 在 9 进制中表示式中最左边一位是什么 数? 10、在 1,2,…,2k+1-1 中,有些数写成二进制时数字和为偶数,求这些数的和。

参考答案: 1、因[log31]=[log32]=0,即[log31]+[log32]=0,[log33]+[log34]+…+[log38]=6×1=6,[log39]+ [log310]+…+[log326]=18×2=36, 327]+[log328]+…+[log380]=54×3=162, 381]+[log382] [log [log +…+[log3242]=162×4=648,[log3243]+[log3244]+…+[log3728]=486×5=2430>2007 所以,243<n<728。于是,6+36+162+648+(n-242)×5=2007,解得 n=473 2、120=23·3·5,n(n2-1)(n2-5n+26)=20 (n-1)n(n+1)+(n-3)(n-2) (n-1)n(n+1) ∵3!|(n-1)n(n+1), ∴120|20 (n-1)n(n+1) ∵5!|(n-3)(n-2) (n-1)n(n+1), 120|(n-3)(n 即 2 2 -2) (n-1)n(n+1) ∴120|n(n -1)(n -5n+26) 3n-1 1 3、当 n 为奇数时,取 a= ,b= .由于 1n+(3n-1)n 被 1+(3n-1)=3n 整除.故 a,b 满足条件.即 n 可 3 3 x z 为任何大于 1 的奇数. 设 n 为偶数,若有满足条件的 a= ,b= (x,y,z,w∈Z,y,w>1,(x,y)=(z,w)=1).则 y w xw+yz 由 a+b= ∈Z 得到 yw|(xw+yz),y|xw,但(x,y)=1,故 y|w.同理,w|y.因此 y=w.z=ky-x.再由 an+ yw xn+zn bn= n ∈Z 得到 yn|(xn+zn).但 xn+zn=My2-nkxn-1y+2xn,故必 y|2xn.由 y>1 及(x,y)=1 得到 y=2 且 y x 为奇数.由于 n 是偶数,4|(My2-nkxn-1y),从而 4|2,矛盾.所求的 n 是大于 1 的一切奇数. 4、当 s=1,r=2,n=501 时三角形的周长最小,其值为 3003. 5、(2)提示:首先证明:若 27|n,则 27|(n)。设 n=27k,则(n)=(27)×

?10
i ?0

k ?1

27 i



再证明:若 27|(n),则 27|n。 27|(n),即 35|(10n-1)。 6、提示:首先证明存在正整数 n,使 1987|11…1。 个 1) (n 。另一方面,11…199…988…877…7= 3n 2n n 11…1×10 +9×11…1×10 +8×11…1×10 +7×11…1=11…1×(103n+9×102n+8×10n+7) 。 由 1987|11…1 知结论成立。 7、?因(y-x)3-3(y-x)x2+(-x)3=x3-3xy2+y3,∴(x,y)为方程 x3-3xy2+y3=n 的整 数解时, (y-x,-x)也是解。将 y-x 当作 x,-x 当作 y,则由于(-x)-(y-x)=-y,- (y-x)=x-y,故(-y,x-y)也是方程的解。 这三组解互不相同,因任两组相同将导出 x=y=0 与 n 为正整数相矛盾。 ?若 x3-3xy2+y3=2891,则 x3-3xy2+y3≡2(mod 9) ,从而 x、y 不能都被 3 整除。若 x、y 中恰 有一个被 3 整除,用(y-x,-x)或(-y,x-y)代替(x,y) 。因此可假定 x、y 都不被 3 整除, 3 3 2 从而 x ≡±1。y ≡±1,-3xy ≡±3(mod 9) ,矛盾。 8、所求为 x=1×720+3×120+3×24+3×6+1×2+0×1=1172 9、∵32=9,将 x 的三进制表示的数一对对地组合,得 x=(1·19+2·18)+(1·17+1·16)+…+(2·1 3 3 3 3 3 +2)=(1×3+2)(32)9+(1×3+1)(32)8+…+(2×3+2)=5×99+4×98+…+8∴x 的九进制的第一个 数字是 5。 1 + - 10、所求的和为 (1+2+…+2k 1-1)=2 2k-2k 1 2


相关文章:
夏建新--初等数论
夏建新--初等数论_学科竞赛_高中教育_教育专区。2012 年江苏省高中数学奥林匹克夏令营 初等数论江苏省南菁高级中学 夏建新 一、整除 ?带余除法:对于任一整数 a 和...
侯绪兵--初等数论
朱震--初等数论 陈培东-初等数论 夏建新--初等数论 曹瑞彬--初等数论1...2012 年江苏省高中数学奥林匹克夏令营讲座资料 初等数论江苏省扬州中学一. 整数 ...
于忠明--数学思想方法
夏建国--赛题选讲 夏建新--初等数论 徐昌根--组合初步 徐德同--平面几何 徐贻林--数学思想方法 徐志春--函数综合 俞向阳--不等式 翟小军--平面几何 周敏泽...
高一物理竞赛试题-新课标
4页 免费 夏建新--初等数论 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
更多相关标签:
初等数论 | 初等数论第三版答案 | 初等数论 pdf | 初等数论 潘承洞 | 初等数论及其应用 | 初等数论难题集 | 初等数论视频 | 初等数论100例 |