基础数论问题讲稿---陶平生

1、基础数论问题A讲稿陶平生【基本问题】整数与整除，最大公约数与最小公倍数，辗转相除法，裴蜀等式，质数与 合数，唯一分解定理，高斯函数，二进制，不定方程，同余，平方数，有理数与无理数；例1、一本书共有61页，顺次编号为1,2,L ,61 ,某人在将这些数相加时，有两个两位数页码都错把个位数与十位数弄反了(即：形如茄的两位数被当成了两位数 ba ),结果得到的总和是2008,那么，书上这两个两位数页码之和的最大值是多少？答案：68.解：1 2 L 61 1891, 2008 1891 117,由于形如0b的页码被当成ba后，加得的和数将相差9 a b ,因为a, b只能在1,2,L ,9中取值，a

2、b 8,得9a b 72, 由于117 72 45 63 54 ,设弄错的两数是 而和Cd,若9 a b 72,9 c d 45, 只有ab 19,而Cd可以取16, 27,38, 49;这时ab Cd的最大值是68;若9 a b 63, 9c d 54,则 而 可以取18,29,而Cd可以取17,28,39, ab Cd的最大值也是68.例2、设k为正整数，证明：(10)、如果k是两个连续正整数的乘积，那么 25k 6也是两个连续正整数的乘积； (2°)、如果25k 6是两个连续正整数的乘积，那么 k也是两个连续正整数的乘积.证明：(10)、如果k是两个连续正整数的乘积，设 k n

3、(n 1),其中n为正整数，则 _ _- _225k 6 25nm 1) 6 25n 25n 6 (5n 2)(5n 3)为两个连续正整数的乘积；(2O)、如果25k 6是两个连续正整数的乘积，设 25k 6 m(m 1),其中m为正整数,则 100k 25 4m2 4m 1 (2m 1)2 于是2m 1是5的倍数，且2m是奇数；设 组 2n 1,由得，5524k 12m-(2n 1)2 因此，4k (2n 1)2 1 2n (2n 2),即k n(n 1),它是两个连续正整数的乘积.141800例3、已知一个角，其大小为180-,其中nn为不能被3整除的正整数;证明：这个角 可以用欧几里得作

4、图工具(圆规与直尺)三等分.证：因为正整数n不能被3整除，所以可写成:180° , 180° 180°，如果n 3k 1,则有k (n3n3n180018001800小如果n 3k 1 ,则有k (3n33nn 3k 1或n 3k 1, k为正整数;3k) 180-,即 600 k ；3n3n) 180-,即 k600 一.3n3因为 为给定的角，所以k可用尺规作出，而 600角也可用尺规作出，所以 一可以作出.3例4、不能写成两个奇合数之和的最大偶数是多少？解：因为任一偶数总能表成 6M,6 M 2,6 M 4这三情形之一;由于对每个正整数 n , 6(n 2)

5、 18,而6(n 2) 9 3(2n 1)为两个奇合数之和，所以凡是不小于18的这种6M形状的偶数皆可写成两个奇合数之和；又对每个正整数 n , 6(n 6) 2 44 ,而6(n 6) 2 35 3(2n 1)为两个奇合数之和，故不小于 44的这种6M 2形状的偶数皆可写成两个奇合数之和；对每个正整数n , 6(n 4) 4 34 ,而6(n 4) 4 25 3(2n 1)为两个奇合数之和，故不小于34的这种6M 4形状的偶数皆可写成两个奇合数之和；不在上述三种情况之内的最大偶数是38(因40,42,44皆在上述三情况之内，而大于它们的每个偶数适当增加 6的倍数)；再说明，38不能写成两个奇

6、合数之和.因小于38的奇合数是：9,15,21,25,27,33,35 ,这七数中任两个之和(或某个数的两倍)皆不等于38,因此本题答案为 38.例5、如果正整数a可表为：a 2m 3n 5k (m,n, k N),就称a为好数.证明：11存在2012个互开好数 场，a2,L , a2012,满足：二 La a21a20111a2012证：注意到，33 43 5363,因此有111123 153203，显然中所有的分母皆为好数；又由1113332430 4011111113333333202 102 121520据得,11存12313 ,-315333243303403右端五个分母为互异好数;

