数论（数学奥林匹克）

书书书 目　　录 !!"!!!! 目!!录 " ! 整除 $$0 " 最大公约数与最小公倍数 $$2 # 素数及唯一分解定理 $00 $ 不定方程&一' $04 % 竞赛问题选讲&一' $#A & 同余 $!! ' 几个著名的数论定理 $AA ( 阶及其应用 $2$ ) 不定方程&二' $23 !* 竞赛问题选讲&二' $"! !!习题解答 $32 书书书 整　　除 !!"!!!! "!整!!除 " 本书中所涉及的数都是整数!所用的字母除特别申明外也都表示整数! 设""#是给定的数!##!!若存在整数$!使得"%#$!则称#整除"!记 作#$"!并称#是"的一个约数#或因子$!而称"为#的一个倍数!如果不存在 上述的整数$!则称#不能整除"!记作#$"! 由整除的定义!容易推出整除的几个简单性质#证明请读者自己完成$% #"$若#$$!且$$"!则#$"!即整除性质具有传递性! ##$若#$"!且#$$!则#$#"$$$!即为某一整数的倍数的整数之集关于 加"减运算封闭! 反复应用这一性质!易知%若#$"及#$$!则对任意整数&"'有#$#"&% $'$!更一般地!若""!"#!&!"(都是#的倍数!则#$#""%"#%&%"($! #&$若#$"!则或者"%!!或者)")%)#)!因此!若#$"且"$#!则 )")%)#)! 对任意两个整数""###&!$!"当然未必被#整除!但我们有下面的结 论'''带余除法!这是初等数论中最为基本的一个结果! #'$#带余除法$设""#为整数!#&!!则存在整数*和+!使得 "%#*,+!其中!'+(#! 并且*和+由上述条件唯一确定! 整数*称为"被#除得的#不完全$商!数+称为"被#除得的余数!注 意!+共有#种可能的取值%!!"!&!#("!若+%!!即为前面说的"被#整 除的情形! 易知!带余除法中的商*实际上为 "( )# #不超过"#的最大整数$!而带余 除法的核心是关于余数+的不等式%!'+(#!我们在后面将看到这一点! 证明#$"的基本手法是将"分解为#与一个整数之积!在较初级的问题 中!这种数的分解常通过在一些代数式的分解中取特殊值而产生!下面两个 分解式在这类论证中应用很多! !!#!!!! "!!数!!论 #)$若(是正整数!则 -(./( %#-./$#-(.",-(.#/,&,-/(.#,/(."$! #*$若(是正奇数!则#在上式中用(/代换/$ -(,/( %#-,/$#-(.".-(.#/,&.-/(.#,/(."$! 例!!证明%"!&* ! #!!个! "被"!!"整除! 证明!由分解式#*$!我们有 "!& * ! #!!个! "%"!#!","%#"!&$*+," %#"!&,"$(#"!&$**.#"!&$*),&."!&,")! 所以!"!&,"#%"!!"$整除"!&* ! #!!个! "! 例"!设0&(%!!证明%### ( ,"$)### 0 ."$! 证明!在分解式#)$中取-%## (,"!/%"!并以#0((("代替那里的(! 得出 ## 0 ."%### (," ."$(### (,"$#0.(.".",&,## (," ,")! 故 ### (," ."$)### 0 ."$! 又 ## (," ."%### ( ."$### ( ,"$! 从而 ### ( ,"$)### (," ."$! 于是由整除性质#"$知### ( ,"$)### 0 ."$! 注!整除问题中!有时直接证明#$"不易入手!我们可以尝试着选择适当 的+中间量,$!来证明#$$及$$"!由此及整除性质#"$!便导出了结论! 例#!对正整数(!记1#($为(的十进制表示中数码之和!证明%,$(的充 分必要条件是,$1#($! 证明!设(%"23"!2,&,""3"!,"!#这里!'"4',!且"2#!$! 则1#($%"!,"",&,"2!我们有 (.1#($%"2#"!2."$,&,""#"!."$! ! 对"'4'2!由分解式#)$知,$#"!4("$!故!式右端2个加项中的每一 个都是,的倍数!从而由整除性质##$知!它们的和也被,整除!即,$#(( 1#($$!由此易推出结论的两个方面! !!$!!!! "!整!!除 " 注!!整除性质##$提供了证明#$#""%"#%&%"($的一种基本的想法! 我们可尝试着证明更强的#也往往是更易于证明的$命题% #整除每个"4#4%"!#!&!($! 这一更强的命题当然并非一定成立!即使在它不成立时!上述想法仍有 一种常常奏效的变通%将和""%"#%&%"(适当地分组成为$"%$#%&%$2! 而#$$4#4%"!#!&!2$!读者将看到!为了证明#$"!我们有时针对具体问题 将"表示为适当数之和!以应用上述想法论证! 注"!例&的证明!实际上给出了更强的结论%对任意正整数(!数(与 1#($之差总是,的倍数!由此易知!(与1#($被,除得的余数相同#这可表述 为(与1#($模,同余!请看第*单元$! 注#!有些情形!我们能够由正整数十进制表示中的数码#字$的性质!推 断这整数能否被另一个整数整除!这样的结论!常称为+整除的数字特征,!被 #")""!整除的数的数字特征是显而易见的!例&则给出了被,整除的数的 数字特征!这一结果!应用相当广泛而且灵活多样!另外!习题"第&题给出了 被""整除的数的数字特征!这也是一个应用较多的结论! 例$!设2%"是一个奇数!证明%对任意正整数(!数"2%#2%&%(2不 能被(%#整除! 证明!(%"时结论显然成立!设(%#!记所说的和为5!则 #5%#,##2,(2$,#&2,#(."$2$,&,#(2,#2$! 因2是正奇数!故由分解式#*$可知!对每个4%#!数42%#(%#(4$2被 4,#(,#.4$%(,#整除!故#5被(%#除得的余数是#!从而5不可能被 (%#整除#注意(,#&#$! 注!论证中我们应用了+配对法,!这是代数中变形和式的一种常用手法! 例%!设0"(为正整数!0&#!证明%##0."$)##(,"$! 证明!首先!当('0时!易知结论成立!事实上!0%(时!结论平凡- ((0时!结果可由#(,"'#0.","(#0."推出来#注意0&#!并参看 整除性质#&$$! 最后!(&0的情形可化为上述特殊情形%由带余除法!(%0*,+!!' +(0!而*&!!由于 #(,"%##0*."$#+,#+,"! 由分解式#)$知##0."$)##0*."$-而!'+(0!故由上面证明了的结论知 ##0("$$##+%"$!#注意+%!时!结论平凡!$从而当(&0时也有##0("$$ !!%!!!! "!!数!!论 ##(%"$!这就证明了本题结论! 我们顺便提一下!例)中的条件0&#是必要的!因为当0%#时!#0. "%&!而由#*$知!对于所有奇数(%"!数#(%"均被&整除! 例&!任给(&"!证明%有正整数"!使得""%"!"" " %"!&中所有数均 被(整除! 解!我们注意!若"是奇数!则""!"" "!&均是奇数!从而由#*$知!""% "!"" " ,"%"#" "$,"!&均有因子"%"!因此取"%#(."则符合问题中的 要求! 例'!任给(%#!证明%存在(个互不相同的正整数!其中任意两个的 和!整除这(个数的积! 解!我们任取(个互不相同的正整数""!&!"(!并选取一个#正整数$ 参数6!希望6""!&!6"(的积6(""&"( 被任意两项的和6"4%6"7 整除 #"'4!7'(!4#7$!由于(%#!显然!取 6% ) "'4(7'( #"4,"7$ 即符合要求#注意6""!&!6"(互不相同$! !!! !习 题 ! ! 设(和2都是正整数!则"!#!&!(中恰有 (( )2 个数被2整除! " ""个女孩与(个男孩去采蘑菇!所有这些孩子共采到(#%,((#个蘑菇! 并且每个孩子采到的个数都相同!试确定!采蘑菇的孩子中是女孩多还是 男孩多! # 设正整数(的十进制表示为(%"2&"""! #!'"4 ',!"2 #!$!记 8#($%"!."",&,#."$2"2 #由(的个位起始的数码的正"负交错 和$!证明((8#($被""整除!由此得出被""整除的数的数字特征%""整 除(的充分必要条件是""整除8#($! $ 设(个整数具有下述性质%其中任意(("个数之积与剩下那个数的差都 能被(整除!证明%这(个数的平方和也能被(整除! % 设整数""#"$"9满足"9.#$&"!证明%""#"$"9中至少有一个数不 被"9(#$整除! 最大公约数与最小公倍数 !!&!!!! #!最大公约数与最小公倍数 " 最大公约数是数论中的一个重要概念! 设""#不全为零!同时整除""#的整数#如$"$称为它们的公约数!因 ""#不全为零!故由第"单元中性质#&$推知!""#的公约数只有有限多个!我 们将其中最大的一个称为""#的最大公约数!用符号#"!#$表示!显然!最大 公约数是一个正整数! 当#"!#$%"时#即"!#的公约数只有$"$!我们称"与#互素#互质$! 读者在后面将看到!这种情形特别重要! 对于多于两个的#不全为零的$整数"!#!&!$!可类似地定义它们的最 大公约数#"!#!&!$$!若#"!#!&!$$%"!则称"!#!&!$互素!请注意! 此时并不能推出"!#!&!$两两互素#即其中任意两个都互素$-但反过来! 若"!#!&!$两两互素!则显然有#"!#!&!$$%"! 由定义不难得出最大公约数的一些简单性质% 任意改变""#的符号不改变#"!#$的值!即有#:"!:#$%#"!#$- #"!#$关于""#对称!即有#"!#$%##!"$- #"!#$作为#的数!以"为周期!即对任意整数-!有#"!#,"-$%#"!#$! 下面#"$中的结论!是建立最大公约数的性质的基础!通常称为裴蜀等式! #"$设""#是不全为!的整数!则存在整数-"/!使得 "-,#/%#"!#$! 顺便提及!若-%-!!/%/!是满足上式的一对整数!则等式 "#-!,#&$,##/!."&$%#"!#$#&为任意整数$ 表明!满足上式的-"/有无穷多组-并且!在"#&!时!可选择-为正#负$ 数!此时/则相应地为负#正$数! 由#"$易于推出下面的 ##$两个整数""#互素的充分必要条件是存在整数-"/!使得 "-,#/%"! !!'!!!! "!!数!!论 事实上!条件的必要性是#"$的特例!反过来!若有-"/使等式成立!设 #"!#$%9!则9$"且9$#!故9$"-及9$#/!于是9$#"-%#/$!即9$"!从而 9%"! 由#"$及##$不难导出下面的几个基本结论% #&$若0$"!0$#!则0$#"!#$!即""#的任一个公约数都是它们的最大 公约数的约数! #'$若0&!!则#0"!0#$%0#"!#$! #)$若#"!#$%9!则 "9 !## $9 %"!因此!由两个不互素的整数!可自然 地产生一对互素的整数! #*$若#"!0$%"!##!0$%"!则#"#!0$%"!这表明!与一个固定整 数互素的整数之集关于乘法封闭!由此可推出%若#"!#$%"!则对任意2&! 有#"2!#$%"!进而对任意;&!有#"2!#;$%"! #+$设#$"$!若##!$$%"!则#$"! #-$设正整数""#之积是一个整数的2次幂#2%#$!若#"!#$%"!则 ""#都是整数的2次幂!一般地!设正整数"!#!&!$之积是一个整数的2 次幂!若"!#!&!$两两互素!则"!#!&!$都是整数的2次幂! #*$"#+$"#-$表现了互素的重要性!它们的应用也最为广泛! 现在!我们简单地谈谈最小公倍数! 设""#是两个非零整数!一个同时为""#倍数的数称为它们的一个公倍 数!""#的公倍数显然有无穷多个!这其中最小的正数称为""#的最小公倍 数!记作("!#)!对于多个非零整数"!#!&!$!可类似地定义它们的最小公 倍数("!#!&!$)! 下面是最小公倍数的主要性质! #,$"与#的任一公倍数都是("!#)的倍数!对于多于两个整数的情形! 类似的结论也成立! #"!$两个整数""#的最大公约数与最小公倍数满足 #"!#$("!#)%)"#)! 但请注意!对于多于两个整数的情形!类似的结论不成立#请读者举出例 子$!然而我们有下面的 #""$若"!#!&!$两两互素!则有 ("!#!&!$)%)"#&$)! 由此及#,$可知!若"$9!#$9!&!$$9!且"!#!&!$两两互素!则有"#&$$9! !!(!!!! #!最大公约数与最小公倍数 " 互素!在数论中相当重要!往往是许多问题的关键或基础!竞赛中! 有一些问题要求证明两个整数互素#或求它们的最大公约数$!下面几个例子 表现了处理这些问题的一个基本方法! 例!!对任意整数(!证明分数#"(%'"'(%&是既约分数! 证明!问题即要证明#"(%'与"'(%&互素!易知这两数适合裴蜀等式 &#"'(,&$.###"(,'$%"! 因此所说的结论成立! 一般来说!互素整数""#适合的裴蜀等式不易导出!因此我们常采用下 述的变通手法%制造一个与裴蜀等式类似的辅助等式 "-,#/%+! 其中+是一个适当的整数!若设#"!#$%9!则由上式知9$+!所谓适当的+是 指%由9$+能够通过进一步的论证导出9%"!或者+的约数较少!可以由排 除法证得结论! 此外!上述辅助等式等价于"$##/(+$或#$#"-(+$!有时!这些由整除更 容易导出来! 例"!设(是正整数!证明#(.,"!#(,"$.,"$%"! 证明!我们有等式 #(.,"$#(,"$.##(,"$.,"$%(! ! 设9%#(.,"!#(,"$.,"$!则由!知9$(! 进一步!因9$(故9$(.!结合9$#(.%"$可知9$"!故9%"! 例#!记<2 %## 2 ,"!2%!!证明%若0#(!则#<0!<($%"! 证明!不妨设0&(!论证的关键是利用<()#<0.#$#见第"单元例 #$!即有一个整数-!使得 <0,-<( %#! 设9%#<0!<($!则由上式推出9$#!所以9%"或#!但<( 显然是奇 数!故必须9%"! 注!<2#2%!$称为费马#./0123$数!例&表明!费马数两两互素!这是 费马数的一个有趣的基本性质! 下面例'的结论用处颇多!值得记住! 例$!设"&"!0!(&!!证明% #"0."!"(."$%"#0!($."! !!)!!!! "!!数!!论 证明!设= % #"0 ."!"(."$!我们通过证明#"#0!($("$$= 及=$ #"#0!($("$来导出=%"#0!($."!这是数论中证明两数相等的常用手法! 因为#0!($$0!#0!($$(!由第"单元中分解#)$即知#"#0!($("$$ #"0("$!以及#"#0!($("$$#"(("$!故由本单元的性质#&$可知!"#0!($("整 除#"0("!"(("$!即#"#0!($("$$=! 为了证明=$#"#0!($("$!我们设9%#0!($!因0!(&!!故可选择&! '&!!使得#参见本单元#"$中的注释$ 0&.('%9! ! 因为=$#"0("$!故更有=$#"0&("$!同样!=$#"('("$!故=$#"0&( "('$!从而由!!得 =)"('#"9."$! " 此外!因"&"!及=$#"0("$!故#=!"$%"!进而#=!"('$%"!于是! 从"及性质#+$导出=$#"9("$!即=$#"#0!($("$! 综合已证得的两方面的结果!可知=%"#0!($."! 例%!设0!(&!!0()#0#,(#$!则0%(! 证明!设#0!($%9!则0%0"9!(%("9!其中#0"!("$%"! 于是!已知条件化为0"("$#0#"%(#"$!故更有0"$#0#"%(#"$!从而0"$(#"! 但 #0"!("$%"!故#0"!(#"$%"!结合0"$(#"!可知必须0"%"!同理("% "!因此0%(! 注!!对两个给定的不全为零的整数!我们常借助它们的最大公约数!并 应用性质#)$!产生两个互素的整数!以利用互素的性质作进一步论证#参见 性质#*$"#+$$!就本题而言!由于0(为二次式!0#%(#为二次齐次式!上述 手续的功效!实质上是将问题化归成0"(互素这种特殊情形! 注"!在某些问题中!已知的条件#或已证得的结论$$$"并不适用!我们 可试着选取$的一个适当的约数#!并从$$"过渡到#较弱的结论$#$"!以期望 后者提供适宜于进一步论证的信息!例)中!我们便是由0"("$#0#"%(#"$产生 了0"$(#"!进而导出0"%"! 例&!设正整数""#"$的最大公约数为"!并且 "# ".#%$! 证明%"(#是一个完全平方数! 证明! 设#"!#$%9!则"%9""!#%9#"!其中#""!#"$%"!由于#"! #!$$%"!故有#9!$$%"! !!*!!!! #!最大公约数与最小公倍数 " 现在!问题中的等式可化为 9""#"%$"".$#"! ! 由此可见""整除$#"!因#""!#"$%"!故""$$!同样得#"$$!再由#""!#"$% "便推出""#"$$#参考性质#,$与#"!$$! 设$%""#"2!其中2是一个正整数!一方面!显然2整除$-另一方面!结 合!式得9%2#"".#"$!故2$9!从而2$#$!9$#见性质#&$$!但#$!9$%"! 故2%"! 因此9%"".#"!故".#%9#"".#"$%9#!这就证明了"(#是一个 完全平方数! 注!借助素数!则可以给予本题一个更为直接的证明#参考第&单元例' 的解法!$! 例'!设2为正奇数!证明%"%#%&%(整除"2%#2%&%(2! 证明!因为",#,&,(%( #(,"$ # !故问题等价于证明%(#(%"$整除 ##"2%#2%&%(2$!因(与(%"互素!所以这又等价于证明 ()##"2,#2,&,(2$ 及 #(,"$)##"2,#2,&,(2$! 事实上!由于2为奇数!故由第"单元中分解公式#*$!可知 !##"2,#2,&,(2$ %("2,#(."$2),(#2,#(.#$2),&,(#(."$2,"2),#(2 是(的倍数!同理! ##"2,#2,&,(2$%("2,(2),(#2,#(."$2),&,((2,"2) 是(%"的倍数! 注!整除问题中!有时直接证明#$"不易入手!若#可分解为#%#"##! 其中##"!##$%"!则我们可将原命题#$"分解为等价的两个命题#"$"及##$ "!后者可能更容易导出来!例+应用了这一基本手法!例*中证明""#"$$也 是这样做的! 更一般地!为了证明#$"!可将#分解为若干个两两互素的整数#"! ##!&!#(之积!而证明等价的#4$"#4%"!#!&!($#参见性质#""$!并可比 较第"单元例&的注"中说的想法$!关于这种手法的一种应用!请参考 !"!!!! "!!数!!论 第&单元例)! !!! !习 题 " ! 设(为整数!证明%#"#(,)!,(,'$%"! " 设0"(都是正整数!0是奇数!证明%##0 ."!#(,"$%"! # 设#"!#$%"!证明%#"#,##!"#$%"! $ 若一个有理数的2次幂是整数#2%"$!则这有理数必是整数!更一般地! 证明%一个首项系数为$"的整系数多项式的有理数根!必定是一个 整数! % 设0"("2都是正整数!满足(0,2!0)%((,2!()!证明%0%(! 素数及唯一分解定理 !""!!! $!素数及唯一分解定理 " 大于"的整数(总有两个不同的正约数%"和(!若(仅有这两个正约数#称 (没有真因子$!则称(为素数#或质数$!若(有真因子!即(可表示为"/#的 形式#这里""#为大于"的整数$!则称(为合数!于是!正整数被分成三类% 数"单独作一类!素数类及合数类! 素数在正整数中特别重要!我们常用字母>表示素数!由定义易得出下 面的基本结论% #"$大于"的整数必有素约数! 这是因为!大于"的整数当然有大于"的正约数!这些约数中的最小数必 然没有真因子!从而是素数! ##$设>是素数!(是任意一个整数!则或者>整除(!或者>与(互素! 事实上!>与(的最大公约数#>!($必整除>!故由素数的定义推知!或 者#>!($%"!或者#>!($%>!即或者>与(互素!或者>$(! 素数的最为锐利的性质是下面的 #&$设>是素数!""#为整数!若>$"#!则""#中至少有一个数被> 整除! 实际上!若>不整除"和#!则由上述的##$!>与""#均互素!从而>与 "#互素#见第#单元#*$$!这与已知的>$"#相违. 由#&$特别地推出!若素数>整除"(#(%"$!则>$"! 关于素数的最为经典的一个结果是公元前欧几里得证明的% #'$素数有无穷多个! 我们用反证法来证明这一事实!假设素数只有有限多个!设全体素数为 >"!>#!&!>2!考虑数?%>">#&>2,"!显然?&"!故?有素因子>!因 >"!>#!&!>2是全部素数!故>必等于某个>4#"'4'2$!从而>整除?( >">#&>2!即>整除"!这不可能!因此素数有无穷多个!#请注意!>"&>2%" 并不一定是素数!$ #'$中的断言!也可由第#单元例&推出来%设<2 %## 2 ,"#2%!$!则 !"#!!! "!!数!!论 <2&"!故<2有素约数!因已证明无穷数列0<21#2%!$中的项两两互素!故 每个<2 的素约数与这个数列中其他项的素约数不同!因此素数必有无穷 多个! 现在我们转向初等数论中最为基本的一个结果!即正整数的唯一分解定 理!也称为算术基本定理!它表现了素数在正整数集合中的真正分量! #)$#唯一分解定理$每个大于"的正整数均可分解为有限个素数的积- 并且!若不计素因数在乘积中的次序!这样的分解是唯一的! 换句话说!设(&"!则(必可表示为(%>">#&>2!其中>4#"'4'2$ 都是素数-并且!若(有两种素因数分解 (%>">#&>2 %*"*#&*;! 则必有2%;!并且>"!>#!&!>2是*"!*#!&!*;的一个排列! 将(的素因数分解中的相同的素因子收集在一起!可知每个大于"的正 整数(可唯一地表示为 (%>!"">!##&>!22 ! 其中>"!>#!&!>2是互不相同的素数!!"!!#!&!!2是正整数!这称为(的 标准分解! 若已知正整数(的#如上所述的$标准分解!则由唯一分解定理!可确定其 全部的正约数% #*$(的全部正约数为>""">"##&>"22 !其中"4是满足!'"4'!4#4%"!&! 2$的任意整数! 由此易知!若设##($为(的正约数的个数!$#($为(的正约数之和!则有 ##($%#!","$#!#,"$&#!2,"$! $#($%> !","" ." >"." /> !#,"." >#." /&/> !2,"." >2." ! 虽然素数有无穷多!但它们在自然数中的分布却极不规则#参见习题&第 "题$!给定一个大整数!判定它是否为素数!通常是极其困难的!要作出其标 准分解!则更为困难!下面#+$中的结果相当有趣!它对任意(&"!给出了(. 的标准分解! #+$对任意正整数0及素数>!记号>!*0表示>!)0!但>!%"$0!即>! 是0的标准分解中出现的>的幂! 设(&"!>为素数!>!>*(.!则 !"$!!! $!素数及唯一分解定理 " !> %+ 4 ;%" ( >( ); % (( )> , (>( )# ,# $& ! 这里(-)表示不超过实数-的最大整数!请注意!由于当>;&(时!(>( ); %!! 故上面和式中只有有限多个项非零! 证明某些特殊形式的数不是素数#或给出其为素数的必要条件$!是初等 数论中较为基本的问题!在数学竞赛中尤为常见!处理这类问题的基本方法 是应用#各种$分解技术!指出所说数的一个真因子!我们举几个这样的例子! 例!!证明%无穷数列"!!!"!"!!!"!!!"!&中没有素数! 证明! 记"( %"!!!"&,- ."!!!" (个" #(%#$!则 "( %","!',"!-,&,"!'#(."$%"! '(." "!'." ! 为了将上式右端的数分解为两个#大于"的$整数之积!我们区分两种情形% (为偶数!设(%#2!则 "#2 %"! -2." "!'."% "!-2." "!-." /"! -." "!'." ! 易知!"! -(" "!'(" 是大于"的整数!而对2%#!"! -2(" "!-(" 也是大于"的整数!故 "#2#2%#!&!&$都是合数!又"#%"!!!"%"&3"&+是合数! (为奇数!设(%#2,"!则 "#2,"%"! '##2,"$." "!'." % "!###2,"$." "!#." /"! ###2,"$," "!#," 是两个大于"的整数之积!故"#2%"也均是合数!因此!所有"(是合数! 注!例"的论证中!数的符合要求的分解!是应用代数式的分解实现的 #第"单元分解公式#)$和#*$$!下面的例#也是这样做的! 例"!证明%对任意整数(&"!数('%'(不是素数! 证明!若(为偶数!则('%'(大于#且均被#整除!因此都不是素数!但对 奇数(!易知('%'(没有一个#大于"的$固定的约数!我们采用不同的处理% 设奇数(%#2,"!2%"!则 (','( %(','/'#2 %(','/##2$' %(','(#/##2$#,'/##2$'.'(#/##2$# %#(#,#/##2$#.##/(/#2$# %#(#,#2,"(,##2,"$#(#.#2,"(,##2,"$! !"%!!! "!!数!!论 上式右边第一个因数显然不为"!而后一个因数为#((#2$#%##2也不是" #因2%"$!故('%'(对(&"都是合数! 例#看上去平平常常!但自己动手做却未必顺顺当当!这一解法的关键! 是在(为奇数时!将'(看作单项式'/'!以利用代数式的分解 -','/'%#-#,#/#,#-/$#-#,#/#.#-/$! 产生数的适用的分解! 例#!设正整数""#"$"9满足"#%$9!证明%"%#%$%9不是素数! 证明一!本题不宜用代数式的分解来产生所需的分解!我们的第一种解 法是应用数的分解!指出"%#%$%9的一个真因子! 由"#%$9!可设"$ % 9 # % 0 ( !其中0和(是互素的正整数!由"$ % 0 ( 意味着有理数"$的分子 "分母约去了某个正整数&后!得到既约分数0( !因此 "%0&!$%(&! ! 同理!有正整数'!使得 #%('!9%0'! " 因此!",#,$,9%#0,($#&,'$是两个大于"的整数之积!从而不 是素数! 注!若正整数""#"$"9适合"#%$9!则""#"$"9可分解为!及"的 形式!这一结果!在某些问题中颇有用处! 证明二!由"#%$9!得!#%$9"! 因此 ",#,$,9%",$9" ,$,9% #",$$#",9$ " ! 因"%#%$%9是整数!故 #"%$$#"%9$ " 也是整数!若它是一个素数 !设 为>!则由 #",$$#",9$%"> # 可见!>整除#"%$$#"%9$!从而素数>整除"%$或"%9!不妨设>$#"%$$! 则",$%>!结合#推出",9'"!而这不可能#因9%"$! 证明二的论证!应用素数的性质#见#&$$并由反证法导出结果!这与前面 的手法很不相同! !"&!!! $!素数及唯一分解定理 " 例$!证明%若整数""#满足#"#,"%&##,#!则"(#和#"%##%"都 是完全平方数! 证明!已知关系式即为 #".#$##",##,"$%##! ! 论证的第一个要点是证明整数"(#与#"%##%"互素!记9% #".#! #",##,"$!若9&"!则9有素因子>!从而由!知>$##!因>是素数!故 >$#!结合>$#"(#$知>$"!再由>$##"%##%"$导出>$"!这不可能!故 9%"!因此!由于!的右端为##!是一个完全平方数!故$"(#$与$#"%##% "$均是完全平方数#参见第#单元的#-$$! 现在证明".#%!!从而由!知#",##,"%!!于是"(#及#"%##% "均是完全平方! 假设有整数"!#满足问题中的等式!但".#(!!因已证明$"(#$是一 个完全平方数!故有#."%+#!这里+&!-结合!推出+$#!再由#."%+# 知+$"!设#%#"+!"%""+!代入问题中的等式可得到#注意+&!及#"% "",+$ "#",*""+,&+#,"%!! " 为了证明上式不可能成立!可采用下面的办法% 将"看作是关于""的二次方程!由求根公式解得 ""%.&+: *+#.槡 "! 因""为整数!故由上式知*+#("为完全平方数!但易知一个完全平方数被& 除得的余数只能为!或"-而*+#("被&除得的余数为#!产生矛盾! 或者更直接地%由于"#"被&除得的余数为!或"!故"左边被&除得的余 数是"或#-但"的右边为!!被&整除!矛盾!即"对任何整数""及+均不成 立!从而必须有".#%!!这就证明了本题的结论! 注!!许多数论问题需证明一个正整数为"#例如!证明整数的最大公约 数是"$!本单元的#"$给出了整数是否为"的一个数论刻画!由此!我们常假 设所说的数有一个素因子!利用素数的锐利性质#&$作进一步论证!以导出矛 盾!例'便是这样的一个例子! 注"!上述证明"不成立的论证!实质上应用了同余#比较余数$的想法! 这是证明两个整数不等的一种基本的手法!请参见第*单元! 例%!设("""#是整数!(&!且"##!证明%若($#"((#($!则 (" ((#( "(#! !"'!!! "!!数!!论 证明!设>是一个素数!且>!*(!我们来证明>!" ((#( "(# !由此即导出本 题的结论#参见下面的注$! 记@%".#!若>$@!则#>!!@$%"!因($#"((#($!故>!$#"((#($!又 "(.#( %@/" (.#( @ !于是>!" ((#( @ ! 若>$@!用二项式定理!得 "(.#( @ % ##,@$(.#( @ %+ ( 4%" 54(#(.4@4."! ! 设>"*4#4%"$!则#"'>"'4!由此易知"'4."!因此54(@4."% ( 45 4." (."@4." 中所含的>的幂次至少是!.",#4."$%!!故!右边和中每一项均被>!整 除!故>!" ((#( @ !即>!" ((#( "(# #参考第"单元例&的注"$! 注!为了证明#$"!可将#作标准分解#%>!"">!##&>!22 !进而将问题分解 为证明>!44)"#4%"!#!&!2$#参看第#单元中#""$$!这样做的益处在于能 够应用素数的锐利性质!例)的论证清楚地表现了这一点! 例&!设0"(是非负整数!证明% ##0$.##($. 0.(.#0%($.是一个整数! 证明!我们只需证明!对每个素数>!分母0.(.#0%($. 的标准分解中 >的幂次!不超过分子##0$.##($.中>的幂次!由#+$中的公式可知!这等价 于证明 + 4 ;%" #0 >( ); , #(>( )# $; %+ 4 ;%" 0 >( ); , (>( ); , 0,(>( )# $; ! ! 事实上!我们能够证明下述更强的结果% 对任意实数-"/!有 (#-),(#/)%(-),(/),(-,/)! " 为了证明"!我们注意!对任意整数2及任意实数!!有(2,!)%(!),2! 由此易知!若-或/改变一个整数量!则不等式"两边改变一个相同的量!因 此只要对!'-("!!'/("的情形证明"!于是问题化为证明不等式 (#-),(#/)%(-,/)! 注意现在!'(-,/)'"!若(-,/)%!!则结论显然成立!若(-,/)% "!则-,/%"!从而-"/中至少有一个大于或等于"# !不妨设-%"# !因此 !"(!!! $!素数及唯一分解定理 " (#-),(#/)%(#-)%"!这就证明了"!从而更有!成立!这就证明了本题的 结论! 例'!设0"(是互素的正整数!证明%0.(.$#0%(("$.! 证法一!与例*的方法相同!我们证明!对每个素数>!有 + 4 ;%" 0,(." >( ); %+ 4 ;%" 0 >( ); , (>( )# $; ! ! 为此!我们#与上例相同地$希望证明+单项不等式,% 0,(." >( ); % 0>( ); , (>( ); " 对任意素数>及任意正整数;成立!从而!得证! 然而!现在的情形下!我们不能指望建立像例*中"那样的对所有实数成 立的结果来导出"!我们需要利用所说整数的特别性质% 由带余除法!0%>;*",+"!(%>;*#,+#!这里!'+""+#(*;!而*"" *#均为非负整数!则有#参见第"单元的#'$$ 0 >( ); %*"及 (>( ); %*#! 但#0!($%"!故+"与+#不能同时为零!从而+",+#%"!故 0,(." >( ); %*",*#, +",+#.">( ); %*",*#! 这就证明了"!证毕! 证法二!首先!与例*类似地不难证明!对任意正整数""#!数 #"%#$. ".#. 是 一个整数!#这也可以利用 #",#$.".#. %5 " ",#!而由后者的组合意义知!它必定 为一个整数!下面的注中给出了一个更为直接的证明!$ 由上述结果可知!#0%(("$.0.#(("$.与 #0%(("$. #0("$.(.均是整数!因此 !若设5% #0,(."$. 0.(. !则05与(5 均是整数!故0(5 %0/(5 是0 的倍数!又 0(5%(/05!而由0$(/05及#0!($%"!可知0$05!而这表明!5本 身是一个整数!证毕! 注!这儿给出 #"%#$. ".#. 为整数的一个证明 % 我们对"%#归纳!易知",#%#时结论成立!设对所有满足",#%(的 !")!!! "!!数!!论 正整数""#结论均已成立!现在设""#满足",#%(,"!若""#中有"!则 结论显然成立!故设"&"!#&"!由#"."$,#%(!",##."$%(!及归 纳假设可见 #"."$.#.)#",#."$.!".##."$.)#",#."$.! # 我们又有 #",#$.%#",#."$./#",#$%#",#."$./",#",#."$./#! $ 由#易知".#.%"/#"."$.#.整除#"%#("$./"!同样".#. 整除#"%#( "$./#!故".#. 整除$的右端!从而".#.$#"%#$.!即",#%(,"时结论 也成立!这就完成了归纳证明! !!! !习 题 # ! 证明%对任意给定的正整数(&"!都存在连续(个合数! " 证明%形如'2("的素数有无穷多个!形如*2("的素数也有无穷多个#2 为正整数$! # 证明%有无穷多个奇数0!使-0%,0#是合数! $ 设整数""#"$"9满足"&#&$&9&!!且 "#,"$.$#%##,#9.9#! 证明%"#%$9不是素数! 不定方程（一） !"*!!! %!不定方程!一" " 不定方程!是指未知数的个数多于方程的个数!而未知数的取值范围受 某些限制#如整数"正整数"有理数等$的方程!不定方程是数论的一个重要课 题!数学竞赛中也常涉及这方面的问题! 初等范围内!处理不定方程主要有三种方法%分解方法!同余方法!以及 #不等式$估计方法!分解方法则是最为基本的方法! 分解方法的主要功效!大致地说!是通过+分解,将原方程分解为若干个 易于处理的方程!这里说的+分解,包含两个方面的手法%其一!是代数#整式$ 的分解-其二!是应用整数的某些性质#唯一分解定理!互素的性质等$导出适 用的分解! 分解方法当然没有固定的程序可循!有时!分解相当困难!或分解方式较 多而难以选择-有时!进一步的论证则很不容易!本节的一些例子就已表现了 这些! 分解方法常和别的方法结合使用!请参考本单元及后面的一些例子! 例!!一个正整数!加上"!!!为一完全平方数!若加上"*-!则为另一个 完全平方数!求此数! 解!设所求的数为-!由题意!有正整数/"A!使得 -,"!!%/#! -,"*-%A#0 ! 从上面两个方程中消去-!得出 A#./#%*-! 将这个二元二次方程的左边分解因式!而将右边作标准分解!得 #A./$#A,/$%##3"+! ! 由于A(/及A%/都是正整数!且A./(A,/!故由!及唯一分解定理#第 &单元#)$$推出!必有 !#!!!! "!!数!!论 A./%"! A,/%##3"+0 -A./%# ! A,/%#3"+0 -A./%# #! A,/%"+0 ! " 逐一解这些二元一次方程组!可得出/%"*!A%"-!故-%")*! 例"!求不定方程% -',/',A'%#-#/#,#/#A#,#A#-#,#' 的全部整数解! 解!关键的一步#也是本题的主要困难$是看出方程可分解为 #-,/,A$#-,/.A$#/,A.-$#A,-./$%.#&3&! ! 因上式左边四个因数都是整数!由唯一分解定理!可类似于例"那样!将 !分解为若干个#四元一次$方程组来求解!这虽然也能够解决问题!但却较 为麻烦! 我们#基于!$采用下面的处理%因素数#整除!的右边!故!的左边四个 因数中至少有一个被#整除!另一方面!这四个数中任意两个的和显然是偶 数!故它们的奇偶性相同!从而现在都是偶数!即!的左边被#'整除!但!的 右边不是#'的倍数!因此方程无整数解! 顺便提一下!若在例"的解答中采用类似的考虑!可稍稍简化那儿的程 序%因为A(/与A%/的奇偶性相同!因此例"的"中所列的方程组中!我们 只需求解其中的第二个! 例#后一半的论证!以#第*单元讲的$同余的角度看则更为清楚%就是先 对!模#!然后再模#'!同余方法处理不定方程将在第,单元中专门讨论! 例#!证明%两个连续正整数之积不能是完全平方!也不能是完全立方! 证明!反证法!我们假设有正整数-!/!使得 -#-,"$%/#! 将方程两边乘以'!变形为##-,"$#%'/#,"!这可分解为 ##-,",#/$##-,".#/$%"! 因左边两个因数都是正整数!故有 #-,",#/%"! #-,".#/%"0 ! 解得-%/%!!矛盾!这就证明了问题中的第一个断言! 然而!对于方程 !#"!!! %!不定方程!一" " -#-,"$%/&! 上面的分解方法不易奏效!我们采用另一种#基于数的性质的$分解%设所说 的方程有正整数解-"/!则由于-和-%"互素!而它们的积是一个完全立 方!故-和-%"都是正整数的立方!即 -%&&!-,"%'&!/%&'! &!'都是正整数!由此产生'&.&&%"!故 #'.&$#'#,&',&#$%"! 这显然不可能!不难看到!用类似的论证!可证明连续两个正整数之积不会是 整数的2次幂#这里2%#$! 判明一个乘积中的各个因数互素往往非常重要!下面的例'!例)均是 如此! 例$!证明%方程 /,/#%-,-#,-& 没有-#!的整数解! 证明!设方程有-#!的整数解!将它分解为 #/.-$#/,-,"$%-&! ! 我们先证明#/.-!/,-,"$%"!若这不正确!则有一个素数>为/( -与/%-%"的一个公约数!由!知>$-&!故素数>整除-!结合>$#/(-$ 知>$/!但>$#-%/%"$!从而>$"!这不可能!故!的左边两因数互素!因! 的右边是一个完全立方!从而有整数""#!使得 /.-%"&!/,-,"%#&!-%"#! 消去-!/得到 #&."&%#"#,"! " 现在证明方程"无整数解!由此便导出了矛盾!我们将"分解为 ##."$###,"#,"#$%#"#,"! # 注意-%"#而-#!!故"##!!若"#&!!则由#易知#."&!!因""# 为整数!故#."%"!于是#的左边%##%"#%"#&&"#&右边-若"#(!!则 )#.")%#!故#的左边的绝对值%##"#%##($"#$$&#$"#$!而#的右边的 绝对值(#$"#$!因此#不能成立!这就证明了问题中的方程没有-#!的整 !##!!! "!!数!!论 数解! 方程#无解的论证!采用了不等式估计#左边的绝对值总大于右边的绝 对值$!这就是所谓的估计法!#数论中的$估计法往往需着眼于整数!利用整 数的各种性质产生适用的不等式!例如!上述论证应用了整数的最基本的性 质%若整数-&!!则-%"! 估计法!当然不限于不定方程!许多数论问题都可以用这方法解决!本书 中有不少这样的例子! 例%!设2是给定的正整数!2%#!证明%连续三个正整数的积不能是整 数的2次幂! 证明!假设有正整数-%#及/!使得 #-."$-#-,"$%/2! ! 请注意上面左端的三个因数-(""-"-%"并非总两两互素!因此不能 由!推出它们都是2次方幂!克服这个困难的一种方法是将!变形为 #-#."$-%/2! " 因-和-#("互素!故由"推出!有正整数""#!使得 -%"2!-#."%#2!"#%/! 由此我们有 "%"#2.#2 %#"#$2.#2 %#"#.#$#"#2.#,"#2.'#,&,"##2.#,#2."$! 由于-%#!故"%#!又2%#!故上式后一个因数必大于"!导出矛盾! 例&!求#-#./#$#%","*/的全部整数解! 解!因方程左边%!!故右边%!!从而/%!!又显然-#./##!!而-"/ 为整数!故)-)%/,"!或)-)'/."! 当)-)%/,"时!方程左边%##/%"$#(/#$#6##/%"$#! 当)-)'/."时!此时/."%!!且/#.-#%/#.#/."$#%#/. "&!!故方程左边%##/("$#! 因此由原方程产生 ##/."$#'","*/! 故有!'/')!逐一检验可求出全部整数解为#-"/$%#:"!!$!#:'!&$! #:'!)$! 例'!设正整数-"/"A满足#-- %//,AA!则-%/%A! !#$!!! %!不定方程!一" " 证明!首先!将#-%"$-%"展开即知 #-,"$-,"&--,",#-,"$-- &#--! ! 由此可知/"A必须均'-%因若/"A中有大于-的!无妨设/&-!因/"-为 整数!故/%-,"!从而 //,AA&// %#-,"$/ %#-,"$-,"&#--#应用!$! 产生矛盾! 因此/'-!A'-!故 //,AA'--,-- %#--! 结合原方程知!必须有/%-!且A%-!故-%/%A!证毕! 例*"例+的处理均依靠不等式!其要点是利用#前面提过的$整数的基本 性质%若整数-&!!则-%"! !!! !习 题 $ ! 证明%连续四个正整数之积不能是一个完全平方数! " 求出所有可以表示为两个整数平方差的整数! # 求不定方程组 -,/,A%&! -&,/&,A&%0 & 的全部整数解! $ 求-&%/&,#/#,"的全部整数解! % 求所有正整数-"/!使-#%&/!/#%&-均是完全平方数!   《数学奥林匹克小丛书》    以专家讲座的形式展开  由浅入深、夹叙夹议、讲练结合  在知识学习中实现能力培养  薄薄的小册子助你透析每一个专题  从奥委会委员到国家队教练  从大学教授到金牌教练员  聚集了国内最顶尖的奥数辅导专家  为你打造了一套最经典奥数专题辅导丛书  数学奥林匹克小丛书（第二版）初中卷    初中卷 1 单墫  著因式分解技巧 初中卷 2 葛军  编著方程与方程组 初中卷 3 一次函数与二次函数  李惟峰  编著 初中卷 4 三角形与四边形  沈文选  编著 初中卷 5 柯新立  编著圆 初中卷 6 冯志刚  著整除、同余与不定方程 初中卷 7 周建新  编著组合趣题 初中卷 8 冯志刚  顾滨  主编初中数学竞赛中的解题方法与策略   数学奥林匹克小丛书（第二版）·高中卷  高中卷1 刘诗雄  编著集合 高中卷2 熊斌  朱臻  苏勇  编著函数与函数方程 高中卷3 曹瑞彬  周益忠  编著三角函数 高中卷4 李胜宏  边红平  编著平均值不等式与柯西不等式 高中卷5 苏勇  熊斌  编著不等式的解题方法与技巧 高中卷6 冯志刚  著数列与数学归纳法 高中卷7 范端喜  邓博文  编著平面几何 高中卷8 张思汇  编著复数与向量 高中卷9 冷岗松  著几何不等式 高中卷10 余红兵  著数论 高中卷11 张垚  编著组合数学 高中卷12 熊斌  郑仲义  编著图论 高中卷13 冯跃峰  编著组合极值 高中卷14 熊斌  何忆捷  编著高中数学竞赛中的解题方法与策略               学奥数，这里总有一本适合你    自从 2000 年《奥数》中首次在图书中使用“奥数”一词以来，华东师范 大学出版社已陆续出版近 200种“奥数”图书,  形成多品种、多册层次全系列。  “奥数”入门篇——《从课本到奥数》（1‐9年级）Ａ、B版  “奥数”智优篇——《优等生数学》（1‐9年级）  “奥数”辅导篇——《奥数教程》、《学习手册》、《能力测试》（一至高三年级）  “奥数”小学顶级篇——《高思学校竞赛数学课本》、《高思学校竞赛数学导引》  “奥数”专题篇——《数学奥林匹克小丛书》（小学、初中、高中共 30种）  “奥数”题库篇——《多功能题典  数学竞赛》（小学、初中、高中共 3种）  “奥数”高中预赛篇——《高中数学联赛备考手册（预赛试题集锦）》  “奥数”联赛冲刺篇——《高（初）中数学联赛考前辅导》  “奥数”IMO  终极篇——《走向IMO：数学奥林匹克试题集锦》  “奥数”域外篇——《日本小学数学奥林匹克》、《全俄中学生数学奥林匹克》