haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

整除、同余不定方程(第二版)

发布时间:2014-04-13 11:48:03  

目  录

????整除

)P)????整除的概念与基本性质)PQ????素数与合数

)P/????最大公因数与最小公倍数)PR????算术基本定理??习题)

$$0$$0$$!$$3$0!$01$#0$#0$#2$#4$!!$!"$<0$<2$<2$2$$"$$"2$"1

????????

????同余

QP)????同余的概念与基本性质QPQ????剩余系及其应用QP/????费马小定理及其应用QPR????奇数与偶数QP+????完全平方数??习题Q

????不定方程

组??/P)????一次不定方程??/PQ????不定方程的常用解法/P/????勾股方程??习题/习题解答

目录

??????????????????????????

'??%??(

*??%??+

??????

????':6<??(????':6<??(??)':6<??(

*??+

:LT,??%??-

:35,??%??-符号说明整除??不整除??与??的最大公因数与??的最小公倍数??????但????S)??与??对模??同余????????与??对模??不同余对模??的数论倒数不超过??的最大整数实数??!??中较大的数实数??!??中较小的数

符号说明????????????????????????????

整  除

任意两个整数的和??差或积都是整数??但是两个整数做除法时所得的结

因此??数论中的许多问题都是在研究整数之间的除法!果不一定是整数??

????????整除的概念与基本性质

????使得#%"如果存在整数$??定义??#??"??????对任给的两个整数"??$??

??那么称#能被"整除??记作"或称"能整除记否则??称#不能被"整除??#??#!??

作"#!

那么称"为#的因数??如果"#??#为"的倍数!??

利用整除的定义??可以非常容易地推导出下面一些经常被用到的性质!

????那么"反过来也成立??进一步??如果"那么性质????#??#??#??????????如果"

??反过来也成立!??"??#????

因此??我们经常只讨论正整数之间的整除关系!

??性质??那么"&这表明整除具有传递性!#??#&''!??如果"&

????则对任意整数(??都有"性质??即"能整#??"'#(*'&&&??若")??)!

??线性组合??除#??'的任意一个??

??且存在整数(??使得"例??证明??+??#+??(*#"#&+!&&??若")%??)??

证明??由条件??可设+%"于是,??+%#-??,??-为整数!????????

+%+??"(*#)??

"(*+#%+)

#-(*"#,%")

??#??-(*,%")??

因此"#&+!

????并不能推出"例如??但说明??一般地??由"&+??#+??#&+????????&&&

??见??为??即"题中给出的条件实质上表明"??????节??!#的最大公因数????????

整除

与#互素"在此条件下可推出"#&+!

"所得的数都是例??无论在数??????????的两个??之间添加多少个????证明(

????的倍数!

")"")!"证明??记"????????????????"??????+%????%??+%??*+个??

首先"因为

""??.????????%??

则由其次"设????"&+"

"""??????%????.??????/??++%??*

可知????"&+??!*

数"所以"对一切整数+"??的倍数!+都是??

说明??此题的处理过程中运用了递推的思想"其基本思路是将"+??表示*为"??的一个线性组合!+与??

例????????位正整数的任意连续????个数码形成的????位数是??已知一个??

????????

????????????的倍数!证明(该正整数为??的倍数!??其中"证明??设该正整数(%"由条件"可知""????)????????"0是十进位数码!????????????????""""??????)????????"??????)??????""????&??!

因此??????????!""??????)??????.??

则有记)%""??????)??????"

????????????????"*??)"??????.??

????可知结合????""??????)????????"????????????)!

??????????&)*"????????"

于是

这要求

类似地"朝前倒推"可得????????"????????""!????????%??

""????%)%"????????%??

即))!(%""!!#??#!.#

#!即可得再结合条件$??""#??#!??

#!!!$(!&

说明??这里先证明"在证明中利用##%??%"#!!!%!是非常关键的??""))#??)))来过渡也是比较巧妙的!

1都有$证明??对任意正整数+??例??/#??设1是一个大于$的正整数??

+!$*#

1+??那么取其中最小的那使得$证明??如果存在正整数+??/#&$*#

个+!

+1??????而+%1知+??#进一步??应有$由于1??$知+??1??*#??$/#

1+++????????时??将导致$因为$%??右边每一项都是$$$$/#&*#/??/#/#的??矛盾??故+??1!倍数??

+1??这里$为正整数??现在??设$则$*#%??/#$??

+1+11????????????$$$$*$%??*#*??/#%??/#$*#

于是??1??+11/????????$$$!*#%??/#$*#????????

+11+11//??????????????????$$$$*#*??/#*#%??/#$*#+11+1??1+"1//????????因此??得$与+的最小性矛盾!$$"#$*#*#%??/#??$/$

所以??命题成立!

??????则&说明??这里用到了两个结论??一个是??若"它#??#??!"#&&&&??

??由整除的定义可直接证出!另一个是??任意多个正整数中必有最小元??这是

著名的??最小数原理??!

????????素数与合数

??如果除#与+以外??对任意正整数+??#那么称+为+没有其他的因数??

??素数!否则称+为合数!这样??我们将正整数分为了三类??素数??合数!#

????????????!素数从小到大依次为$我们可以非常轻松地写出#'+,##!!

都能轻易地指出2后面以内的所有素数??共$但是并不是对每个素数2??+个!

求出它后面的那个素数是十分困的一个素数是多少!事实上??当2比较大时??

难的!正是素数的这种无规律性??初等数论才显得魅力无穷??具有很强的挑战

整除

性和极大的吸引力!

素数与合数具有如下的一些性质!

性质????设+为大于#的正整数"2是+的大于#的因数中最小的正整数"则2为素数!

都有2+"那么+为素数!性质??这之间的素数2"??如果对任意#到$为正整数!里+#??#

$即证明??事实上"若+为合数"因此2则可写+%2$??2??$!$"??+"

!2??且它是+的因数"这表明2的素因子??与条件矛盾!因此+为素数!"

说明??这里素因子是指正整数的因数中为素数的那些数"此性质是我们检验一个数是否为素数的最常用的方法!

性质????素数有无穷多个!

考虑数证明??若只有有限个素数"设它们是2#??2$??)??2+!

"(%222#$)+*#

)"它是一个素数"因此"其最小的大于#的因数2"2应为2#"22$"+中的某