7、再由1403iiiiii3 3 c33 3 33 3 33 cc34 104 1215201483160318031111111133333333, 如此米续.103123153243303483603803由于任意多个好数之积仍为好数，所以利用叠代、归纳易得，对于每个奇数存在n个互异好数a1,a2,L11,an ,使得可以将101表为：一q1031a11a21， an因此所证的结论成立.例6、是否存在奇数n 3及n个互不相同的质数r, p2 ,L , pn ,使得pipi 1(i 1,2,L ,n,其中 仇1 pc都是完全平方数？请证明你的结论.解：不存在，反证法，假设存在奇数n 3及n个满

8、足要求的互异质数p1, p2,L , pn.若R, p2,L , pn都是奇数，则 pi R 1 ( i 1,2,L , n )都必须是 4的倍数，从而p1，p2,L ,pn除以4的余数是1和3交替出现，这与n是奇数矛盾.若p1，p2,L , pn中有一个等于2 ,不妨设R2 .因为p1p2和pnp1都是完全平方数，且为奇数，所以 p2和pn除以4余3.又由上一段讨论知 p2, p3,L , pn除以4的余数是1和3交替出现，所以n 1是奇数，矛盾!综上所述，不存在奇数 n 3及n个满足要求的质数.例7、设正整数a,b满足：a b 2011,记2011 12011 2 L 2011 aaa20

9、11 1b2011 2 L b2011 bbB的值.解：易知，两个和式的最后一项都是2011,今考虑其它加项，由于 2011是质数,1 a,b 2011 ,所以（a,2011） 1,（b,2011） 1,且（a,b） 1,_一，2011m 2011n ,， 一因此对于满足1 m a,1 n b的整数m,n, 2011m,20Un皆不是整数，且互不相等, a b这是因为，若有 m,n，使2011m 2011n，则m 旦，这与旦为既约分数矛盾！ a b n b b我们将长为1区间集合：M(1,2), (2,3), L ,(2009,2010)中的每个区间都称为“单位区间”，由于竺1,则2011(a

10、 1 2011竺2010,2011 1所以a对于20U baa2011 22011 (a 1),L ,中的任两个分数，属于 M中不同的单位区间,aa2011 2 ,2011 (b 1),L ,也是如此;bb,2011m 2011n再说明，对任何m,n, 1 m a,1 n b, 2011m ,20iU也属于m中不同的单位区间,a b事实上，如果这样的两个分数属于同一个单位区间(k,k 1),则有2011m2011nk 1,kabk 1,即 ak 2011ma(k 1), bk 2011n b(k 1),相加得(a b)k 2011(m n)(a b)(k 1),注意 a b 2011,于是上式

11、成为km n k 1 ,即整数m n介于两个连续整数之间，矛盾!工曰 2011 1 2011 2 ,2011 (a 1) 2011 1 2011 2 ,十走，,L , ; , ; ,La aab b2011 (b 1)b2009个分数，分别属于 M中所有2009个不同区间，每个区间恰含一个上述分数.由于当x (k,k 1)时，有x k ,所以AB (1 2 L2009) 2011 2011 2023067.例8、试确定所有这样的六位数 p ,具有如下性质:(10)、p, 2 P, 3p, 4 P, 5p, 6P 仍是六位数；(2O)、每个六位数的六个数字仍是数p的六个数字(仅排列顺序不同).解

12、：设p abcdef ,并记Ma,b,c,d,e, f ,对任意正整数 n ,用S(n)表示n的数字和，则因S(3p) S(p),而由 33p3 S(3p) 3S(p) 3 p 9 3p 9 S(3p) 9S(p)9 p .再确定集M，首先指出，六个数p, 2P,3p, 4 P,5p, 6 P的首位数字必定互异； 事实上， 假若ip与jp的首位数字相同，其中1 i j 6,则(j i)p的首位数字为0,即(j i)p的位数小于6,但1 j i 5,即(j i)p是p, 2P,3p,4p,5P之中的一个数，据条件，它应当是六位数，矛盾！由于每个首位数字皆属于集M ,故这六个首位数字恰好构成集合M

13、 ,因此p的各位数字互不相同，且不含 0;同理可知，六数的末位数字也各不相同（否则，若有两数ip与jp的末位数字相同，那么其差的末位数字为 0,而（j i ）p是p, 2 P, 3p, 4 p, 5P之中的一个数，矛盾！）因此p的末位数字必是奇数（否则，假若p的末位数字是偶数，则5P的末位数字为0, 矛盾！），并且此末位数字 f 5 （否则导致2 P的末位数字为0,也得矛盾）；又因6P仍是六位数，所以 p的首位数字a 1 （假若p的首位数字a 2,则6P将成 为七位数，与条件矛盾），因为1已被p的首位数字a所占用，所以f 1;于是得到，f 3,7,9 .下面分别讨论.假若f 3,则六数p,2P

14、,3p,4P,5p, 6P的末位数字分别是3,6,9,2,5,8 ,它们皆是 集M中的数，且互不相同，于是 M 3,6,9,2,5,8 ，此六数字也应是 p的六位数字，然 而此时S（p） 33不是9的倍数，矛盾！假若f 9,则六数p, 2P,3p, 4 P, 5p, 6P的末位数字顺次是 9,8,7,6,5,4 ,它们皆是 集M中的数，且互不相同，于是 M 9,8,7,6,5,4 ，此六数字也应是 p的六位数字，然 而此时S（p） 39,也不是9的倍数，矛盾！因此只有f 7,于是六数p, 2 P,3p, 4 P, 5p,6 P的末位数字分别是7,4,1,8,5,2，从 而集 M 7,4,1,8

15、,5,2，前面已得，a 1,f 7 ,所以 p 1bcde7 ；于是 b 2,4,5,8 ;p, 2P,3p,4P,5p, 6P的首位数字应是 M中各数的递增排列，故依次为1,2,4,5,7,8 ;假若b 5 ,则2 P的首位数字将大于 2 ,矛盾！因此b 2,4 ;假若b 2 ,则p 128547 ,这时5P的首位数字6 ,矛盾！于是只有b 4,得到p 14cde7 ；因此e 2,5,8 ;如果e2 ,即p14cd27 ,此时4p的十位（倒数第二位）数字为0 ,而0M；如果e8,即p14cd87,此时3P的十位（倒数第二位）数字为6,而6M;因此只有e 5,进而p 14cd57 ,其中c,d

16、 2,8 ;这时只有p 148257或 p 142857两种情况;假若 p 148257，则 2P 296514 ,而数字 6,9 M ；因此本题的六位数 p只有唯一可能：p 142857 ,容易验证，它满足本题中的条件.例9、设a 1 3 5 L 2013为不大于2013的全体正奇数的乘积， 试求a的末三位数.解：设a的末三位数为b,则a 1000m b,则b为奇数，由于a与1000m皆是125 的倍数，故b也是125的倍数，所以奇数 b属于125,375,625,875四种情形之一.又因8 a b,只需考虑a被8除得的余数，由于a (8 0 1)(8 0 3)(8 0 5)(8 0 7)

17、(8 1 1)(8 1 3)(8 1 5)(8 1 7) L(8 k 1)(8 k 3)(8 k 5)(8 k 7) L (8 251 1)(8 251 3)(8 251 5)而(8 k 1)(8 k 3)(8 k 5)(8 k 7)被8除的余数为1,所以a被8除得的余数，等于(8 251 1)(8 251 3)(8 251 5)被8除得的余数，即为 7,又因为在四数125,375,625,875中被8除余数为7的只有375,所以b 375.此即a的末三位数.例10、设n为正整数，问n2的各位数字之和能否为：(1°)、2013?(2°)、2014?解：由于涉及数字和，故可从

18、分析被9除的余数入手；因为任一正整数的平方被9除的余数，只有0,1,4,7这四种可能；由于2013 6(mod9),所以，任何平方数的各位数字和不可能是2013;而2014 7 (mod9),故有可能存在某个正整数的平方，其各位数字和为2014,为了证实这一说法，我们需要具体找出这样的一个数来；注意2014 9 223 7,我们来证明，对任何自然数 k,存在正整数a,使得a2的各 位数字和恰为9k 7;从简单做起，取特殊的数，逐步观察：k 0时，由于42 16,其数字和为7；.22k 1时，14196,其数字和为9 1 7； k 2时，948836 ,其数字和为9 2 7；2k 3时，9949

19、88036,其数字和为9 3 7；此时，规律已经显现，对于任意的k 2,取 n 10k 6 99L394，则 n2 102k 2 10k 6 36 99L3988q L 036 ,易知 n2 的 k 1k 2k 2各位数字和为9k 7 .若取k 223,则对于n 10223 6, n2的各位数字和恰为2014.下面再解决其余情况的构造：02222(10) 、 n 9时，n2 81 ， n 与 n 2的数字和皆为9； n 99 时，n2 9801 ， n 与 n2的数字和皆为9 2 18；当 n 10k 1 时，n2 102k 2 10k 1 ?L 98QL 01, n与 n2 的数字和皆为 9

20、k;k1 k1022(2 ) 、 n 1 时， n 与 n 的数字和皆为1，当 n 8 时， n 64 ，数字和为9 1 1 ，当 n 91 时，n2 8281 ，其数字和为9 2 1 ；当 n 10k 9 9192L391 时，k2 2kkn2 102k 2 9 10k 81 9 L 9820 L 081 ，其数字和为9k 1 ；k1k1(30) 、 n 2时， n2 4，其数字和为4； n 7时，n2 49 ，其数字和为9 1 4；当 n 97时，n2 9409 ，其数字和为9 2 4；当 n 997时，n2 994009 ，其数字和为 9 3 4；一般地，n 10k 3时， n2 102

21、k 6 10k 9 9L 940 L 09 ，其数字和k1 k1为 9k 4 例 11、将前 300个正整数1,2,3,4, L ,300 顺次在黑板上排成一行，然后划去前两数1,2， 而将这两数的和写在最后面，成为 3,4,5,6, L ,299,300,3 ； 接着， 再划去前两数3,4 ，而将这两数的和写在最后面，成为5,6, L ,299,300,3,7 ；象这样一直进行下去，直到最后黑板上只剩下一个数为止；试求黑板上出现过的所有的数之和(包括每次划去的数在内)解：先考虑特殊情况：如果原先有2n 个数a1, a2 ,L , a2n 每次在前面划去两数，在后面补写其和，当把这2n 个数都

22、划去后，则得到2n 1 个新补写的数，称这样的操作为“一轮变换” ；显然，当一轮变换完成后，所得的2n 1 个新数之和与已划去的原先2n 个数之和相等，仿此再进行第二轮、第三轮变换，每轮变换后所得到的数之和都与原来的数之和相等，当进行了 n轮变换后，黑板上只剩下一个数，则这数就是原先的2n个数之和S,连同每轮划去的数，这时，黑板上出现过的所有的数之和为n 1 S ；再考虑本题情况，由于300不是 2的幂，而30028 44，当划去前88个数，在后面补写出44个数后，黑板上的数成为28个，且其和就是前300个正整数的和S300 .( S300 1 2 L 300 45150) ，按照前面的说法，

23、对这28个数进行8轮变换后，最后得到一个数，于是，黑板上所出现的数的总和(连同最初划去的前88个数)为：S 1 2 L 889 S300 3916 9 45150 410266.例12、九个连续正整数自小到大排成一个数列a, ,a2,L ,a9 ,若a1 a3 a5 a7 a9为一平方数，a2 a4 a6 a8为一立方数，问这九个正整数之和的最小值是多少？解：设这九数为a 4, a3,a2,a1,a,a1,a2, a 3,a 4,则有，5a m2,2 23 m n 一 234a n , S 9a,贝U a ，得 4m 5n542_32_3令 n2n1,m5m1,得 100m140n1,所以5m

24、12n1,再取m12m2, n1 5n2,2_2 3化为2m2 5 n2,取m2 10, n2 2 ,可使左式成立，这时 n 20, m 100 , a 2000,222里数，证明ab土为整数.a b c,3a b (、,3a b)(、3b c)、3b c 3b2 c20 ,于是b c)2 2(ab bc b2)c),S 9a 18000.例13、已知a,b,c为正整数，且/3a b为 ,3b c证：因J3是无理数，则J3b c 0,而3ab bc . 3(b ac)2为有理数，所以 b2 ac 3b2 c2a2 b2 c2 (a b c)2 2(ab bc ac) (a(a b c)2 2b

25、(a c b) (a b c)(a b2.22因此，a一b一- a b c为整数. a b c例14、十二个互不相同的正整数之和为2010,则这些正整数的最大公约数的最大值是.答案：15.解：设最大公约数为 d , 12个数分别为a1d,a2d,L ,a12d ,其中(a1,a2,L ,a12) 1 ,12记S ai ,则2010 Sd,欲使d最大，当使S取最小，由于a1，a2,L ,a12互异，则 i 1S 1 2 L 12 78,因S 2010,但2010 2 3 5 67 ,其大于67的最小正因数是 2 67 134,所以d 15,且d 15可以取到，只需令 乌人 同1,知)(1,2,L

26、 ,11,68) 即可.例15、如果四位数n的四个数位中至多含有两个不同的数码，则称n为“简单四位数”；例如5555和3313等等，那么，简单四位数的个数是 .答案：576.解：如果四位数的四个数码都相同，则这种四位数有9个；如果四位数的四个数码有两个值，首位数a 1,2,L ,9有9种取法，当首位数a填好后，再任取b 0,1,2, L ,9,且b a,选取b的方法有9种；后三个数位中，每一位置都可 填a或b ,但是不能后三位全填 a ,有23 1 7种填法，即，四个数码恰有两个值的情况 有 9 9 7 567 种；因此简单四位数共有9 567 576个. 22例16、满足x 7y 2011的

27、一组正整数(x,y) .答案：(38,9).解：由于2011是4N 3形状的数，所以 y必为奇数，而x为偶数， 设x 2m, y 2n 1,代人得 4m2 28n(n 1) 2004 ,即 m2 7n(n 1) 501 . 而n(n 1)为偶数，则m2为奇数，设 m 2k 1 ,则m2 4k(k 1) 1,由得，k(k 1) 7 n(n 1) 125，则n(n 1)为奇数,且n,n 1中恰有一个是 444的倍数，当n 4r ,为使7 n(n 1) 7r(4r 1)为奇数，且7r(4r 1) 125,只有 4r 1,成为 k(k 1) 35 125,即 k(k 1) 90 ,于是 n 4,k 9

28、, x 38, y 9；若 n 1 4r ,为使 7 n(n 1)7r(4r 1)为奇数，且 7r(4r 1) 125 ,只有 r 1, 4成为k(k 1) 21 125,即k(k 1) 104,它无整解；于是(x,y) (38,9)是唯一解：382 7 92 2011 .(另外，也可由 x为偶数出发，使 2011 x2 2009 (x2 2) 7 287 (x2 2)为7的 倍数，那么x2 2是7的倍数，故x是7k 3形状的偶数，依次取 k 1,3,5,检验相应的 六个数即可.)2011例17、用S（n）表示正整数n的各位数字之和，则 S（n） . n 1答案：28072.解：添加自然数0,

29、这样并不改变问题性质；先考虑由0到999这一千个数，将它们全部用三位数表示，得到集 M 000,001,L ,999 ,易知对于每个a 0,1,L ,9 ,首位为a的“三位数”恰有100个：a00,a0i,L ,a99 ,这样，所有三位数的首位数字和为100 （0 1 L 9） 45 100;再将M中的每个数 航的前两位数字互换，成为 bac,得到的一千个数的集合仍是M ,又将M中的每个数 航的首末两位数字互换，成为 cba ,得到的一千个数的集合也是M ,999999由此知，S（n） S（n） 300 45 .n 1n 0今考虑四位数：在1000,1001,L ,1999中，首位（千位）上，共有一千个1,而在0000,0001,L ,0999中，首位（千位）上，共有一千个0,因此,1999S(n)n 11999S(n) 1000n 09992 S(n)n 01000 600 45 28000；其次，易算出,2011S(n)n 200072。所以,20112011S(n) S(n) 28072 .n 1n 0例18、在前一百个正整数 1,2,L ,100中任取27个不同的数，证明：其中必有两个数 是不互质的.证明：前一百个正整数中，共有 25个质数，它们是：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59