《数学竞赛辅导》——初等数论

1、数学竞赛辅导初等数论部分数论是竞赛数学中最重要的一部分，特别是在1991 年， IMO 在中国举行，国际上戏称那一年为数论年，因为 6 道 IMO 试题中有 5 道与数论有关。数论的魅力在于它可以适合小孩到老头， 只要有算术基础的人均 可以研究数论在前几年还盛传广东的一位农民数学爱好者证明 了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最 难的数论问题，适合于任何人去研究。初等数论最基础的理论在于整除，由它可以演化出许多数论定 理。做数论题，其实只要整除理论即可， 然而要很快地解决数论问题， 则要我们多见识， 以及学习大量的解题技巧。 这里我们介绍一下数论 中必需的一个内容：对于a

2、,b N, q,r N，满足a bq r，其中0 r b。除了在题目上选择我们努力做到精挑细选， 在内容的安排上我们 也尽量做到讲解详尽，明白。相信通过对本书学习，您可以对数论有 一个大致的了解。希望我们共同学习，相互交流，在学习交流中，共 同提高。编者：刘道生2007-8-21 于江西赣州第一节整数的p进位制及其应用人们发明了进位制,近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现,比如处理数字问题、处理整除问题及处理正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数, 这是一种位值记数法。 进位制的创立体现了有限与无限的对立统一关系,数列问题等等。在本节，我们着重介绍进位

3、制及其广泛的应用。基础知识ami,am 2, ,ao，则此数可以简给定一个 m位的正整数 A,其各位上的数字分别记为记为：A am iam 2a。（其中 am 1 0 ）。由于我们所研究的整数通常是十进制的，因此A可以表示成10的m 1次多项式，即A （am 1am 2a°）10。在我们的日常A ami 10m1 am 2 10m 2ai 10 a。，其中 a： 0,1,2, ,9, i 1,2, ,m 1 且am 10 ,像这种10的多项式表示的数常常简记为生活中，通常将下标10省略不写，并且连括号也不用，记作A am1am2 a0 ,以后我们所讲述的数字，若没有指明记数式的基，

4、我们都认为它是十进制的数字。但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用 0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。为了具备一般性，我们给出正整数A的p进制表示：A am1 pm1 am 2 pm2a1 p a°，其中 a： 0,1,2, , p 1, i 1,2, ,m 1 且am 10。而m仍然为十进制数字，简记为 A （am 1am 2

5、a°） p。典例分析例1 将一个十进制数字 2004 （若没有指明，我们也认为是十进制的数字）转化成二进制与 八进制，并将其表示成多项式形式。分析与解答分析：用2作为除数（若化为p进位制就以p作为除数），除2004商1002,余数为0;再 用2作为除数，除1002商501余数为0;如此继续下去，起到商为0为止。所得的各次余数按从左到右的顺序排列出来，便得到所化出的二进位制的数。解：各次商数被除数除数同理，有(2004) 10 (3274)8 , 2 10143 83 28278 4。处理与数字有关的问题，通常利用定义建立不定方程来求解。例2.求满足abc (a b c)3的所有三位数

6、abc 。(1988年上海市竞赛试题)解:由于100abc999，则100(a b当abc5时，53125(125)3;当abc6时，63216(216)3 ；当abc7时，73343(343)3;当abc8时，83512(512)3;当abc9时，93729(729)3;512。c)3999，从而 5 a b c 9 ；于是所求的三位数只有例3.一个四位数，它的个位数字与百位数字相同。(即个位数字与千位数字互换，十位数字与百位数字互换) 差为7812，求原来的四位数。如果将这个四位数的数字顺序颠倒过来，所得的新数减去原数，所得的(1979年云南省竞赛题)解：设该数的千位数字、百位数字、十位数

7、字分别为x,y,z，则原数 103x 102 y 10z y颠倒后的新数 103y 102z 10y x由得 7812 = 999(y x) 90(z y)即 868111(y x) 10(z y) 102(y x)10(zy) (yx)比较式两端百位、十位、个位数字得y x8,z由于原四位数的千位数字x不能为0,所以x1，从而y x又显然百位数字y 9，所以y 9,x 1, z x 67。所以所求的原四位数为1979。例4.递增数列1,3 , 4,9 , 10,12,13 ,是由一些正整数组成，它们或是3的幕，或是若个不同的3的幕之和，求该数列的第100项。 解：将已知数列写成 3的方幕形式