并且(%2则2即2个数!设2%#??0??+"#%22)"22)")/0"0#$)+*00#

????????

这导致2矛盾!!#!%#22222#$)00+$0&##)/*

所以"素数有无穷多个!

并写说明??如果将所有的素数从小到大依次写出为$%2#??2$??)"

"那么$22+%2#$)+*#

"""""###'##$$$$$#%'$%,'%'-%$+%$

它们都是素数!是否每一个+都有$+为素数呢+我们不能被表面现象所迷惑"再朝下算"可知$事实上"后面的$).+!)就是一个合数!$$%%+,"(")"

)中是否有无穷多个素到目前为止"人们还不知道数列$$$#!都是合数!#"$"

数"也不知道其中是否有无穷多个合数!

性质??它是$!??素数中只有一个数是偶数"

+-例??证明(数+*+*#不是素数!??设+为大于#的正整数!

证明??注意到

+-*+*#??+??????????????

+-''$+*+*+/#/#%+

'$$$$#$#++/#+/#*+*#*+*#%+

'$$#$"++%#/+*#*+*#

+-'"因此"若+则+这要求+%!或.#!*+*#为素数"/+*#%#

+-故当+%#时"+*+*#不是素数!

说明!利用因式分解来判断一个数是否为素数是数论中的常见方法"后面也将不断用到!

例??!考察下面的数列(

""")!#!##!#!##!#!#!#

问(该数列中有多少个素数+

解!易知#下证这是该数列中仅有的一个素数!!#是素数!

")则当+&$时"有记"+%+个!#

$+$+#/!!"*#*)*#+%#

#$$+#*%$#!/#

##++**#$#$!%))

##++**""故"因注意到"而"))(#!#))(#!#/*+为正整数"+是一个合数###++**$为分子中的项#!!)约为#!/#与#*#都不能被)

+++#$//$#$反说明!这里需要将因式分解式((/#(/#%#*(*)*##$??????!

用"高中阶段它被作为等比数列求和的公式!

#$使得/#是一个素数!例??!求所有的正整数+"$

$#"解!记"因此只需讨论+%#的情则"#/+%#%!不是素数"$

!!形!我们利用+只能是形如--3!3*#3*$3*'的数分别讨论!--

要"只能是当+是形如-3*$或-3*#的数时""+都是偶数"+为素数"

$#"/#%$$

解得

可得当+%-3时"

$-"3#3*#/#!!!+%$

$33/#*$%(

$#$"-3/#$3*#%#+%$!

这是一个合数!

可得当+%-3*'时"

整除

#$#$"3*#3*'-/#+%$

$-33*+*#%(

$#$"-$3*+3*#%#

"仅当3%!即+%'时""+为素数!

所以"满足条件的+%$或'!

说明??对+分类处理一方面是去分母的需要"另一方面是为进行因式分解做准备!

证明(存在连续+个正整数"例??它们都是合数!??对任意正整数+"

则证明??设+为正整数"

$,*$"#$,*'")"#$,*#$#+*#+*#+*#+*#

"是+个连续正整数"并且第3个数是3*且大于3*故它们是连#的倍数##$

续的+个合数!

都存在两个素数"它们之间至少说明??这个结论表明(对任意正整数+"

"$"#"$"有+个数"且这些数都是合数!但是"让我们来看一些素数对#'++,

#"$"#"$")"#"$"#它们所含的两个素数都只相差$这###'#,#)#)),#)))

"是两个奇素数的最小差距$这样的素数对称为孪生素数!是否存在无穷多对

????????

素数"它们是孪生素数+这是数论中一个未解决的著名问题!

满足+??2??+,!证明(存在一个素数2"例????设+为大于$的正整数!

)"证明??设2且2+的素数"22#??2$??)??23"#"$"3是所有不超过

考虑数

"$%222#$)3/#

)""利用性质故+??$??+,/#??+,"在+??$时"$'都在22#"3中出现"

)"可知$的素因子2不等于2#"而'证明中的方法"22$"3中的任何一个!

)"所以+??2??$??+,!因此2??+"+的素数"222#"$"3是所有不超过

