多功能题典 高中数学竞赛-32

14.1.74★★★证明：不存在整数”>1,使川2"-1.

解析假设存在满足的正整数.令〃为这些数开的最小者.根据欧拉定理，我们有

"邛*一1.注意到(2"-1,=取a=〃，b=<p(n),d=(a,b)=(〃，0(〃))，则

又因为〃>1,所以从而d>l,且而42”—1,与〃的定义矛盾.

14.1.75*★★求满足〃|3"+1的所有奇数

解析只有唯一的奇数〃=1满足条件.事实上，假设存在一个奇数〃>1,使得〃w+1.则〃忙-1.与

上题类似，设”为满足〃|9。⑺—1,设d=(〃，夕(n))，则〃印-1.于是d>l(如果d=l,那么〃|8与〃

为大于1的奇数矛盾)，并且与〃的定义矛盾.所以没有大于1的奇数〃，满足(x,y)=l,

且f+y2=z4,那么7|孙.说明条件(x,y)=l是必要的.

解析条件(x,>)=1是必要的.例如(15,20)片1,152+202=54,但73520.如果(x,y)=l,且

X,y,Z是满足V+y2=z4的正整数，那么，由于X、>、z2是一组勾股数，并且(X,y)=1,存在整

数〃?，"，使x=〃「-“2,y=2mn,z2=m2+n2.假设73，，于是7CEn,且7G&.易知一个不被7

整除的整数的平方，被7除，余数只能为1,2或4.z2=/+〃2,而1+2,1+4,2+4不等于1,

2,4,也不能被7整除.于是小，/被7除，余数应该相同，从而7卜=〃--〃2.

14.1.77*★★证明：对于任何一个正整数s,都存在一个正整数〃，使得〃的数字和等于s,且6%.

解析设s为正整数，将s表示成s=2"5九八这里a,夕为非负整数，「不能被2与5整除.根据欧拉

定理，有10""三l(modf).

令"=10"+10M，)+…+10卬⑺)，因为10"”>+10训')+…+10")三s三0(modf)(因为f|s).

且2"5[10"+J所以s|”.另一方面，很显然有"的数字和为s.

14.1.78★★★证明：存在无穷多对正整数x,y,满足x(x+l)b(y+l),

x癌，x+ly,x耨+l,x+ly+1.并求最小的一对(x,y).

解析x=36A+14,y=(12&+5)(184+7),k=0,1,2,…具有题设性质.

事实上，因为x(x+l)=2・3(12Z+5)(18Z+7)=6y,而6|y+l,所以x(x+l)似y+1).因为x为偶数，

y为奇数，所以了母.因为3卜+1,33，，所以x+l团.因为18无+7|x,18k+7|y,所以18A+7西+1,

故x西，+1.最后，因为12大+5|x+l,12Z+5|y,所以12人+5①，+1.故x+1但+1.

容易看出满足要求的x、x+1都不能是质数，由于)，与)，+1互质，x、x+1也不能是质数的嘉.因此x

最小是14.同样，y、y+1也都不能是质数的基.而且)，>14.经检验，满足要求的y最小是20.x=14,

y=20时，x(^+l)=14xl5=2x7x3x5=10x21,整除y(y+1)=20x21.因此最小的一对是(14,20).

14.1.★是否存在能被比二整除且数字和小于根的正整数？

，“个

解析不存在.

r

假设有被M=上」整除且数字和小于〃?的自然数.设其开P=at\0+a2-\0'-'+…是最小的数.若

加个

rrra

r=m-\,贝！]q=〃2=---«r+,•这时p的数字和m.所以rN机.这时p,=p-(10-10-)<p能被M

整除，而且PI=(P-IO')+IOE的数字和不超过"的数字和.这与"的最小性矛盾.

14.1.80★★★设方和〃是自然数.证明：如果对于某些非负整数匕,右，…，kn,数2%+2&+…+2*”被

2"'-1整除，那么机.

解析首先可设匕，网,…，/互不相同(如果有相同的，就加以合并：2"+2*=2"',直至没有相同

的).如果有2&+2毋+…+2%依<%<…<^)被2川-1整除，而"<加，那么设它是这种数开最小的.若

kn^m,则p=2&+2&+…+2%-2*”f(2小-1)=2勺++…+2%+24厂"仍被2'"-1整除，而且项数

Wn<m.这与2&+2&+…+2*"的最少性矛盾.

所以幺W/M-l.但这时由于〃<m，2%+2e+--+2*"<1+2+—・+2"1=2"'—1与2&+2板+・一+2""被