8、：（第4届美国数学邀请赛试题）a130,a231,a33130®32且 3230,a63231,a732 3130,易发现其项数恰好是自然数列对应形式的二进制表示:即 120,221,32120,422,522 20,6222,722 2120,由于 100 = (1100100)2262522所以原数列的第100项为363532981 o例5. 1987可以在b进制中写成三位数xyz，如果7，试确定所有可（1987年加拿大数学竞赛试题）能的x,y,z和b om是由n取消它的中间一个数码后所成的四位（第3届加拿大数学竞赛试题）m解：设n xyzuvx 104y 103z 102u 1

9、0x 1 ；m xyuvx 103y 102u 10v ;而k是整数，可证9mmn,即39(x 10y 102即80u8v 103x102y102z ,这显然是成立的;v ,又可证u 10例6 设n是五位数（第一个数码不是零）数，试确定一切n使得-是整数。其中 x, y,z,u,v43v) x 10 y 10n 11m，即 x 1C4 y 1C3 z16 u 10 vv 11(x10"y 102 u 100,1,2,9且2z10 u10 vV）即(b1)(b1)xy19622 32 109 ,由b10 知 b 19 o由 19622b 1知b196345故9b145 ；又因为 196

10、2232 109有 12 个正约数，分别为 1,29,18,109,218,327,654,981,1962，所以b 118，从而b 19o1)y(b 1)162 ,9,z11.5,y1987,x y z解：易知xb225 ,从而 x(b2,3,6,又由 19875 1929 19 11 知 x于是 n 10m，即 x 1tf y 10 z 1tf u 10 v= 10(x 103102u 10v)即102z 103x 102 y 102u 10v，这显然也是正确的。k 10 ；于是9m n 11m，即9 k 11，又因为k是整数，从而即 z 102 90u 9v 9（10 V），而 9|1O

11、2Z但 3 102知 z 9t（t 为正整数）从而t 102 10u v，显然t u v 0,因而推得n xyZOO N 103其中10 N 99。例7若n 1,2,100且n是其各位数字和的倍数，这样的 n有多少个？（2004年南昌竞赛试题）解：（1 ）若n为个位数字时，显然适合，这种情况共有 9种；（2）若n为100时，也适合；（3）若n为二位数时，不妨设 n ab，则n 10a b，由题意得（a b） |（10 b）即10a b z即空 Z也就是（a b） |9a ；a ba b若b 0显然适合，此种情况共有9种；若 b 0，则由 aba，故 31 （a b）若（a b）|9，则显然可以

12、，此时共有 2+ 8= 10个；若（a b） 9,则a b 6或a b 12，这样的数共有24,42,48,84 共4个；综上所述，共有 9+ 1 + 9+ 10 + 4 = 33个。例&如果一个正整数 n在三进制下表示的各数字之和可以被3整除，那么我们称n为“好的”则前2005个“好的”正整数之和是多少？ （ 2005年中国奥林匹克协作体夏令营试题） 解：首先考虑“好的”非负整数，考察如下两个引理：引理1.在3个连续非负整数3n,3n 1,3n 2 （ n是非负整数）中，有且仅有1个是“好的”。证明：在这三个非负整数的三进制表示中，0,1 , 2各在最后一位出现一次，其作各位数字相同

13、，于是三个数各位数字之和是三个连续的正整数，其中有且仅有一个能被 3整除（即“好的”），引理1得证。引理2.在9个连续非负整数 9n,9n 1, 9n 8 （ n是非负整数）中，有且仅有 3个是“好的”。把这3个“好的”非负整数化成三进制，0,1 , 2恰好在这三个三进制数的最后一位各出现一次。证明：由引理1不难得知在9个连续非负整数9n,9n 1, 9n 8 （ n是非负整数）中，有 且仅有3个是“好的”。另一方面，在这三个“好的”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取 0,1 , 2。若它使它们成为“好的”非负整数，则最后一位不相同，引理2得证。将所有“好的”

14、非负整数按从小到大的顺序排成一列，设第2004个“好的”非负整数为m ,根据引理 1,得 2003 3 m 2004 3，即 6009 m 6012。设前m个“好的”正整数之和为Sm ,由于前2003个“好的”正整数之和等于前 2004个“好的”非负整数之和。因此 S2003（0 122003） 3 20046023022 ；又因为(6013)10 (22020201)3和(6015)10(22020210) 3都是“好的”正整数。因此前2005年“好的”正整数之和是：S2005 S20036013 60156035050。第二节整数的性质及其应用(1)基础知识整数的性质有很多， 这里我们着重

15、讨论整数的整除性、整数的奇偶性，质数与合数、完全平方数及整数的尾数等几个方面的应用。1. 整除的概念及其性质在高中数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。定义：设a,b是给定的数，b 0，若存在整数c，使得a be则称b整除a，记作b| a ,并称b是a的一个约数(因子)，称a是b的一个倍数，如果不存在上述e，则称b不能整除a 记作b a。由整除的定义，容易推出以下性质：(1)若b | e且e | a，则b |a(传递性质)；若b|a且b|e，则b|(a e)即为某一整数倍数的整数之集关于加、减运算封闭。若反复运用这一性质，易知 b|a及b|e，则对于任意的

16、整数 u,v有b |(au ev)。更一般，若naa?, ,an都是b的倍数，则b|(q a?a“)。或着a |bi ,则a | q 0其中i 1Ci Z,i 1,2, ,n;若b | a，则或者a 0 ,或者| a | | b |,因此若b | a且a | b，则a b ；(4) a,b互质，若 a | e,b | e ,则 ab | e ;(5) p是质数，若p|aQ2an，则p能整除aa2, , a.中的某一个；特别地，若p是质数，若p | an，则p |a ;(6) (带余除法)设a,b为整数，b 0,则存在整数 q和r，使得a bq r，其中0 r b，并且q和r由上述条件唯一确定；

17、整数 q被称为a被b除得的(不完全)商，数r 称为a被b除得的余数。注意：r共有b种可能的取值：0,1,b 1。若r 0 ,即为 a被b整除的情形；易知，带余除法中的商实际上为a (不超过-的最大整数)，而带余除法的核心是关bb于余数r的不等式：0 r b。证明b |a的基本手法是将a分解为b与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生，下面两个分解式在这类论证中应用很多,见例1、例 2。若n是正整数，则xnny(x y)(xn 1 xn2yn 2n 1 xyy )；若n是正奇数，则xnny(x y)(xn 1 xn2yxyy )；(在上式中用y代y

18、)nm(7) 如果在等式ah中取去某一项外，其余各项均为c的倍数，则这一项也是 c的i 1 k 1倍数；(8) n个连续整数中，有且只有一个是n的倍数；(9) 任何n个连续的整数之积一定是 n!的倍数，特别地，三个连续的正整数之积能被6整除；2. 奇数、偶数有如下性质 ：(1) 奇数奇数=偶数，偶数偶数=偶数，奇数偶数=奇数，偶数偶数=偶数，奇数 偶数=偶数，奇数 奇数=奇数；即任意多个偶数的和、 差、积仍为偶数，奇数个奇数的和、 差仍为奇数，偶数个奇数的和、差为偶数，奇数与偶数的和为奇数，和为偶数；(2) 奇数的平方都可以表示成 8m 1的形式，偶数的平方可以表示为8m或8m 4的形式；(3

19、) 任何一个正整数n，都可以写成n 2ml的形式，其中m为负整数，I为奇数。(4) 若有限个整数之积为奇数，则其中每个整数都是奇数；若有限个整数之积为偶数，则这些整数中至少有一个是偶数；两个整数的和与差具有相同的奇偶性；偶数的平方根若是整数，它必为偶数。3 完全平方数及其性质能表示为某整数的平方的数称为完全平方数，简称平方数。平方数有以下性质与结论：(1)平方数的个位数字只可能是0,1, 4,5, 6,9 ；(2 )偶数的平方数是4的倍数，奇数的平方数被 8除余1，即任何平方数被4除的余数 只有可能是0或1；(3 )奇数平方的十位数字是偶数；(4) 十位数字是奇数的平方数的个位数一定是6；(5

20、) 不能被3整除的数的平方被 3除余1，能被3整数的数的平方能被 3整除。因而， 平方数被9也合乎的余数为0,1 ,4,7,且此平方数的各位数字的和被9除的余数也只能是 0,1, 4,7；(6 )平方数的约数的个数为奇数；(7) 任何四个连续整数的乘积加1,必定是一个平方数。(8) 设正整数a,b之积是一个正整数的 k次方幕(k 2)，若(a,b )= 1，则a,b都是整数的k次方幕。一般地，设正整数a,b, ,c之积是一个正整数的 k次方幕(k 2), 若a, b, , c两两互素，则 a,b, ,c都是正整数的k次方幕。4整数的尾数及其性质整数a的个位数也称为整数 a的尾数，并记为 G(a

21、)。G(a)也称为尾数函数，尾数函数 具有以下性质：(1)G(G(a) G(a) ；(2)G(ai a2a.) = GG(aJ G(a2)G(an)；(3 ) G0 a2a.) GG(q) G®)G(a.) ; ( 4 ) G(10a) 0 ；G(10a b) G(b)；(5)若 a b 10c，则 G(a) G(b) ； (6) G(a4k) G(a4), a, k N ;(7) G(a4k r) G(ar),k0,0 r 4, a,k,r N ;G (a),当为奇数，b2是偶数b2 bn(8) G(ab1)G(a4),当g为偶数，b?为奇数或 bb2同时为偶数时G (a b1 )

22、,当b1, b2同为奇数时5 整数整除性的一些数码特征(即常见结论)(1) 若一个整数的未位数字能被 2 (或5)整除，则这个数能被 2 (或5)整除，否则不能；(2) 一个整数的数码之和能被 3 (或9)整除，则这个数能被 3 (或9)整除，否则不能；(3) 若一个整数的未两位数字能被4 (或25)整除，则这个数能被 4 (或25)整除，否则 不能；(4) 若一个整数的未三位数字能被8 (或125)整除，则这个数能被 8 (或125)整除，否则 不能；(5) 若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被 11整除，否则不能。6 .质数与合数及其性质1.正整数分

23、为三类：(1)单位数1 ； (2)质数(素数)：一个大于1的正整数，如果它 的因数只有1和它本身，则称为质(素)数；(3)如果一个自然数包含有大于 1而小于其本 身的因子，则称这个自然数为合数。2 有关质(素)数的一些性质(1 )若a乙a 1，则a的除1以外的最小正因数 q是一个质(素)数。如果q a，则q . a ；(2) 若p是质(素)数，a为任一整数，则必有 p | a或(a, p) = 1 ；(3) 设aa, ,4为n个整数，p为质(素)数，且p|a£2 a.,则p必整除某个ai (1 i n)；(4) (算术基本定理) 任何一个大于1的正整数a ,能唯一地表示成质(素)因数

24、的乘积(不 计较因数的排列顺序)；(5) 任何大于1的整数a能唯一地写成a pfp；2pk,i 1,2, ,k 的形式，其中Pi为质(素)数(pi pj(i j)。上式叫做整数a的标准分解式;(6)若a的标准分解式为，a的正因数的个数记为 f(a)，则f(a) (a 1)(a2 1) (ak 1)。典例分析例1.证明：1001被1001整除。2000 个 0证明：10 01102001 1(103)667 1 (103 1)(103)666 (103)665103 12000 个 0所以 103 1( 1001)整除 1001。2000个 0例2对正整数n，记S(n)为n的十进制表示中数码之和

25、。证明：9|n的充要条件是9 | S( n)。证明：设n比忖 印10a0(这里0 ai 9，且ak 0)，则S(n) a0 a1an,于是有 n S(n) ak (10k 1)ai (10 1)对于1 i k，知9|(10i 1)，故式右端k个加项中的每一个都是9的倍数，从而由整除的性质可知它们的和也能被9整除，即9|(n S(n)。由此可易推出结论的两个方面。例3设k 1是一个奇数，证明 L对于任意正整数n，数1k 2knk不能被n 2整除。证明：n 1时，结论显然成立。设 n 2,记所说的和为 A，则：2A 2(2k nk)(3k (n 1)k) (nk 2k)。由k是正奇数，从而结于每一

26、个i 2，数ik (n 2 i)k被i (n 2 i) n 2整除，故2A被n 2除得余数为2,从而A不可能被n 2整除(注意n 2 2)。例4设m,n是正整数，m 2，证明：(2m 1)( 2n 1 )。证明：首先，当n m时，易知结论成立。事实上，m n时，结论平凡；当n m时，结果可由2n 12m 112m 1推出来(注意m 2)。最后，n m的情形可化为上述特殊情形：由带余除法n mp r ,0 r m而q 0,由于 2n1 (2mq1)2r2r1，从而由若 n 是正整数，则xnyn(xy)(xn1xn2yx2yn1)知(2m 1) |(2mq 1);而0 r m，故由上面证明了的结论

27、知 (2m 1) (2r 1)(注意 r 0时结论平凡)，从而当n m时，也有(2m 1 * 2n 1 )。这就证明了本题的结论。例5设正整数a,b,c,d满足ab cd，证明：a b c d不是质(素)数。a d m» ,a证法一：由ab cd，可设其中（m, n） 1。由一c b nc分母约去了某个正整数 u后得既约分数 m，因此，a mu,cnma意味着有理数一 nc的分子、同理，存在正整数 v使得b nv, d mv因此，a b c d = （m n）（u v）是两个大于1的整数之积,nu从而不是素数。注：若正整数a,b,c,d适合ab cd，则a,b,c,d可分解为及的形式

28、,这一结果在某些问题的解决中很有作用。证法二：由ab因为a b ccdcd，得b ，因此a b c dad是整数，故（a c）（a d）也是整数。(a c)(a d)若它是一个素数,设为p，则由(a c)(a d) ap可见p整除（ac)(ad），从而素数p整除a c或。不妨设a cp，结合推出a d a，而这是不可能的（因为1 )。例6.求出有序整数对（m,n）的个数，其中1 m 99,21 n 99, (m n)3m是完全平方数。解：由于1 m 99,（1999年美国数学邀请赛试题）1 n 99可得:(m n) 3m n v (m n) 4(m n)4 (m n 2)2。又(m n)2(m

29、 n)23m n，于是（mn)2 (m n)23m n(m n 2)2若（m n）2 3m n是完全平方数，则必有(m n)2 3mn = (mn 1)2。然而(m n) 3m n = (m n 1) nm 1,于是必有此时n 2,3,99 , m 1,2,98。所以所求的有序整数对（m, n)共有98对:(m,n)(1,2),(2,3),(3,4),(98,99)。例7.证明：若正整数a,b满足2a2 a 3b2b，则a b和2a 2b 1都是完全平方数。（2006年山东省第二届夏令营试题）证法一：已知关系式即为 2a2 a 3b2 b2(a2 b2) (a b) b2(a b) ( 2a

30、2b 1 )= b2若a b 0 (或者说a, b中有一个为0时)，结论显然。不妨设 a b且 ab 0，令(a,b) d，则 a aq,b dd , (ai,bi)122从而a b = (a1 b1 )d，将其代入得 2a1 d a1b1 3Q d 2因为 d |2a1 d，所以 d | (a1 d)，从而 d a1 d ；而式又可写成g b1) (2a1 2b1 1) dd2;因为(a,b) d且(a-bj 1，所以 db)1 bj所以(a1 bi) | d，从而 a1 b1 d。所以d a1 b1，所以a b = bjd d2，从而a b为完全平方数。b2b所以2a 2b 1 务 (b)