从而"命题成立!

说明??利用本题的结论亦可证出(素数有无穷多个!贝特朗曾猜测在

有一个素数!如果将素数从正整数1与$不包括1与$#时"1??1之间#1$

小到大排列为2该猜测亦即2这个猜测被契比雪夫证2#??2$??)"+#??$+!*

明了!因此它被称为贝特朗猜想或契比雪夫定理!

!!!例??#'4!57%"*#*'*4*5*6是"#'*??设"!6都是正整数"

证明(45#*#'*'""45"554的因数!7为合数!6和"6"

证明??考虑多项式

????????????/??"??!(??(*"??(*#??(*'("4??("5("6??6??

展开后??可知

!4??(??($*??"#*#'*'"/45/5(*??"#'*45%76??6/66??

??特别地??取(/就有7即由条件可知??对任意(,'??都有7!(??4??4??$$6??6??

????????????由于"??故4*!74*"??4*#??4*'#??'4??5"??4*#??$6都为正整数??

所以??4*'都小于7??7为合数!

??说明!对比例$两个例子中分别用到下面的结论??若(??8为正整数??)??

亦为整数??为合数??那么且则如果(??如果(??8??)%)(8??那么8为88

合数!

??????!最大公因数与最小公倍数

那设"??如果4#是不全为零的两个整数??4是一个非零整数??"且4&#??&

么称4为"??#的公因数!

注意到??当4&则4'对"且4&#时??"&或4'#&&&中必有一个成立??

因此??这个数称为!"??#中不为零的数成立??"??#的公因数中有一个最大的??

??????如果??那么我们称"??记为??!"??#的最大公因数??"??#"??##互素!%#

在讨论最大公因数的性质之前??我们不加证明地引入一个在小学就接触到的??数论中最基本??最常用的结论!

??则存在唯一的一对整数$和带余数除法!设"??#是两个整数??"#!9??

满足

??!'9(#%"9??#&&$*

其中$称为#除以"所得的商??9称为#除以"所得的余数!

????则存在整数(??使得性质!"??#!设4%??)????????!

"(*#)%4!

??这个结论就是著名的贝祖??定理!()*+,-

证明!我们利用带余除法来处理??此结论的证明过程又是求"??#的最大公因数的过程??它被称为??辗转相除??!

??不妨设"??当"??结论是显然的??且#都不为零??#中有一个为零时??

"&#!&&'&

????设#%"若9其中!'9则辗转相9"9&&$$#*#??#(#??#为整数!#%!

整除

得等式"%9依此讨除到此为止??否则用"去除以9????99$????????*????????9??????论??由于9因此辗转相除到某一步后??所得的9于是??99??%??????????????????3*我们得到了如下的一系列式子??

??????9#%"9"&&$??*????????

????9"%99$????*????????9????????999$??%9????*????????9????

??????????????????????????????999$3*3??3??9333??%9????///

9$333??%9??!/*

我们依次有注意到??从第一个式子到第3个式子??

????4&94&94&9????????3??

而从第3*??个式子倒推??又依次有

??3&????999999"??9#??3&33&????3&3&????/3??9/

??所以??又4&结合4为"??9"??#的公因数??#的最大公因数知993又是3??43??

因此??故4??9也就是说??我们求出了"??4%9#的最大公因数!3??3!

????????

现在??利用4%9可知3个式子??3及第

4%99$3??33??/??//

再由

??????99$??%9??/????第3/??个式子变形得3333////

??????线性组合??见??依代入上式??可知4可以表示为9????节性质????与9??的??33//??此倒推??可知4可以表示为"??线性组合??即存在整数(??#的??)使得

4%"(*#)!

并不能推出4说明??反过来??设(??4:%"(*#:为"??#的)为整数??)??最大公因数!事实上??可以证明??"??#的最大公因数是形如"(*#(??)??)为任

意整数??的正整数中最小的那个!

????性质??则4!#的公因数??"??#????设4为"??

这个性质可由前面的贝祖定理证出!事实上??贝祖定理也是初等数论中的一个基本定理??应用非常广泛??下面的性质是它的一个直接推论!

性质??则"与#互素的充要条件是存在整#是不全为零的整数????设"??数(??)满足

"(*#!)%??

"则"且#性质$'"#&'"""#$#&'!%#??设"&

这个性质的证明见#&#节的例#!

"且#则"&性质%#'"""#$'!%#??设"&

"证明??由性质'知存在整数(!)使得

""(*#)%#

"由"&可知"&故"'(*#'#'及"&"'("'!)%'

则2&性质&"#""或2&#!??设2为素数"2&

证明??由于2只有两个正约数"故#若#"$"$"$%#或者#%2!%2"2"2""则由性质+知2&若#则2&##%"$"!%2"2"

下面引入公倍数的一些概念和性质!

"那么称'为设"!如果整数'满足"&#都是不等于零的整数"'且#&'

在"!最小的那个称为"!"!#的公倍数!#的所有正的公倍数中"#的最小公

倍数"记作-!""#.

性质.#为非零整数"4!'分别是"!#的一个公因数与公倍数"??设"!

"-则4&#""#$""#.'!&

证明??这个性质在本质上反映了最大公因数与最小公倍数的属性!前者是性质$的结论"这里再次列出是为了对比!

对于后者"采用反证法予以证明!

.'"设'%-.."则由"&/若-!??9??-""#""#""#'及$*9"

."."可知"&同理#即9为"!这与但9??-"&-""#9"9"#的公倍数"""#&

..-是"!所以-""##的最小公倍数矛盾!""#'!&!!*??

.则-性质/!#都是正整数"""#%??设"!"#

"$$"证明??记'%则由#即'为""#"及#""##知#&'"'!&&&"#

.故-"!#的公倍数"""#'!&

使得反过来"由贝祖定理"知存在整数(!)"

$""(*#""#)%#

于是"*#"$%##"$"#"#.-.-"".!""#*%-"#"#

.."由#及"&-可知""#""#&-

整除

-".-".'"'!"#"#

所以

综上"可知'""#.!&--""#.!%"#

一般地"对+个整数#非零$可以类似地引入最大公因数"""#"$")"+"

与最小公倍数的概念"分别记为#和-容易得""""""!#"$")"+$#"$")"+.到下面的一些结论(

#"%而-性质??""""""""""%#??##"$"'")"+$#"$$'")"+$#"$"

)"-")"""""""!%-'"+.#"$.'"+.

)"性质??使得??((??存在整数(#"$"+"

)""("("("""!##*$$*)*++%##"$"+$

#)"")"特别地"即"存在整"""""%##"$"+$#"$"+互素的充要条件是(

)"数(使得((#"$"+"

"("("(!##*$$*)*++%#

????????""注意"并不能保证它们两两互素"例如#+个数互素"$.'$.+'.

$"!!但%反过来"若+个数中有两个数互素"则这++##!#+两两不互素!%

&个数互素!因此"在+个数中"两两互素'的条件比&它们互素'的条件要强

得多!

性质??则????设1为正整数"

#)")"%1"1"1""""%1##"$"+$#"$"+$

-)")"1"1"1""""!%1-#"$"+.#"$"+.

也是正整数证明(#$例??且#为正整数"!""#!??设"!??#"*#

$"$"证明??若#则#这由性质'可推得$从而"由""#"""*#%#%##

$"得"*但是"*故"*"*#&"#及#"""*##&#"#??#"##不可%#&

#$能成立!所以"""#!??#

说明??在辗转相除求"!可知对任意整数("都有#的公因数的讨论中"

#$%#"这一点在利用最大公因数处理数论问题时经常被""#""#*"($

用到!

$$!#$$例??证明(#'满足#'!""#""'!%"%"#??设正整数"!

$$$#$"$""证明??如果我们能够证明(那么结合性质#可知""#"##%#

$$"$$$"$#$""#$"#%#""'%"#""'!%#

命题获证!

"为此"记4%#设"%4则由性质#""#$,"#%4-"#可知,!-是两个$"$$$"$"$$#为证#只需证明(互素的正整数""#%4,-%#!

$$$"利用贝祖定理"知存在整数(!使得,故,(*-(%##/-%)")%#)$

$"$$""结合性质'可知#交换,与-的位置"同上再做#*-#-$,-%#)$)$/

$"$$即有#一次"-,%#!

所以"命题成立!

$"$$说明??利用下一节的算术基本定理可以非常方便地证出(#"#%

$"#但遗憾的是我们还没给出该定理的证明"通常都是先建立最大公因""#$

数理论再去证算术基本定理"这里不用该定理是不希望掉入&循环论证'的旋涡"读者在学习中应认真掌握其中的逻辑结构!

"例??使得##"??#$??求所有的正整数"!

-#"#%'!!*,""#.""#$!*+??

.$解??设-由性质(可知"于是"""#""##%(%("#%)"??变为)"

(!!*,(*+)%')"

$#$即#(/+,!%+.%)/,

.$""只有如下的两种由于-故(??)"进而(/+??)/,""#""#??#

情形!

%""情形一??(/+%%此时"于是"可设,且)/,%+(%,$$)%#

"#"并有#结"%#$+"#%#$1"#1"+$#$+$#$1$#%($.,$%#%")%#

"$"$"$"$"合"??#"只能是#或#对应的#或#1"+$#%$'""##$,$$-%#%#

$'%!

%""情形二??(/+%'对应地"但)%#'+且)/,%#(%'-!"")%(

$."是(%-的因数"而('所以"此时无解!#""#-!

$"$"$综上"符合条件的#或#""##$,$$-'%!%#

例??使得#"??求所有的正整数"!

#$-.#$""#""#"*#"#!*)*)%,

-."由性质(知$于是代入??可得""#(%4)#

##*)((*)$4(%,)*))"??

整除??????????$"解??记#设"%4则#由性质#""#("#%4("#知$%4"%##)")$

所以

故"*$*()()")??,4??)*)*$(*%$###.#,4%)*)$??4??-!

当4%$时"由??得

#"+((*)$%#)/)

"两边乘以+并将左边因式分解"得

#$#$"+(/)+%%$.-'%()/)

"$"$!#"$"#"$!#"$故#分别求解可知只+(/)+#(%(%#$-'-'$!%#)/)

"$"#"$""$"#"$能是#对应的#("$#)#)$""#$-'('(-!%#%#)$

""$分别就4%'得#-同上讨论"""#$--!%#

"$"#"$"#"$所以"满足条件的#""#$-'('(---!%#

""例??12345661数列定义如下(;;;+%#??0#%;$%#+$%;+#*+"**

")!证明(对任意正整数1!都有#$+";;!%;#1"+$1"+$

证明??当1%+时"命题显然成立!现在不妨设1??+"注意到

????????;;;+%;$+/#*;#+/$??????????

;;%;*;$#+/$*;+/'$#+/$

;;;%#$*;#$+/$*;$+/'

;;%;'+/$*;$+/'

;;%;*;'#+/'*;+/-$$+/'

;;%;-+/'*;'+/-

%)

;+/1*;%;1#*;1/#+/1"

因此"设4&则由上式可知4&又对任意正整数1"有;1且4&;;;+"1/#+1!/

#";1";1/;1/;1/;1/;1/;;;%#%#%)%#%##$#*$"#$#"1/$$$"#$

#"所以"故4&反过来"若4则由上式4";1/;:&;:&;%##$++1"/1%/1且4

又可知4依此可知#:&;;;1$;;!%#+!+"+1$/1"

利用上述结论"对下标进行辗转相除"就可证得#;;!%;#+"1$1"+$

说明??由本题的结论还可以推出一个有趣的性质(若;则+%-+为素数"

或者+为素数!

事实上"设;而+为合数"可设+%2/$??2??$"$"2!$为正+为素数"

#整数"则由前面的结论"可知#;;;;%;#%;#+"+"+"+"2$2$%;2"$$$$%

结合0可知;而;故;12345661数列的定义";+??;+??;+为素数"$!2"$"

#""所以"再由$??2??$"可知只能是;;;;;%#%#+"+"2$$$2%;$%#

"即+%-所以"性质成立!!2%$%$

例??证明(存在从小到大排列后成等差数列??设+为大于#的正整数!

#即从第二项起"每一项与它前面那项的差为常数的数列$的+个正整数"它们中任意两项互素!

证明??考虑下面的+个数(

"")"+,*#$.#+,$+.#+,$!*#*#

这+个正整数组成一个公差为+,的等差数列!

我们证明其中任意两项是互素的!

事实上"若存在#??0??<??+"使得数0.#+,$+,$*#与数<.#*#不

"$设4%#考虑4的素因子2"可知互素"0.#+,$+,$!*#*#<.#??#

$$"+,$0.#+,$*#/#*#2&#<.#

$即2&#由性质%知2&结合#??</可知0+,!0或2&+,"0??+".</</

#$,",!,$",$"所以"总有2&但是"故2&0++4"40.#+0.#+&&*#*#</2&

,""结合2&导致2&矛盾!+#

所以"命题成立!

说明??此题为导出与反设矛盾的结论"采用了素因子分析的方法!该方法在数论中有广泛的应用!????????

????????算术基本定理

在#对每个大于#的正整数+"如&$节中我们引入了素数与合数的概念"

果+为合数"那么可写+%+其中$??+再分别对++++#$"#??$!#!$重复这样的讨论"即可将+表示为一些素数的乘积!对这个过程认真思考"就能得到下面的重要定理"在解数论的问题时经常会直接或间接地用到它!

算术基本定理??设+是大于#的正整数"则+可以分解成若干个素数的乘积的形式"并且在不考虑这些素数相乘时的前后次序时"这种分解是唯一的!即对任意大于#的正整数+"都存在唯一的一种素因数分解形式(

????#??$3+%22#2$)3"

)"这里2??????#??2$??)??23为素数"#"$"3为正整数!

整除

证明??利用前面的分析"可证得存在性"下面证明唯一性!

若+有两种素因数分解形式(

??????????)??3??????)??="+%22$??2??3%$??$??=??

其中2且都是素数"??$$$????2????)??23"????????)??="0!<都为正整数"??

????0??3"????<??=!

我们证明3%=且2??0%$0"0%??0!

????????)??="事实上"由??知2利用前一节的性质??可知"存在某个<使$$0&??$??=

??<""再用一次性质??知2这要求2即对????0??3及每个2&2$$$0&00%0"<"<!<

)"在$使得2反过来对$又有对????$$$??"??"=中总有一个0%$<"<!<分析"

)""在2使得$这表明3%=及每个=<??$222??"??"3中总有一个0"0!<"<%2

)")"且$结合2$$22??"??"=是2??"??"3的一个排列"????2????)??23及

知2进一步证明??????0??3!$$????????)??$="0%$0"0%??0是容易的!

利用正整数+的素因数分解式"我们可以简单地得到下面的一些结论!

"包括??和+$的个数为4#那么??%+$??设+的所有正因数#

$#$)#$4#+$!%#????????*????*??3*??

????????由此公式易知(为奇数!+是一个完全平方数的充要条件是4#+$"那么??%+$??设+的所有正因数之和为??#

????????$??$3$##)#+$??*2??*2??*2%#??222??*)*??*)*3*)*????3!

#由此可知(为奇数的充要条件是+为完全平方数或者某个完全平方+$??

数的两倍!

??%1的素因数分解分别为??设+!

??????????)??3??????)??3+%21%222??2??3"??2??3"

这里2都为素数"并且对每个????0????????2????)??23"0!0都是非负整数"??

????????)??3那么"我们有#3"1"+$%21"+.%??20与??0不全为零"??2??3%-

????????)??30"0"其中????"#'????0??3!??????220%&0"010%&0"01??2??3"????

"")"例????????????的灯共????????盏"??在一个走廊上依次排列着编号为??

最初每盏灯的状态都是开着的!一个好动的学生做了下面的??对??????次操作(

"该学生第3次操作时"将所有编号是3的倍数的灯的开关都拉????3??????????

了一下!问(最后还有多少盏灯是开着的+

"解??设????+????我们来考察第+盏灯的状态"依题意"该盏灯的开??????

关被拉了4#次!而偶数次拉动开关不改变灯的初始状态"奇数次拉动开关"+$

灯的状态与初始状态不同!

"")"利用4#的性质及前面的讨论"因为#+$$$!#$中恰有--个数为

完全平方数"可知最后还有$!#$/--%#)%(盏灯是开着的!

$例??使得+%4#+$!??求所有的正整数+"

解??当+%#时"符合条件"下面考虑+??#的情形!

由条件知+为完全平方数"因此4#为奇数"设4#鉴于对+$+$%$3*#!任意正整数4"当4&有&因此"我们将4与配对后"可知4#等+时"+"+$44

"")""")"于数#又#$$3/#中为+的因数的个数的两倍加上#!$$3/#

$$$""中的偶数都不是+#的因数"因此结合4#可知#$3*#+$%$3*#%#

")"$$3/#中的每一个奇数都是+的因数!

#"$%#"$%#"注意到"当3??#时"故$$3/#$3*#$3/#$3/#

$$#$$"所以3??#时"不符合要求"故3%#$3*#!+%#$3*#+只能等于)!直接验证"可知#和)满足条件"所以+%#或)!

说明??此题考虑了+的因数关于分析出一个非常强的条的对称性"

件"从而解决了问题!

它还有一个一般性的处理方法"需要用到如下的估计(设2为不小于+

$$????$$的素数"则2而????$时"这两个不等式都可以用!'!??*#??*#??#??#

数学归纳法予以证明#对??归纳$!

$现在设+#是一个满足条件的正整数"则+为一个奇数的平方"于??#

????#??$)??3"/2是"可设+%'其中'??2并且??"2#??2$??)??23"#"#2$3??

$#$)""$$/如果3??!那么由前面的分析"知+??##??*#$"3都是偶数!#*??????

$)#$$"??#$$矛盾"故+%'进一步分析"可知????$时"有#+$!%4#$*#3*????

$"??$"故??%$即+%)'!??*#????#

++#/$$例??证明(数$*$*#至少有+个不同的素因子!??设+为正整数!

证明??我们作如下的分解(

$$*$*#????$

+#+#//$$$$$%#*#/$

+#+$+#+$////$$$$$#$$$%#*$*#/$*#

+$+'+$+'+#+$//////$$$$$$$#$#$$$$%#*$*#/$*#/$*#

%)

$$$$$$$$#$#$)#$$$$%#*$*#/$*#/$*#

++#/#!#!$#????????++#/+#/$/$+$/$!*#$$这样"我们将$为证明它有+个$#表示为+个大于#的正整数之积"**

不同的素因子"只需证明这+个大于#的正整数两两互素!

整除

????????????

注意到"当1??=时"??*??*??与??/??*??都是??*??的因数"因此

????

??/????#??????/????#??????%#/??

??

由于"??.??

1??/

111

1??/

==??/==??/11??/

*??

????"??*??>??

1

==??/

$*??$*??

1??/

????"??*??*????"??.??*??

1

1??/

1??/1??/

$!

1??/

????"中只有一个素因子??而??/??????#??/??

1

1??/

故*??为奇数"

??"??.??*??

=

1??/

$"%????$!*??%??

??

因此

??

????#??/??

??

11??/

????"??*??>??

??

??

=??/

??????????????""")"所以"????????*??*??/??*??/??*??

++??/????

两互素"进而??*??*??至少有+个不同的素因子!

??+??/

??

/??

+??/

*??两

例??且1的所有正因数之积等于+的所有正因数之+是正整数"??设1!问(积!1与+是否必须相等+

解??1与+必须相等!

#$

事实上"将1的正因数4与配对"可知1的所有正因数之积为1??"

4

因此"条件等价于

????????

4#1$4#+$"1%+

??

此式表明1!可设+有相同的素因子"

??????????)??3??????)??3

1%2+%222??2??3"??2??3"

其中2????0??3!??????2????)??23为素数"0与0都是正整数"??

代入??式"利用算术基本定理"可知

"4#1$4#+$????0??3"%????00

??

""故若4#则对????0??3"都有??于是"1$+$??0????0"0*??????0*????4#

#$#$)#$$#$)#$"这导致4#1$??????????*????*??3*????*????*??3*????#??????""利用??式也可导出矛盾!矛盾!同样"由4#所以4#4#+$1$??4#+$1$%

"进而由??式得1%+!4#+$###说明??一般地"由??即考虑1!并不能导1$+$+所有正因数之和$%??

#$#$"例如??此题是对两个正整数的所有正因数作乘出1%+#????????$%??%??积方面的思考得出的结论!

例??使得??求所有的正整数(!)"

(+!

!%()

??

??#??$)??3解!设(!并且(%2(的素因数分)为满足条件的正整数"2#2$3为

解式"则

+!??(

+!??(

+!??)%#$

()3!

由)为正整数"知对#'0'3"都有(&现在先讨论(的素因子!+!??0!

??

如果(有一个不同于$和+的素因子2"并设2那么由前面的结果("-????!"知(&当然有2又2#$故2但是"对任意素数2及正+!+!+&&??"??"??!

????

整数??"有2所以"这表明(的素因子只能为$或+!&??不能成立"2%??"

????#"/于是"我们可设(%$其中??!这时(++!(+!&&??"??为非负整数$??"

#$//????????故$前者要求$后者要求+注意到"当??&'时"+!++!&&&&??"??"??"??!

#$//????"而??&'时"所以"这表明(只能$+!'??'$!'??'$!%??"%??"

$""$"$$"$$""""取#$$++$.+$$.+$.+!.+

"$"将(的上述取值逐个代入??式"可得到全部解为#("##)$%#

$+$$"$#!$$"-$+$#""#"#""#""#"$"#"$"$$$$+$++++"##!#!+!+!#!!#!

共(组解!

说明!上面两例直接用到算术基本定理"所涉及的变量数看似增加或会变难"但这时不等式估计的手段可介入"问题求解反而有了着力点!

")"#)"例??设4满足(4444!给定正整数+%##"$"+都是正整数"#"$"

+0%#

+0%#

??????!

""")"且对<%#这里.44$+都有44%#+$0#0%4#*4$*)*<&.

4!+$

+

+$/#$证明(#444#$)+&#0$%.4

0%#

#$举例说明(上式右边的幂次不能减小!$+%$时"

$设2为4#证明!#且3为各4#44$)+的素因数"0的素因数分解式中2

+

3

0#%

+

#$3+$/

+

+$/

&#0$!.40#%

+

的幂次的最大值"则由4故242&.40可知"0"<&.

0#%

)""而#故存在4使得24结合2可知4444%#&.4#"$"+$0"0"0"#"

0#%

)"所以"44442在4#$"+中至少有两个数不是2的倍数!$)+中的幂次不

$"超过3#依此可知结论成立!+"$

+

#$设4"""#$则.4是每$4#4''0'+"+/##%#$%+/0%+0%+

0#%

)"个4且#444!%#0的倍数"0"$"+$

整除

+$#+$#//$"$"此时"结合#可知满足+444+/#+"+/#+/%##$)+%+

1$$$的最小正整数1%+/$#+#+/#!&#

????????习题??

-+证明(是一个合数!!设+为大于#的正整数!+*-

$"求使得&-($(/$,/#&为素数的所有整数(!

$,*#且1&#证明(#设1为大于#的正整数"1/#!1是一个素数!

使得下面的整除关系都成立+$是否存在'个不同的素数2!9"$!

$$$9&99*4"*4"*4"$22&$2$&

$%#$其中##4%#!$4%##!

2且$求证(%设2为正整数"/#是素数!2为素数!

+3且$证明(存在非负整数3"使得+%$&设+为正整数"!*#是素数!

+#)的素数"这里+为正整数!.求所有形如+!*#且不超过#

!!"且"??'证明(/设"!#'4都是整数""/'"#*'4!"/'"4*#'!&&!且"证明(0设"!#!'4为整数"'!#'*"4!#4都是某个整数,的倍数!

????????数#'和"4也是,的倍数!

+!!$"且对任意正整数3#都有#/证!1设"#+为给定的正整数"3"/3!&??#

+明("%#!

""")"末尾数字为!!!已知正整数+的正因数中"#$)的正整数都至少有

一个!求满足条件的最小的+!

"")"使得?的数码两两不同且都不为零"并对1%$!"求一个)位数?"'

"数?的左边1位数都是1的倍数!)

若存在正整数"!使得+%"则称+是一!#对于一个正整数+"#"#*"*#"

"""")"个&好数'例如'%#故'为一个&好数'问(在####!$#!!.**

+中"有多少个&好数'

)!证明(当+??$时"数2!$设素数从小到大依次为2222#"$"'"+*+#可*

以表示为'个大于#的正整数#可以相同$的乘积的形式!

证明(!%设+为大于#的正整数!+为合数的充要条件是存在正整数"!#!

使得+%"*#(!!*%#)""#

""")中"数列#每一个数都是!&证明(!!!##!!!#!!!##!!!#!!!#!!!#

合数!

$$$$且"??'!.设"!#!'!4都是素数"#??%'??#$4""#'4,-)!/*/%#

$$$$求"的所有可能值!#'***4

的每一项都是正整数"且对任意正整数3"该!/数列0""""+1#??$??'??)"

数列中恰有3项等于3!求所有的正整数+"使得"""#*$*)*+是素数!

满足(对任意正整数1!若1&则!0由正整数组成的数列0"+"+"1??+"+1

且"求"""1&+"1??"+!$!!!的最小可能值!

证明(正整数1!"1设2为奇素数"+满足%#**)*!1!2&+$2/#

1+"且"证明("!设"!1!+为正整数""??#"!1&+!*#&*#

1+"$对任意正整数+及正奇数1"都有#""证明($$!/#*#%#$证明(对任意两个不同的正整数1!都"#费马数;#!+"+定义为;+%$*

有#;;!%#+"1$+

!证明("$已知正整数"!#!'4的最小公倍数为"*#*'*4!"#'4是'或

+的倍数!

"")"$"求所有的正整数+#使"%记?+为正整数#$+的最小公倍数!??#

得?+%?+/#!

#"$1+#"$证明("&设"!1!+为正整数""??#!""!/#/#%"1+/#++"$且"证明(".设"!+为正整数""??#4#"*#是素数!/#??+!

$"存在+个连续正整数"使得其中最大的数是其"/对怎样的正整数+#??$

余+/#个数的最小公倍数的因数+!"*??

11++#$""且"证明("0设正整数"!#!1!+满足(""#"??##"#!%#*&*

1&+!

存在$使得其中任意两个不同的数"!#1证明(!#$个不同的正整数"#都满

$$足#"/#"#!&

$且#证明(对任意正整数1"数列#!设"!#为正整数"""#!%#

"""*#""*$#")""*+#")

中"有无穷多个数与1互素!

"#/满足(数"在十进制表示下"末尾恰有)#"已知正整数数对#""#$#(个

零!求"#的最小值!

-使得1%4###求所有的正整数1"1$!

每一个正整数都可以表示为两个正整数之差"且这两个正整数的素#$证明(

因子个数相同!

$$!"使得"且满足#%求所有的正整数"!#'*#和#*#都是素数"

$$$#$#$"#!*#*#%'*#

整除

表示正整数3的最大奇因数!都有证明(对任意正整数+"#&用2#3$('+$##$!(+*#.'3%#3

".".".---!!求代数式#.设""#'都是大于#的正整数!$"*#*'

的最小可能值!

$"有多少个整数组#使得#/对任意给定的素数2"""#"'

$%#$##'""#"''$2

$.-.-""/#$'!%$"*#2*$

"")"每次允许进行下面的操作(从黑板上任取两#0黑板上写着数#$''!

将它们从黑板上去掉"写上数!个满足(直至黑板上不存$)的数(!)"(

在这样的两个数!问(黑板上至少剩下多少个数+

+$+'+-+证明(数#是一个合数!$1设+是一个正整数!*+*+*+*+

??????!

?

《数学奥林匹克小丛书》?

?

以专家讲座的形式展开

?

由浅入深、夹叙夹议、讲练结合

?在知识学习中实现能力培养?

薄薄的小册子助你透析每一个专题?从奥委会委员到国家队教练?从大学教授到金牌教练员?

聚集了国内最顶尖的奥数辅导专家?

为你打造了一套最经典奥数专题辅导丛书?

数学奥林匹克小丛书(第二版)初中卷?

?

初中卷1

因式分解技巧方程与方程组

单墫?著

初中卷2初中卷3初中卷4初中卷5初中卷6初中卷7初中卷8?

葛军?编著

一次函数与二次函数?三角形与四边形?圆

李惟峰?编著沈文选?编著柯新立?编著

整除、同余与不定方程组合趣题

冯志刚?著

周建新?编著

初中数学竞赛中的解题方法与策略冯志刚?顾滨?主编

·高中卷?数学奥林匹克小丛书(第二版)高中卷高中卷高中卷高中卷4高中卷5高中卷6高中卷7高中卷高中卷集合

刘诗雄?编著

函数与函数方程三角函数

熊斌?朱臻?苏勇?编著曹瑞彬?周益忠?编著

平均值不等式与柯西不等式不等式的解题方法与技巧数列与数学归纳法平面几何

李胜宏?边红平?编著苏勇?熊斌?编著冯志刚?著

范端喜?邓博文?编著

复数与向量几何不等式

张思汇?编著冷岗松?著余红兵?著张垚?编著

高中卷10高中卷11高中卷12高中卷13高中卷?

??

数论图论

组合数学

熊斌?郑仲义?编著

组合极值冯跃峰?编著

高中数学竞赛中的解题方法与策略熊斌?何忆捷?编著

?

?

?学奥数,这里总有一本适合你?

?

自从2000年《奥数教程》中首次在图书中使用“奥数”一词以来,华东师范大学出版社已陆续出版近200种“奥数”图书,?形成多品种、多册层次全系列。??

?“奥数”域外篇——《日本小学数学奥林匹克》、《全俄中学生数学奥林匹克》 ?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com