2"'-1整除矛盾.因此必有"一，”.

评注本题与上题类似.只不过将上题的十进制改成了二进制，其他进制下结论也成立.

14.1.81*★★证明：存在一个能被5HM0整除并且数字开没有0的数.

解析数十000的个位数字为5.任取一个51°0°的倍数，设这个倍数的十进制表示开，从右边起数字0第

一次出现在第％位上.将加到这个数上，所得的数仍被驴双整除，并且最末％个数字都不是

零且被5HxM整除的数.由这最末1000位数字组成的数即为所求.

14.1.82★★★证明：对所有满足3WdW2"”的正整数”，〃及任意正整数*有1国'+1.

解析我们证明：若d23,d—+l,则4>2川.

显然4国”+i(当a为奇数时，因为/"三](mod4)),所以d有奇质因子p,且小=-l(modp).设机

为满足""三l(modp)的最小正整数，由/三三(_])\[(modp)知司2川.若加<2e，则

m=2k,k^n.此时1三(/1=/三T(modp),与p为奇质数矛盾.从而加=2向.由费马小定理

a》ml(modp)知,P-1Z2"',更有d》p22用+1>2向.

所以原命题得证.

14.1.83★★★求出所有的整数”>1,使得“1"+2"+….

解析满足条件的〃为所有大于1的奇数.事实上，如果〃为大于1的奇数，那么当女=1,2,…，七1

2

时，有“4"+(”-&)"(因为(M)"=-%"),从而"1"+2"+…+.另一方面，如果〃为偶数，设

2'是能整数〃的2的最高次基，则s为正整数.因为所以，对偶数么,我们有2'k".而对于奇

数%(在1,2,…，中，奇数k共有]个)，根据欧拉定理，有公"'三i(mdo2'),故〃'三l(mod2')

(因为2~|"),从而1"+3"+…(〃-3)"+(〃-1)”三J〃(mod2’).

l"+2"+3"+—+("-l)、1〃(mod2'),故对偶数〃，1"+2"+…+(〃-1)"不被2,整除，更不被〃整除.

14.1.84★★★设〃为大于1的奇数，则对任意的/%,"T+l).①

解析若=则因《机，d4一一+1),故①成立.以下设。7,机)=1.

设〃的标准分解式为〃=P；"p；"…P：，由2C&可设p,-1=2"•§,”>0,2四，i=1,2,s.令

，nj

q=min{叫，m2?},则有〃一1=p；p：…pf-1=0(mod2),故可设〃一1=2吗•〃，w>0.若①

不成立，则m"~]+1=0(mod/i),即m2'+1三0(mod〃)，由于。为奇数，由上式得出m2+1=0(modn),

即/T〃+l三0(mod〃).②

因为(%〃?)=1,所以(丹，〃7)=1.由费马小定理得〃仙T"-1三0(modpj.结合②得2三0(modpj,

与夕/>2矛盾.

/+1

14.1.85*★★求出所有的有序正整数对(,〃，〃)，使得‘士是整数.

inn-1

解析n3+1=n+mn—^mn—1),所以+1即m〃一+机〃.由于〃与如?一1互质，所以

mn-1|/?2+m.由于〃(疗+/?)=+m)+加(团〃-1),所以又有mn-}\nrn.

这样，由〃?、〃的对称性，不妨设在〃=1时，mn-\-m-1|/?5+1=2,从而加二2或3.以下

设〃22.在〃7=〃时，/-1“+1=〃(/一1)+(〃+1),从而鹿=2.