31、2也是完全平方数。d d证法二：已知关系式即为2a2 a 3b2 b2 2 22(a b ) (a b) b2(a b) ( 2a 2b 1 )= b论证的关键是证明正整数a b与2a 2b 1互素。(a b , 2a 2b 1)。若 d1，则d有素因子p，从而由知p | b2。因为p是2b 1得p| 1，这是不可能的。素数，故p | b，结合p | (a b)知p | a，从而由p | 2a故d 1,从而由推知正整数 a b与2a 2b 1都是完全平方数。例8.证明不存在正整数 n，使2n2+ 1, 3n2+1, 6n2+ 1都是完全平方数。证明：假设存在这样的正整数n，使2n2+1, 3n

32、2+1 , 6n2+1都是完全平方数，那么(2n 2+1) (3n2+1) (6n2+1 )也必定是完全平方数。而(2n2+ 1) (3n2+ 1) (6n2+1 )= 36n6+36 n4+11n2+1 ;(6n33n)236n6+36n4+9n2; (6n3 3n 1)236n6+36n4+12n3+9n2+6n+1;所以(6n33n)2(2n2+ 1) (3n2+ 1) (6n2+1) v (6n33n 1)2 与(2n2+ 1) (3n2+1) (6n2+ 1)为完全平方数矛盾。例9.数列仁的通项公式为f记§ 謠+仁，求所有的正整数n，使得§能被8整除.(2005年

33、上海竞赛试题)解：记 -Sn 21Sn5 i1"5注意到3Sn1Sncn1ncni 01.5 icnii 0ncn03；52175n.52n11，可得3. 53 ：. 5°3、5 n2 2 2因此，Sn+2除以8的余数，完全由 Sn+1、Sn除以8的余数确定*SC；f1,S2c2f1C；f23，故由(*)式可以算出Sn各项除以8的余数依次是1,3,0,5, 7,0, 1,3,，它是一个以6为周期的数列，从而 8 Sn3n故当且仅当3n时，8 &练习题1证明：如果p和p 2都是大于3的素数，则6是p 1的因子。证明：因为p是奇数，所以2是p 1的因子。又因为p , p