在〃?时，2(—22+m+(加一2)>〃2+〃2,所以由加九一1,2+加得机1=+〃2,

即(瓶_“_1)(〃-1)=2,从而{；：；'；，

本题共有九组解，即(加,")=(2,1),(3,1),(1,2),(1,3),(2,2),(2,5),(3,5),(5,2),(5,3).

14.1.86★★★证明：对任意正整数3(依产“(/)!•

解析对任一质数p,考虑p在化!广"‘与小3)!中的基次.

若〃血，则对任意自然数/,左三厂(modp')，1小r<p'.从而攵3三/(modp').

.k3-r3(k-r)(k2+kr+r2)

.7.▼二----F---

仕-〃)(/+&+[)

2---------------------

P

=伊+攵+])

LPJ

p在卜3)!开的幕指数Z拼》£宁(k2+k+l),后者即p在®广川开的幕指数.

若k=p'h,s?l,p岫,则p在(加广开的骞指数不大于p在(/)!中的幕指数，即

^+力+1W——3,其开s(/7)是也在P进制中的数字和.于是

P-\、/p-\

左3_s(R)_伏_§(%))俏2+左+1)=左3_5(/?3)_伏_s®)x(公+攵+])243_/73+(〃_s(初W+/?+l)_

(k-s(h))(k2+k+\)=(s(h)-\)(k2+k-h2-h)^0,即人二半七若。(公+k+i).这表明p在

俨)!中的事指数不小于。在(&y中的累指数.

14.1.87★★★设x,y是使孙-1被质数1979整除的整数.以(x,y)为坐标的那些点，如果有三点在一

条直线上，求证：这三点开至少有两点，它们的横坐标之差与纵坐标之差都能被1979整除.

解析设三点为(七,%),

满足斗丫=1(mod1979),①

z=1,2,3,并且都在直线以+by=c上，这里〃互质，不妨设1979C&.因为

a(x2-xl)+b(y2-yl)=0,②

所以时乙(%2一％)+匕(%工2/2一七工2>1)=。，利用①得以也仁一嘲+"王一/”〃111。^^7外,即

Xj-x2=0(modl979),③

或oxi/三》(mod1979).④

若③成立，则须入2(%一必)三W一X三0(mod1979),而由①，1979(E;,所以上式导出

y}-y2=0(mod1979),即(X，y)与(々，%)为合乎要求的两点.

若④成立，考虑士若王三七巾。即979),则(苞，到)与优，％)合乎要求・否则有与④类似的同余

式

axxx3=Z?(modl979),⑤

④、⑤相减得

axx(x2-x3)=0(modl979),⑥

由④及1979(&得1979(E/，所以⑥即9-七三°(modl979),这表明(/，%)与(七，％)合乎要求.

14.1.88*★★⑴是否存在14个连续正整数，其中每一个数均至少可被一个不大于11的质数整数？

⑵是否存在21个连续正整数，其中每一个数均至少可被一个不大于13的质数整除？

解析⑴14个连续正整数开，有7个奇数(不妨设为)n,〃+2,〃+4,〃+6,〃+8,n+10,〃+12不

能被2整除.这7个奇数开，至多1个被11整除，1个被7整除，2个被5整除，3个被3整除.如果

被3整除的数少于3个或被5整除的数少于2个，那么这7个奇数开被3,5,7,11整除的数不足7

个.如果恰有3个数被3整除，2个数被5整除，那么，被3整除的数必须是“，〃+2,〃+12；被5

整除的两个数必为〃与"+10或〃+2与"+12,这时必有一个数即"或“+12同时被3,5整除.所以这7

个奇数开被3,5,7,11整除的数仍不足7个.不管怎样，这14个连续正整数开必有1个不被2,3,

5,7,11中任一个整除.故答案为不存在.

⑵存在.21个连续整数个0,-9,…，-1,0,1,2,…，10中除去±1外,都被2,3,5,7之一整除.根

据中国剩余定理，满足N=0(mod210),Nml(modll),N=-l(modl3)的整数N存在.于是21个连

续整数N-10,N-9,•••,N,N+1,…，N+10满足条件.

14」.89***求所有的正整数对(“，3，使得

是正整数.

解析一b=\,①成为色，所以a-2机，机为正整数.

2

人=2a时，①显然为正整数.

设6/2。并且b>l.这时①的分母(2。-6)从+1为正整数，所以2a-b为正整数.设2a=6+f,f为正

整数，则

是4的倍数.所以4(疗+1)W(6+r)2W2(/+巧，

从而2tbz<b2+t2,b2<t.

b2(b+r)2-t(tb2+l)~2b(tb2+i)=b4-*t-2b③

被步+1整除，而-t-2b<b'<b2f,f+2b-b&所以必有Z?T-2b=0,

即r=/-26,“比心.将上代入①，得

2

“2_从(/_])2J

2ab2-b3+l~4(b6-2b3+1)-4'

所以b为偶数a=8加4-加.

本题的解为(a,b)=(2m,1),(m,2m),(8???4-m,2〃?)其中加为正整数.

解析二设a1=k(lab2-by+\),N,贝!!(a-kh2]"=k2h4-kh,+k,而h>\时，

(如—-kb3-kb2+^[b+\^<k2bA-kby+k-{a-kb2>f~\b+^=

二匕4_加+妨2+；e_])2.〃为奇数时，(加与(加一为连续平方数，其中不可

能再有平方数.所以6为偶数2,“，而且公/-加+%=("加『=(加-?],从而

a=gb或a=2kb2-,k=.(a,/?)=(〃?，2m),(8m4-〃z,2«?),经检验，它们合乎条件.

又6=1时，有解(a,h)=(2nz,1).

评注前一种解法,要点在使②的分子减少为③.在证明一个分数的形式为整数时，这是常用的方法.第

二种解法，要点在配方，相当于用二次多项式的判别法.得出的解应当检验(第一种解法不需要检验.因

为已经是代入①式得出的结果了).

14.1.90*★★★设p>3是一个质数，且设

则p牛-s.

解析5=I2+22+324—+〃2=，"(〃+1)(2〃+1),在〃=35'时，s被p整除.对每个1Wj二।存

在/满足广产三l(modp),『互不同余，而且1W/W,.所以

1/1+，1+…+＞「万+1三―力!三一£/三0(mod〃)，

2-(p-2)p-1£+1MJM

22

即一/——-+—/——-+•••+---J----=±的分子x三0(mod〃)(y与x互质).所以

l(p-l)2(p-2)pTP+1yv7

-12~

1+—4---1=p--H---------H---1----------=—的分子px被p?整除.而由①，

2p-\l(p-l)2-(p-2)P-1P+1y

IFT~)

i+_L+...+—L=m,左边的小最公分母不被〃整除，所以右边的分子被p整除.==px,

2p-\psp

即一s被/整除.

14.1.91*★★★求出(并加以证明)所有大于1的整数〃，使2〃一+以1为整数.

n

解析显然〃为奇数.设〃为〃的最小质因数，则

2"=-l(modp).①

设。为满足2"三-1(modp)的小最正整数，令n=ka+r,OWr<a,则

2“三2加”三(一炉・2'(modp),②

若女为偶数，则由①、②得2「三-l(modp),由。的最小性知，r=0.若左为奇数，则由①、②得

2「三l(modp),从而2"~"三-l(modp),而0<。一尸由〃的最小性，仍有厂=0.总之，a\n.

由费马小定理，2，T三l(mod〃).若。>〃一1,则〃一(〃一1)<〃，并且2D三一l(modp),与Q的最

小性矛盾，因此。<〃.由p的最小性及。卜7得〃=1,即0三一l(mod〃)，从而〃=3.

令〃=3"d,(d,3)=1,若222,则2"+1=(3-l)"+l=3n-X(-l)AC：3S③

ft=2

由于〃！中的3的幕指数为‘卜样+…<《+[+…=(所以C：中3的幕指数,J，③式右边

£_&+%+]k+-+l

和号中，各项分别被32=32整除(力22),而3〃恰被整除，从而

2"+1=3*+|-d',(3,d')=l.由于”2=32*./,”2但"+],矛盾！

因此〃=3d,(3,d)=l.若d>l,令q为4的最小质因数，则2"三-l(modg),令/为使2,三-l(modq)

的最小的正整数，与前面类似，可得力〃，再由q的最小性及j〈q-l得_/=1,3.从而引3,或q",

均与(3,4)=1矛盾.因而d=l,n—3.

14.1.92*★★★今有26个非零数字写成一行.证明：可将这一行分成若干段，使得各段数字所成自然

数相加所得的和被13整除.

解析利用Cauchy-Davenport-Chowla定理：若A={4，％,是模〃的r个不同剩余类的集合，

8={4=0,b2,■■■,bs}是模〃的s个不同剩余类的集合，且佃，n)=l,j=2,s.则上4+与}中至

少有min(〃，r+s-l)个不同的剩余类.引理：设S是由大个不能被13整除的自然数构成的集合，

kW13；A(S)是S中一切可能的部分元素的和被13除所得余数的集合，则A(S)开元素》左个.

证明：设4={q,/，…，”,}是S开4个元素模13后所有不同余数的集合，剩下来的A-r个余数分别

归入集合加={0,j},…，片={0,ak}.对A,8川利用定理，

知A={q，…，％，q，ar+i>…，ar+«r+i}中至少有r+1个不同的元素(模13).再对\,用.用定理,

这样继续下去，A(S)中元素不少于(…(什+1)+1)+…+1)=上个.引理证毕.

A-r个1

将26个数先分成13个两位数忑，也，…，试.考察由9q,9c2,…，9G3这13个数所构成的集

合S.由引理知，A(S)由模13的13个余数0,1,…，12组成.特别地，下式成立：

(mod13),其中p<13.现在，我们将两位数c,4，…，c,,4,都拆为两个数字，于是得

i=];=1

13P

到的2P个一位数及13-p个两位数的和是，q4-，>q,,它被13整除.

»=|j=\

14.2互质

1421★证明：对任何自然数〃，分式生七不可约简.

14〃+3

+4

解析因为⑵〃+4,14〃+3)=(7〃+1,14〃+3)=(7〃+1,1)=1,所以分式巴上2不可约简.

14〃+3

14.2.2★证明：对任意偶数">6,存在质数p、q,使得p,=1.

解析取p=3,q=5.p=〃-3与=〃-5是连续奇数，所以(〃-p,〃-q)=l.

1423★求三个正整数a,b,c,满足⑴个a<6<c；⑵两两互质；⑶任两个的和必是第三个数的倍数.

证明所找到的三个数是唯一的一组.

解析由⑴得a+bv2c,再由⑶得a+〃=c.从而a+c=2a+b,它是〃的倍数，故，但(@,£>)=1,

故瓦2.所以匕=2,a=l,c=3.

1424★证明：如果。、人是不同的整数，那么存在无穷多个正整数〃，使得a+"与6+〃是互质的.

解析设a、人是两个不同的整数，不妨设a<b,令〃=(6-a)&+l-a,当“充分大时，n,"+a,n+b

为正整数.(a+〃，b+n)=(a+n,b-a)=[(b-a)k+l,b-a)=(\,b-a)=l所以a+〃与6+〃互质.

14.2.5★举出一个例子说明：对于四个不同的正整数不一定存在正整数”，使

a+n,b+n,c+n,d+〃两两互质.

解析取a=l,b=2,c=3,d=4.对于奇数"，数a+w与c+〃为偶数，故(a+〃>c+〃)Hl.对于

偶数〃，数匕+"与d+"为偶数，故(b+”，d+〃)片1.

1426★证明：每一个大于6的整数都可以表示为两个大于1的互质整数之和.

解析如果〃为大于6的奇数，那么〃=2+(〃-2),这里"-2>1为奇数.显然(2,〃-2)=1.如果

〃=4k,k>l,那么〃=(2%-1)+(2A+1),这里2%+1>21—1>1,(2Z-1,2&+1)=1.如果

〃=4Z+2,k>l,那么〃=(2%+3)+(2%-1),这里2%+3>2k-1>1,

(2Z+3,2Z-l)=(2k+3,4)=1.

14.2.7★证明：每一个大于17的整数都能表示为三个大于1并且两两互质的整数的和.说明17不具有

这个性质.

解析如果〃为大于17的偶数，那么"可表示为〃=6&,〃=64+2或”=6左+4的形式.等式

6k=2+3+(6(Z-l)+l),6k+2=3+4+(6(Z-l)+l),6k+4=2+3+(6k-l).表明“为三个两两互质

的正整数的和.

现在设”>17为奇数.那么有6种情形：”=12Z-1,12A+1,12k+3,12Z+5,12k+7,12A+9.

而12k—1=(6仅+1)+5)+(6(k—1)+1)+3,

12*+l=(6(jl-l)-l)+(6(fc-l)+5)+9,121+3=(6左一1)+(61+1)+3,12&+5=(6"5)+(61+1)+9,

12%+7=(6Z+5)+(6k-l)+3,12&+9=(6A-l)+(6Z+l)+9.每种情形，者B不难验证，三项都大于1,

且两两互质.

若17有所述的表示a+%+c,a＜人＜c.a、6、c三数中有两个同奇偶，当然都是奇数.由于。+6+。=17

是奇数，所以第三个也是奇数.在a＞3时，a+6+c25+7+9=21＞17.在。=3时，b+c=\4,但

b=5,c=9不合要求.所以17没有所述的表示.

14.2.8★★设&=2”+1,则对巾有(£"，耳,)=1.

解析不妨设机”因为耳"-2=22"'-1=(2泊厂-1被22"，整除，而工=2?"+归'-1,所以

F„\Fm-2.设d=(%,工)，贝1」42,又甘,为奇数，所以4=1.

14.2.9★★证明：存在一个由三角形组成的无穷递增数列，每两项互质.

解析如果对于正整数机，有机个两两互质的三角形数4＜…〈金，那么令%…品，则

=生土华上0=(。+1)(2。+1)为大于%的三角形数.它与。互质，当然与“，小，…，勺中每

个数都互质，于是，由q=l可以得到一个无限递增数列：q=l,%=6,%=91,…它们是两两互质

的三角形数.

14.2.10★★数列q,a2，…定义如下：

《,=2"+3"+6"-1(〃=1,2,3,…).①

求与①的每一项都互质的所有正整数.

解析设”为大于1的自然数，则〃必有一个质因数p.如果p=2或3,那么(〃，%)=(〃，48)＞1.设

.由费马小定理2"三3k三l(modp),

所以6“片2=6(2°々+3p-2+6/,-2-l)s3xl+2xl+l-6s0(modp),

从而(因为(6,p)=l),p\ap.zy[n,ap_2)^p＞\.符合要求的正整数只有1.

14211★★试找出两个互质的四位正整数A、B,使得对于任何正整数和〃，数/T与8”都至少相

差4000.

解析取A=8001,B=4001.对任何正整数机和〃，A"'-8"都是4000的倍数，又因A"'WB",故知

\A"'-B"\^4000.

14212★★证明：存在一个由四面体数(形如7；=1〃(〃+1)(〃+2),〃=1,2,…的数)组成的无穷递

6

增数列，每两项互质.

解析如果对于正整数加，有〃z个两两互质的四面体数％＜生＜…＜《”，那么令。=4生…M，则

《〃+]=Q+i=(6〃+1)(3〃+1)(2〃+1)与。互质，当然也与生,生，…，%中每一个都互质,从而由

4=1,我们得到无穷多个两两互质的、递增的四面体数：4=1,生=84，….

14.2.13★★设/(工)=12-x+i.证明：对任意自然数加＞1,/(加)，/(/'(⑼)，…两两互质.

解析因为〃0)=〃1)=1,所以.(%)=1(/(…(〃力)…))的常数项二(0)=1.

从而，对任意的正整数相＞1,fn(m)=l(modm).用"，=人(相)代替加，得到力+人(小)=＜("?')与

W=互质.所以/(〃?)，f(/、(〃?))，…两两互质.

14214★★证明：对于数字全是1的两个自然数，当且仅当它们的位数互质时;这两个自然数互质.

解析用4表示数字全是1的相位数.显然在力帆时，11二1113,即

d个m个

当机＞〃时，(1/,“，J“)=(m」，比二1)=(上」—在二£匕g,H--1)=,j“).继续这一过程(与

，“个“个，“个“个〃厂〃个

求最大公约数的辗转相除法完全相同)，直至(，，4)=九*,).