34、 1 , p 2除以3的余数各不相同，而p与p2都不能被3整数。于是6是p 1的因子。2n2m2设 m n 0 ,证明：(221) |(221);mn 1n 1 m n 1n 1n 1m解：由 221(221)(22 )2221，故(221) I ( 221 )。n 1nnnn 1又因为221(221) (221)，从而(221) I (221)，于是由整除的性质知2n2m(221) | (221)。3.证明：对于任意正整数n，数1200522005n2005不能被n 2整除。因为若n是正整数，则xnny(xn 1ny)(xx2ynxy2ny1);若n是正奇数，则xnyn(xy)(xn1n 2

35、x yn 2xyn 1y);故 n 2 1 22005n2005 ； n2 I320052005(n 1)，-，n2I n200522005所以 n 2 1 2 ( 220052005、 n又因为n 232，所以n2 2，所以n 22 ( 220052005 n)+ 2即(n 2 ) 2 ( 12005 22005n2005）命题得证。4.已知n为正奇数，求证：60| 6n3n2n1 o证明：因为若n是正整数，则xnny(x y)(xn1n 2x ynxy2ny若n是正奇数，则xnny(x y)(xn 1n 2x yn 2xyn 1)y )；所以3|6n3n，3|2n1，从而3|6n3n2n

36、1 ；4 |6n2n， 4|3n1，从而4| 6n3n2n 1 ；5|6n1， 5|3n2n，从而 5|6n3n2n 1 ;又(3,4,5)1 且 3 4 560，所以 60 |6n3n2n 15.设a、b、c为满足不等式1 v av bv c的整数，且(ab-1 ) ( bc-1 ) ( ca-1 )能被abc整除，求所有可能数组(a, b, c) .(1989年上海竞赛试题)解'/( ab-1 ) ( bc-1 )( ca-1 )2 2 2=a b c -abc (a+b+c) +ab+ac+bc-1，/ abc| ( ab-1 )( bc-1 )( ca-1 ).存在正整数 k,

37、使ab+ac+bc-仁kabc,丄十1+1丄丄十丄十13k=o D 亡 v必c v d 3 cv 盘 v2k=1.111111147十十 十十=若a>3,此时仁.-<1 一二矛盾.已知a> 1.只有 a=2.221224_ + _ _ 十 _ =.当a=2时，代入中得 2b+2c-仁be，即 1=< - 0< b < 4,知b=3,从而易得 c=5.说明：在此例中通过对因数k的范围讨论，从而逐步确定 a、b、c是一项重要解题技巧.第三节整数的性质及其应用（2）基础知识最大公约数与最小公倍数是数论中的一个重要的概念，这里我们主要讨论两个整数互素、最大公约数、最

38、小公倍数等基本概念与性质。定义1.（最大公约数）设a,b不全为零，同时整除 a,b的整数（如 1）称为它们的公约数。 因为a,b不全为零，故a,b只有有限多个，我们将其中最大一个称为 a,b的最大公约数，用 符号（a,b）表示。显然，最大公约数是一个正整数。当（a,b ）= 1 （即a,b的公约数只有1 ）时，我们称a与b互素（互质）。这是数论中的非常重要的一个概念。同样，如果对于多个（不全为零）的整数 a,b, ,c，可类似地定义它们的最大公约数（a,b, ,c）。若（a,b, ,c ） = 1,则称a,b, , c互素。请注意，此时不能推出a,b, ,c 两两互素；但反过来，若（ a,b,

39、 ,c ）两两互素，则显然有（a,b, ,c ）= 1。由最大公约数的定义，我们不难得出最大公约数的一些简单性质：例如任意改变a,b的符号，不改变（a,b ）的值，即（a, b） （a,b） ； （ a,b）可以交换，（a,b ） = （ b, a ）； （a, b）作为b的函数，以a为周期，即对于任意的实数 x，有（a,b ax ） = （ a, b）等等。为了更详细地介绍最大公约数，我们给出一些常用的一些性质：（1 ）设a,b是不全为0的整数，则存在整数 x, y，使得ax by （a, b）；（2）（裴蜀定理）两个整数 a,b互素的充要条件是存在整数x, y，使得ax by 1 ；事实上

40、，条件的必要性是性质（1）的一个特例。反过来，若有 x, y使等式成立，不妨设（a,b） d，则 d | a, d | b，故 d | ax 及 d | by，于是 d |（ax by），即 d |1，从而 d 1。(3) 若m | a,m| b，则m| (a,b)，即a,b的任何一个公约数都是它们的最大公约数的约数；(4) 若 m 0，则(ma, mb) m(a,b)；(5) 若(a,b) d，则 a，-1，因此两个不互素的整数，可以自然地产生一对互素的d d整数；(6) 若(a,m)1, (b,m)1，则(ab,m) 1，也就是说，与一个固定整数互素的整数集关于乘法圭寸闭。并由此可以推出：

41、若(a,b) 1，对于 k 0有(ak ,b) 1，进而有对 l 0有(ak,b')1。(7) 设 b | ac，若(b,c)1，则 b | a ;(8) 设正整数a,b之积是一个正整数的 k次方幕(k 2)，若(a,b )= 1，则a,b都是整 数的k次方幕。一般地，设正整数 a,b, ,c之积是一个正整数的 k次方幕(k 2)，若 a,b, ,c两两互素，则a,b, ,c都是正整数的k次方幕。定义2.设a,b是两个非零整数，一个同时为a,b倍数的数称为它们的公倍数，a,b的公倍数有无穷多个，这其中最小的一个称为a,b的最小公倍数，记作a,b，对于多个非零实数a,b, , c ,可类

42、似地定义它们的最小公倍数a,b, , c 。最小公倍数主要有以下几条性质：(1) a与b的任一公倍数都是 a,b的倍数，对于多于两个数的情形，类似结论也成立；(2) 两个整数a,b的最大公约数与最小公倍满足：(a,b)a,b | ab | (但请注意，这只限于两个整数的情形，对于多于两个整数的情形，类似结论不成立)；(3) 若 a,b, ,c两两互素，则 a,b, ,c=丨 a,b, ,c I ；(4) 若 a | d ,b | d, ,c | d，且 a, b, , c两两互素，则 a, b, ,c I d。典例分析例1.设x,y是正整数，x y且x y 667，它们的最小公倍数是最大公约数

43、的120倍, 求 x, y。解：设（x, y） d，则 x md, y nd，其中（m,n） 1 且 m n ,于是x, y mnd。所以md nd 667120 即 d门及(2)可得：(m n)d 23 29 mn231 m 2120； n 604030246 m20; n8 m 1015; n 12°由(1)可知只能取524；815；从而d23或29,故x115, y552 或 x232, y435。例2设证明：设(m,n) d，则 m m1d , n n1d，其中,nj1。于是，已知条件转化为2 2mE1 | (m1n1 )，故更有 m1 | (m1ni )，从而转化为 mi|

44、 n，但是(m1,山)1，故2 2(mn1 )1，结合g | m ,知必有m11，同时n11，因此m例3.设正整数a,b,c的最大公约数是c,证明a b是一个完全平方数。证明：设(a,b) d，则 a aq , bbid，其中力)1，由于(a,b,c)1，故(b,c)1,现在问题中的等式可以转化为da1b1ca1 cb1由此可见a1整除cb1。因为，)1，故a11 c，同样可得b1 | c，再由(a1,4) 1便可以推出a1b1 | c。设ca1b1k，其中k是一个正整数。一方面，显然k整除c；另一方面，结m, n 0 , mn | (m2 n2)，则 m合式，得 d k(a1 b1)，故 k

45、 | d，从而 k | (c,d)，但(c, d) 1，故 k 1。因此，da1 b1，故a b d© bj d2，这样就证明了 a b是一个完全平方数。例4. a,b都是正整数，是否存在整数p,q使得对任意的正整数n ,p na与q nb互质？解：令L a,b, r L,s L，则(r,s) 1，于是存在整数x, y使得rx sy 1 ,a b令 p x,q y，则对任意的正整数 n，设 dn (p naq nb),有dn| (r(p na) s(q nb) 即 dn|(rp sq n(ra sb)，而 rp sq rx sy 1, ra L sb，所以 dn 11 dn 1 ,

46、即对任意的正整数 n ,( p na , q nb ) = 1。 例5.已知f(x)x2002 x2001 1，证明：对于任意的正整数 m，都有m, f (m), f( f (m), f (f (f (m), 两两互素。(2002年克罗地亚竞赛试题)证明：设Pn(x) f (f (f (x)(其中f出现n次)。由f(0)1, f (1)1，故对于n N有Pn(0) 1，则Pk(x)是含有0次项Pk(O) 1的多项式。因此，Pn(m)除以m 1 的余数为1。设整数d 1可整除pk(m)和pk|(m)，又pk|(m) = pl(pk(m)，则当p(pk (m) 除以pk(m)时余数为1，即pk l

47、(m) = Q pk(m) + 1。所以d |1，矛盾！从而可知 m, f (m), f (f(m), f (f (f (m),两两互素。1-是一个整数。3例6.求出所有的正整数对(m, n)，使得 mn 1(2006年山东省第二届夏令营试题)解：由于(m3,mn 1)1 且 mn 1|n3 1 mn1| m3( n3 1)mn 11 mm31mn 1|m31,所以m,n是对称的。不妨设当m n时,n2 n 11 n 1n 12，从而m当m n时,1时,则有m 112，所以m2时,由于n1是一个整数,1mn从而 k*3N使得n1 (kn1)(mn 1)即kn 1mnn31n211，所以n 1k

48、n又由于nN，所以以n31 (n 1)(mn 1)mnn mn2nm n 1所以m 5 ；综上知所有的(m,n)%( 2,2),(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).例7.已知a, b, m, n N ，且(a,b)1, a 2，试问an bn|am bm的充要条件是n | m吗?(2006年山东省第二届夏令营试题)分析：因为ak bkk n nn、a (a b )nk nkb (abn)，所以anbn|akbkn abn|k nk na b ；又arrr nnb a (abn) bn(arnbr n)，所以nna b|arbrn ab

49、n | ar nbr n ；令mnq r(0 rn)，则有an bn|anq rbnq ranbn|a(q1)n rb(q1)n rann(q 2)nb | ar b(q 2)n rn abn|ar(1)qbr又因为n r，所以ar ( 1)qbr an bn从而上式r 0且q为奇数，即an bn|am bm的充要条件是n| m且m为奇数。n323例8我们知道219有1个质因子，且3 |21 ；2邸1 513 33 19有2个质因子，且33|23' 1如此下去，我们可以猜想：k N*, 23' 1至少有k个质因子，且3k 11 23' 1。试证明之。(2006年山东省第

50、二届夏令营试题)3kk 1证明：令ak = 21，则ak = 3 bk，即要证bk是整数且有k 1个质因子。下用数学归纳法证明bk是整数。k 1时，结论显然；假设n k时，成立；当 n k + 1 时，因为 ak 1(ak 1)3+ 仁 ak3 3ak2+ 3 ak ；因为3k 1 | ak，所以3k 2 | ak 1，即bk 1是整数。下证bk 1至少有k个质因子。ak 13 bk 1 = ak3 3ak2 + 3 ak = (3 bk)3 3(3 bk)2+ 3(3 bk).因为 bk 1 = bk(32k 1b23k 1bk 1),令 Ck 32k 1 b23k1bk 1，则 bk 1

51、= bk Ck由于(Ck ,3)=1，所以(Ck,bk)=1，从而Ck必有异于bk质因子的质因子，所以bk 1至少有k个质因子。证毕！练习1若 n N,m是奇数，则(2m 1,2n 1)1。分析：要证明2m 1与2n 1互质,我们只需要证明它们的公因子为1即可，但是这对于 m, n不好处理，由m为奇数这一条件，我们可以想到 2m |2mn 1从而找到思路。证明：由于m为奇数，故2n 1|2mn 1，又2m 1|2mn1，从而(2m 1，2n 1)mnmnmnmnmnmn(21, 21)，而(21, 21 ) = ( 21,2)= 1,故(21,21)1。2. 若 17|(2a+3b),试证：17|(9a+5b).证明：注意到 2(9a+5b)=9(2a+3b) - 17b,于是 17|2(9a+5b).但是(17,2)=1,即得 17|(9a+5b).3. 设n,a是正整数，若n a不是整数，则必为无理数。证明：设n. a是非整数的有理数，则可设n ab/.VnCn。因为（b,c）1bnc故可知(bn,cn) 1。但bn 1，因而bn |cn。这与 a是整数矛盾！证毕。bn4. 设a,b是不全为0的整数，一切形如