于是，当且仅当(相，〃)=1时，(J,,,,J〃)=l.

14.2.15**«>6为互质的自然数，机为任一正整数.证明数列

a,a+h,a+2h,a+3h,•••①

开，有无穷多个数与〃?互质.

解析如果m与a互质，那么〃+“•"?〃，”=1,2,…，显然与相互质.如果m与a不互质，

那么设％=cM,其中c与。互质，而d的质因数全是。的质因数(c可以为1).显然a+〃cb与c互质.再

取，7为与d互质的数(这样的数当然有无穷多个)，则a+与"互质.从而“+〃仍与机互质.特别

地，取"=Ad+l(k=O,1,2,••■),则〃+〃仍=a+(A*+c)b(k=0,1,2,…).

因此，在①中有无穷多个数与，〃互质，而且还假设这些项也组成等差数列，首项a+仍与公差〃力仍然

互质.

14.2.16**«,。为互质的自然数.证明：数列

a,a+b,a+2b,a+3b,①

有一个无穷子列，其中的数两两互质.

解析a0=a,ax=a+b,

an+i=a+bala2---aII,n=l,2,•••②

是①的无穷子列.显然(a,aj=(n,b)=l.设(a,6)=1,k=1,2,…，n.

则(a,a“+J=(a,…4”)=1.设4,q,…，a,两两互质，则对于

(«„+i>《)=(。+加分…4,，%)=(。，％)=L

因此②中的数两两互质.

14217★★设A和〃为大于1的自然数，证明：小于川-1且与它互质的自然数的个数是〃的倍数.

解析小于A"-l且与A"-l互质的自然数组成mod(A"-l)的缩系.对于缩系中每个元素x,有一条

长为〃的“轨道”，由缩系中同余于x,Ar,A,，…A"Tx(mod(A'-l))的〃个数组成(这些数与犬-1

互质，而且互不同余).设〉=腾(即)，三A«x(mod(A"-l)))在x的轨道中，则x=4"Yy也在y的轨道

中.而且若y=A"x,z=*y,则z=A1x.所以缩系按轨道分类，每条轨道一类.由于这种分类具有

反身性、对称性、传递性，所以这是等价关系.缩系被分为若干个长为〃的轨道，所以缩系的元数被〃

整除.

评注另一解法参见17.2.10的证明.

14218★★★证明：如果叫心c是互不相同的三个整数，那么存在无穷多个正整数〃，使得

a+n,b+nfc+〃三个数两两互质.

解析设〃=攵(4一0)(力一。)+1—(？，贝!+c+〃)=(a—c,c+〃)=(a-c,+=l,

(b+〃，c+n)=(/?-c,c+〃)=伍一c,Z:(a-c)(^-c)+l)=l.设质数一b.若〃加一,,

则b+〃=攵(〃一+0-c)+1不被p整除.若p(E?-c,则pG&-c,

从而k(a-c)(b-c)+(/?-c)+1=l(modp)有解%三(mod/?).当p跑遍“一〃的、满足p(仍一c的不同

质因数时，由中国剩余定理，有无穷多个正整数k三3(modp).

对这样的3(a+〃，b+n)=(a-b,b+n)=［a-b,&(a-c)(b-c)+(b-c)+l)=l.因而有无穷多个正

整数〃，使〃+〃，〃+〃，c+〃两两互质.

14.3因数与倍数

1431★设(4,b,…，g)与［。，b,…,g］分别表示正整数a,b,…,g的最大公因数与最小公倍数.

[a,b,(a,b,c)2

证明:①

[a,h][hfc]-[c,a](a,b),(b,c)(c,a)

解析对任意质数p,设它在〃，。，c的标准因子分解式中的次数分别为相，*r.不妨假设

“2〃2r(20).①式左端含p的次数为2次一(团+〃+〃?)=一〃.①式右端含p的次数为

2r-(n+r+r)=-H.即对任意质数p,①式两边含〃的幕相同，所以①式成立.

14.3.2支m，。为正整数，a>]t证明：

（am-\A/i、

-----,a-\〃?）・

I）

m_i

解析根据恒等式》n亍=（优-J1）+（产2_1）+...+（〃_1）+加得，

-----,a-\-1,机）.

I"1）

14.3.3★已知正整数“，6互质，求证：

（“+/?,/+〃）=1或2.

解析（a+b,/+62）=d,则d可以整除（°+/7）2-（病+〃）=2".由于（-3=1,4的质因数不整

除a+b,所以（"，“）=1.同理（d,b）=l.因此42,即d=l或2.

14.3.4★一个大于1的整数，如果恰好等于它的不同真因数（除1及本身以外的因数）的积，那么称它

为“好的”.求前十个“好的”自然数的和.

解析设自然数〃的不同真因数依递增顺序排列，依次是4,4，…，4，则必有

\n=d}dk=d2-dk_x='•■,若〃是"好的"，则又应有1•”=&,4,•・”,因此，女只能是2,4必须是

质数；4必须是质数或亦即，〃只能是两个质数的积，或一质数的立方.由此，可以求得前十个

“好的”自然数：6,8,10,14,15,21,22,26,27,33,它们的和为182.

14.3.5**〃+1个正整数“，的，…，〃用都不超过2〃.证明其中必有一个是另一个的倍数.

解析设为=2"的，其中弓是非负整数，勺是正奇数（lWjWn+1）.由于勺<2〃，而小于2〃的正奇

数只有〃个.所以必有左="（1Wi<jWn+1）.从而q与％中，一个是另一个的倍数.

14.3.6★当4"+4"为100的倍数时，相+〃的最小值为多少？（相，”为自然数，且相>〃）

解析因为4"'+4"=4"（4"-"+1）,100=4x25,所以〃=1.

使4"+1被25整除的自然数左最小为5.所以机2n+526.m+〃=7为所求的最小值（在〃=1,机=6

时,4"+4"=4x1025=4100是100的倍数）.

14.3.7★★设q<的<《0为正整数.记处的最大的不等于自身的约数为4.已知仇>4>…>九，

证明：ain>500.

解析令4=%，则G为%的最小质因数（若q是合数，则可将q的一个质因数与“相乘，得出比4

更大的、不等于4的约数.若,不是最小的质因数，则可将4的最小质因数换成/.均与4的最大性

矛盾）.

因为4<4+1,白>如1,所以Jee?<…〈Go,从而J》2,c?23,…，%223.%>九，

所以&*1，C9N“9，从而伉》仇.

ai0>的，（。9）一2529>500.

14.3.8★设町，m2，…，机，（可以有相同的）与外,%,…，%（可以有相同的）是两组正整数，满足：

对任何大于1的正整数"，第一组数中4的倍数（含重数，如6、6、3、2中3的倍数有3个）不少于

第二组中d的倍数（含重数）.证明：网，叫，…，?开有q个数是p'的倍数，%,%，…，〃,中有2

个数是炉的倍数，则a,2b,（i=l,2,…）.因而在见色…乙的质因数分解式中，p的基指数

4+%+4+….所以叫〃??…是"也…%的倍数.

14.3.9★★设〃是自然数.我们考虑以〃为最小公倍数的自然数对（"…）（如果“打，那么我们认为

数对（〃，v）与数对（“，v）是不同的）.证明：对给定的〃，这种数对的个数等于/的正约数的个

数.

解析n的质因数分解为"=p：'pf…p?,Pi,P],p,为不同的质数，a,,a2,■■■,as为正整数.因

为[“，v]=n,所以"，丫的质因数分解中只含有质数p「p2,亿.对于质数月，它在〃的分解式中

的指数为4,所以在的分解式开，网的指数都不大于并且至少有一个指数等于于是，在

u,v的分解式开，口的指数分配总共有2q+l种不同的情况.对质数pz，凸，…，区可进行类似的讨

论.从而，在〃，v的分解式中，质数四，生，…，区的指数可能取的方法共有

(2《+1)(2生+1)…(2/+1)种.这个种数正好就等于r=於p；”…靖的正因数的个数.

14.3.10**17的一个倍数写成二进制数时恰好有三个数字1.证明它至少含有6个数字0.而如果它恰

好含有7个数字0,那么它就是偶数.

解析17=24+1在二进制中为10001(以下均采用二进制).10001的倍数为10001X"?.如果m的位

0a0a

数<4,即机=qa2a3%，其中qe{0,l},那么10001x/n=a1a23a4123a4，其开1的个数为偶数,

与己知不合.因此，〃至少为5位数，lOOOlxm至少为9位数.如果10001x〃?恰好有3个数字1,那

么它至少有6个数字0.如果lOOOlxw恰好有3个数字1,7个数字0,那么它是10位数，此时“必

为6位数.设m=la24a4%4，若4=1，则将位OOlxm列成竖式得

X1001+1000000-•①式-----

la24a4出1②式

从①式可以看出，当々=0时，无论为为0或1,lOOOlxnt至少有4个1.

当4=1时，10001xm=1la3a4a5Oa3a4a51+1000000.从②式看出，若q=0，则lOOOlx/n至少有4

个1.若q=1(此时％=0),则10001X,"至少有5个1,以上均与已知不合.因此必有％=。，即

10001X加为偶数.

14.3.11★★已知r,s为正整数.正整数的有序的四元数组(a,b,c,d)满足：

3'-T=[a>b,c]=[a,b,d\

=[a,c,t/]=[/?,c,d].

求这种四元数组的个数(答案是r,s的函数).

解析答案是(1+4厂+6埒(l+4s+6s2).

事实上，a,6,c,d中每一个都是3"'7的形式，nze{0,1,2,…，r},〃e{0,I,2,…，6}.并且

a.b.c,4中至少有两个数〃?=r,也至少有两个数〃=s.当a,b,c,d都有m=r时，只有一种取

法.当a,6,c,d中有一个数使me{0,1,…，r-1},另外两个数中的机=厂时，有C：•产=6产种取

法.于是根有l+4r+6,种取法，同样地，〃也有1+4s+6s2种取法.

所求个数为(1+4厂+6，乂1+4$+6$2).

14.3.12★★数列101,104,116,—

对每个以4记可与a向的最大公因数.试求：当〃取遍正整数时，的最大值.

解析因为=(100+/,100+(«+l)2)=(100+n2,2n+l)=(2(100+n2),2n+l)=

(200-n,2n+l)=(200-n,401),所以，当”=200时，d,最大，最大值为d2ao=401.

评注我们有一般的结论：若“为一正整数，4是4+/与a+5+炉的最大公因数，则当”=2“时，

4,达到最大值4〃+1.

14.3.13★★证明：存在无穷多对不同的正整数m，n,使得机与〃的质因数都相同，并且机+1与”+1

的质因数也都相同.

解析当Q1时，数对巾=2,2,”=2*(2*-2)满足题设条件.因为机+1=2*—1,〃+1=(2*—1)2.

14314★★证明C：的质因数分解式中,质数2的幕指数为S伙)+S(〃-A)-S(〃)，其开S(大为a在二

进制中的数字和.

解析C=/"、•〃!的分解式中,2的寨指数为〃-S(”)，所以C：的分解式开，2的事指数为

k\\n-k)\

〃——[z—S(左)+(〃—氏)—S(〃—攵)]=S(A)+S(〃—A)—S(几).

14.3.15*