整除、同余不定方程（数学奥林匹克）

书书书 目　　录 !!"!!!! 目!!录 " !!整除 $$0 !)P)!整除的概念与基本性质 $$0 !)PQ!素数与合数 $$! !)P/!最大公因数与最小公倍数 $$3 !)PR!算术基本定理 $0! !习) $01 "!同余 $#0 !QP)!同余的概念与基本性质 $#0 !QPQ!剩余系及其应用 $#2 !QP/!费马小定理及其应用 $#4 !QPR!奇数与偶数 $!! !QP+!完全平方数 $!" !习题Q $<0 #!不定方程 $<2 !/P)!一次不定方程'组( $<2 !/PQ!不定方程的常用解法 $2$ !/P/!勾股方程 $"$ !习题/ $"2 ! 习题解答 $"1 符号说明 !!"!!!! 符号说明 " !"#!!!!!!!!!!!整除# ! # !不整除# '!%#( !与#的最大公因数 *!%#+ !与#的最小公倍数 $!#! $!$!但$!S)! !%#':6<%( !与#对模% 同余 !&#':6<%( !与#对模% 不同余 !&)':6<%( !对模% 的数论倒数 *'+ 不超过'的最大整数 :LT,!%#- 实数!!#中较大的数 :35,!%#- 实数!!#中较小的数 书书书 整　　除 !!"!!!! "!整!!除 " 任意两个整数的和!差或积都是整数"但是两个整数做除法时所得的结 果不一定是整数"因此"数论中的许多问题都是在研究整数之间的除法! !"!!整除的概念与基本性质 定义!!对任给的两个整数"!##"#!$"如果存在整数$"使得#%"$" 那么称#能被"整除#或称"能整除#$"记作"$#!否则"称#不能被"整除"记 作" #! 如果"$#"那么称"为#的因数"#为"的倍数! 利用整除的定义"可以非常容易地推导出下面一些经常被用到的性质! 性质!!如果"$#"那么"$#"#$"反过来也成立%进一步"如果"$#"那么 #""$$#"反过来也成立! 因此"我们经常只讨论正整数之间的整除关系! 性质"!如果"&#"#&'"那么"&'!这明整除具有传递性! 性质#!若"&#""&'"则对任意整数(!)"都有"&#(*')!#即"能整 除#!'的任意一个&线性组合'$ 例!!若"&+"#&+"且存在整数(!)"使得"(*#)%#"证明("#&+! 证明!由条件"可设+%","+%#-",!-为整数!于是 +%+#"(*#)$ %+"(*+#) %"#-(*"#,) %"##-(*,)$" 因此 "#&+! 说明!一般地"由"&+"#&+"并不能推出"#&+"例如$&%"%&%"但 #$ %!题中给出的条件实质上表明"!#的最大公因数#见#&'节$为#"即" !!#!!!! "!!整除!同余与不定方程 与#互素"在此条件下可推出"#&+! 例"!证明(无论在数#$!!(的两个!之间添加多少个'"所得的数都是 #)的倍数! 证明!记"!%#$!!(""+ %#$!')* ' +个' !("+%#"$")! 首先"因为 "!%#).%'$" 故 #)&"!! 其次"设#)&"+"则由 "+*#/#!"+ %$$(%#).#$" 可知 #)&"+*#! 所以"对一切整数+"数"+都是#)的倍数! 说明!此题的处理过程中运用了递推的思想"其基本思路是将"+*#表示 为"+与#)的一个线性组合! 例#!已知一个#!!!位正整数的任意连续#!个数码形成的#!位数是 $#!的倍数!证明(该正整数为$#!!!的倍数! 证明!设该正整数(%"#"$)"#!!!"其中"0是十进位数码!由条件"可知 $#! !"))#)"#!!!"$#! !"))!)")))" 因此 $#! !"))!)"))).#!! 记)%"))#)")))"则有 $#! !"))!.#!#!*#!)" 故 $#! !#!)! 结合$#! !"))#)"#!!!"可知 $#!&#!)*"#!!!" 于是 $#! !"#!!!" 这要求 "#!!!%!! 类似地"朝前倒推"可得 "##%)%"#!!!%!" !!$!!!! "!整!!除 " 即 (%"#)"#!.#!))!! 再结合条件$#! !"#)"#!"即可得 $#!!!&(! 说明!这里先证明"##% ) %"#!!!%!是非常关键的"在证明中利用 "))#)")))来过渡也是比较巧妙的! 例$!设1是一个大于$的正整数"证明(对任意正整数+"都有$1/# $+*#! 证明!如果存在正整数+"使得$1 /#&$+*#"那么取其中最小的那 个+! 由于1%$"知+%#"进一步"应有$+*#&$1/#"知+&1"而+%1 时"将导致$1/#&$#因为$%#$+*#$/#$+/#$"右边每一项都是$+/#的 倍数$"矛盾"故+%1! 现在"设$+*#%#$1/#$$"这里$为正整数"则 $+*$1 %#$+*#$*#$1/#$%#$1/#$#$*#$" 即 $1#$+/1*#$%#$1/#$#$*#$! 于是" #$+/1*#$*#$1/#$#$+/1*#$%#$1/#$#$*#$" 得$+/1*#%#$1/#$#$/$+/1$"因此"$1"#$$+"1*#"与+的最小性矛盾! 所以"命题成立! 说明!这里用到了两个结论(一个是&若"&#"##!"则&"&'&#&'"它 由整除的定义可直接证出!另一个是&任意多个正整数中必有最小元'"这是 著名的&最小数原理'! !"#!素数与合数 对任意正整数+%#"如果除#与+以外"+没有其他的因数"那么称+为 素数!否则称+为合数!这样"我们将正整数分为了三类(#"素数"合数! 素数从小到大依次为$"'"+","##")!我们可以非常轻松地写出#!! 以内的所有素数"共$+个!但是并不是对每个素数2"都能轻易地指出2后面 的一个素数是多少!事实上"当2比较大时"求出它后面的那个素数是十分困 难的!正是素数的这种无规律性"初等数论才显得魅力无穷!具有很强的挑战 !!%!!!! "!!整除!同余与不定方程 性和极大的吸引力! 素数与合数具有如下的一些性质! 性质!!设+为大于#的正整数"2是+的大于#的因数中最小的正整 数"则2为素数! 性质"!如果对任意#到槡+之间的素数2"都有2 +"那么+为素数!这 里+#%#$为正整数! 证明!事实上"若+为合数"则可写+%2$"$'2'$!因此2$'+"即 2'槡+! 这表明2的素因子'槡+"且它是+的因数"与条件矛盾!因此+为素数! 说明!这里素因子是指正整数的因数中为素数的那些数"此性质是我们 检验一个数是否为素数的最常用的! 性质#!素数有无穷多个! 证明!若只有有限个素数"设它们是2#(2$()(2+!考虑数 (%2#2$)2+*#" 其最小的大于#的因数2"它是一个素数"因此"2应为2#"2$")"2+中的某 个数!设2%20"#'0'+"并且(%20)"则2#2$)2+*#%20)"即20#)/ 2#2$)20/#20*#)2+$%#!这导致20&#!矛盾! 所以"素数有无穷多个! 说明!如果将所有的素数从小到大依次写出为$%2#(2$()"并写 $+ %2#2$)2+*#"那么 $#%'"$$%,"$'%'#"$-%$##"$+%$'##" 它们都是素数!是否每一个+都有$+ 为素数呢+ 我们不能被表面现象所迷 惑"再朝下算"可知$%%+).+!)就是一个合数!事实上"后面的$,"$("$)" $#!都是合数!到目前为止"人们还不知道数列$#"$$")中是否有无穷多个素 数"也不知道其中是否有无穷多个合数! 性质$!素数中只有一个数是偶数"它是$! 例!!设+为大于#的正整数!证明(数++*+-*#不是素数! 证明!注意到 !++*+-*#!!!!!!! %++*+-*+'/#+'/#$ %+'#+$*+*#$/#+/#$#+$*+*#$ %#+'/+*#$#+$*+*#$" !!&!!!! "!整!!除 " 因此"若++*+-*#为素数"则+'/+*#%#"这要求+%!或.#! 故当+%#时"++*+-*#不是素数! 说明!利用因式分解来判断一个数是否为素数是数论中的常见方法"后 面也将不断用到! 例"!考察下面的数列( #!#"#!#!#"#!#!#!#")! 问(该数列中有多少个素数+ 解!易知#!#是素数!下证这是该数列中仅有的一个素数! 记"+ %#!#!#))* +!# +个!# "则当+&$时"有 "+ %#!$+*#!$#+/#$*)*# %#! $#+*#$/# #!$/# % ##!+*#/#$##!+*#*#$ )) ! 注意到"))(#!+*#/#"))(#!+*#*#"而"+为正整数"故"+是一个合数#因 为分子中的项#!+*#/#与#!+*#*#都不能被))约为#$! 说明!这里需要将因式分解式(+/#%#(/#$#(+/#*(+/$*)*#$反 用"高中阶段它被作为等比数列求和的公式! 例#!求所有的正整数+"使得+ #+*#$ $ /# 是一个素数! 解!记"+%+ #+*#$ $ /# "则"#%!不是素数"因此只需讨论+%#的情 形!我们利用+只能是形如-3!-3*#!-3*$!-3*'的数分别讨论! 当+是形如-3*$或-3*#的数时""+都是偶数"要"+为素数"只能是 +#+*#$ $ /#%$ " 解得 +%$! 当+%-3时"可得 "+ %$3#-3*#$/#!!! %(3$*$3/# %#-3/#$#$3*#$" 这是一个合数! 当+%-3*'时"可得 !!'!!!! "!!整除!同余与不定方程 "+ %$#3*#$#-3*'$/# %(3$*#-3*+ %#-3*+$#$3*#$" 仅当3%!"即+%'时""+为素数! 所以"满足条件的+%$或'! 说明!对+分类处理一方面是去分母的需要"另一方面是为进行因式分 解做准备! 例$!对任意正整数+"证明(存在连续+个正整数"它们都是合数! 证明!设+为正整数"则 #+*#$,*$"#+*#$,*'")"#+*#$,*#+*#$ 是+个连续正整数"并且第3个数是3*#的倍数#且大于3*#$"故它们是连 续的+个合数! 说明!这个结论表明(对任意正整数+"都存在两个素数"它们之间至少 有+个数"且这些数都是合数!但是"让我们来看一些素数对#'"+$"#+",$" ###"#'$"##,"#)$")"##)),"#)))$"它们所含的两个素数都只相差$#这 是两个奇素数的最小差距$"这样的素数对称为孪生素数!是否存在无穷多对 素数"它们是孪生素数+ 这是数论中一个未解决的著名问题! 例%!设+为大于$的正整数!证明(存在一个素数2"满足+(2(+,! 证明!设2#(2$()(23"且2#"2$")"23是所有不超过+的素数" 考虑数 $%2#2$)23/#" 在+%$时"$"'都在2#")"23中出现"故+'$'+,/#(+,"利用性质 '证明中的方法"可知$的素因子2不等于2#"2$")"23中的任何一个!而 2#"2$")"23是所有不超过+的素数"因此2%+"所以+(2'$(+,! 从而"命题成立! 说明!利用本题的结论亦可证出(素数有无穷多个!贝特朗曾猜测在 1%#时"正整数1与$1之间#不包括1与$1$有一个素数!如果将素数从 小到大排列为2#(2$()"该猜测亦即2+*#($2+!这个猜测被契比雪夫证 明了!因此它被称为贝特朗猜想或契比雪夫定理! 例&!设"!#!'!4!5!6都是正整数"7%"*#*'*4*5*6是"#'* 456和"#*#'*'""45"56"54的因数!证明(7为合数! 证明!考虑多项式 !!(!!!! "!整!!除 " 6#($/#(*"$#(*#$#(*'$"#("4$#("5$#("6$! 展开后"可知 6#($%7($*#"#*#'*'"/45/56/64$(*#"#'*456$! 由条件可知"对任意(,'"都有7$6#($!特别地"取(/4"就有7$6#4$"即 7$#4*"$#4*#$#4*'$!由于"!#!'!4!5!6都为正整数"故4*"!4*#! 4*'都小于7"所以"7为合数! 说明!对比例$"两个例子中分别用到下面的结论(若(!)!8为正整数" 且()8 亦为整数 "则如果(!)%8"那么()8 为合数 %如果(!)(8"那么8为 合数! !"$!最大公因数与最小公倍数 设"!#是不全为零的两个整数"4是一个非零整数"如果4&"且4&#"那 么称4为"!#的公因数! 注意到"当4&"且4&#时"则4'&"&或4'&#&中必有一个成立#对 "!#中不为零的数成立$!因此""!#的公因数中有一个最大的"这个数称为 "!#的最大公因数"记为#""#$!如果#""#$%#"那么我们称"!#互素! 在讨论最大公因数的性质之前"我们不加证明地引入一个在就接触 到的!数论中最基本!最常用的结论! 带余数除法!设"!#是两个整数""#!"则存在唯一的一对整数$和9" 满足 #%"$*9"!'9(&#&" 其中$称为#除以"所得的商"9称为#除以"所得的余数! 性质!!设4%#""#$"则存在整数(!)"使得 "(*#)%4! 这个结论就是著名的贝祖!()*+,-"定理! 证明!我们利用带余除法来处理"此结论的证明过程又是求"!#的最大 公因数的过程"它被称为&辗转相除'! 不妨设"!#都不为零#当"!#中有一个为零时"结论是显然的$"且 &"&'&#&! 设#%"$#*9#"其中!'9#(&"&"$#!9#为整数!若9#%!"则辗转相 !!)!!!! "!!整除!同余与不定方程 除到此为止%否则用"去除以9#"得等式"%9#$$*9$"!'9$(9#%依此讨 论"由于9#%9$%9'%)"因此辗转相除到某一步后"所得的93*#%!"于是" 我们得到了如下的一系列式子( #%"$#*9#"!(9#(&"&% "%9#$$*9$"!(9$(9#% 9#%9$$'*9'"!(9'(9$% )))))))))))) 93/$%93/#$3*93"!(93(93/#% 93/#%93$3*#! 注意到"从第一个式子到第3个式子"我们依次有 4&9#"4&9$")"4&93" 而从第3*#个式子倒推"又依次有 93&93/#"93&93/$")"93&9#"93&""93&#" 所以"93又是"!#的公因数"结合4为"!#的最大公因数知93'4"又4&93" 故4'93"因此"4%93!也就是说"我们求出了"!#的最大公因数! 现在"利用4%93及第3个式子"可知 4%93/$/93/#$3" 再由 93/#%93/'/93/$$3/##第3/#个式子变形得$" 代入上式"可知4可以表示为93/$与93/'的&线性组合'#见#&#节性质$$"依 此倒推"可知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(-""#."这与 -""#.是"!#的最小公倍数矛盾!所以-""#.&'! 性质/!设"!#都是正整数"则-""#.% "##""#$! 证明!记'% "##""#$ "则由#""#$&"及#""#$&#知#&'""&'!即'为 "!#的公倍数"故-""#.&'! 反过来"由贝祖定理"知存在整数(!)"使得 "(*#)%#""#$" 即 "#""#$(* # #""#$)%# " 于是 "-""#.#""#$(* #-""#. #""#$)% -""#.! 由#&-""#.及"&-""#."可知 !"!!!! "!!整除!同余与不定方程 '" -""#. #""#$ "'# -""#. #""#$! 所以 '&-""#.! 综上"可知 -""#.% "##""#$! 一般地"对+个整数#非零$"#""$")""+"可以类似地引入最大公因数 与最小公倍数的概念"分别记为#"#""$")""+$和-"#""$")""+.!容易得 到下面的一些结论( 性质0!#"#""$""'")""+$% ##"#""$$""'")""+$%而 -"#""$" "'")""+.%--"#""$.""'")""+.! 性质!1!存在整数(#"($")"(+"使得 "#(#*"$($*)*"+(+ %#"#""$")""+$! 特别地"#"#""$")""+$%#"即"#""$")""+互素的充要条件是(存在整 数(#"($")"(+"使得 "#(#*"$($*)*"+(+ %#! 注意"+个数互素"并不能保证它们两两互素"例如 #$.'"$.+"'. +$%#"但%!#!!#+两两不互素!反过来"若+个数中有两个数互素"则这+ 个数互素!因此"在+个数中"&两两互素'的条件比&它们互素'的条件要强 得多! 性质!!!设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%'"-同上讨论"得#""#$%#-"-$! 所以"满足条件的#""#$%#-"'($"#'("-$"#-"-$! 例%!012345661数列定义如下(;#%;$%#";+*$%;+*#*;+"+%#" $")!证明(对任意正整数1!+"都有#;1";+$%;#1"+$! 证明!当1%+时"命题显然成立!现在不妨设1(+"注意到 ;+ %;$;+/#*;#;+/$!!!!! %;$#;+/$*;+/'$*;#;+/$ %#;$*;#$;+/$*;$;+/' %;';+/$*;$;+/' %;'#;+/'*;+/-$*;$;+/' %;-;+/'*;';+/- %) %;1;+/1*#*;1/#;+/1" 因此"设4&;1且4&;+"则由上式可知4&;1/#;+/1!又对任意正整数1"有 #;1";1/#$%#;1/#*;1/$";1/#$%#;1/#";1/$$%)%#;$";#$%#" 所以"#4";1/#$%#"故4&;+/1%反过来"若4:&;+/1且4:&;1"则由上式 又可知4:&;+!依此可知#;+";1$%#;+/1";1$! 利用上述结论"对下标进行辗转相除"就可证得#;+";1$%;#1"+$! 说明!由本题的结论还可以推出一个有趣的性质(若;+为素数"则+%- 或者+为素数! 事实上"设;+为素数"而+为合数"可设+%2/$"$'2'$"2!$为正 !"$!!! "!整!!除 " 整数"则由前面的结论"可知#;+";2$%;#+"2$%;2"#;+";$$%;#+"$$% ;$!结合012345661数列的定义"可知;+ %;2";+ %;$"而;+ 为素数"故 #;+";2$%#;+";$$%#"所以";2%;$%#"再由$'2'$"可知只能是 2%$%$"即+%-!所以"性质成立! 例&!设+为大于#的正整数!证明(存在从小到大排列后成等差数列 #即从第二项起"每一项与它前面那项的差为常数的数列$的+个正整数"它们 中任意两项互素! 证明!考虑下面的+个数( +,*#"$.#+,$*#")"+.#+,$*#! 这+个正整数组成一个公差为+, 的等差数列! 我们证明其中任意两项是互素的! 事实上"若存在#'0(<'+"使得数0.#+,$*#与数<.#+,$*#不 互素"设4%#0.#+,$*#"<.#+,$*#$%#!考虑4的素因子2"可知 2&#<.#+,$*#$/#0.#+,$*#$" 即2&#$$ =/# *#$ '#$$ 1 /$$ 1/# *#"$$ 1 *$$ 1/# *#$ %#$$ 1 /$$ 1/# *#"$.$$ 1/#$! 由于"$.$$ 1/# 中只有一个素因子$"而$$ 1 /$$ 1/# *#为奇数"故 #$$ 1 /$$ 1/# *#"$.$$ 1/#$%#"! 因此 #$$ 1 /$$ 1/# *#"$$ = >$$ =/# *#$%#! 所以"$$ # *$$ ! *#"$$ # /$$ ! *#"$$ $ /$$ # *#")"$$ +/# /$$ +/$ *#两 两互素"进而$$ + *$$ +/# *#至少有+个不同的素因子! 例$!设1!+是正整数"且1的所有正因数之积等于+的所有正因数之 积!问(1与+是否必须相等+ 解!1与+必须相等! 事实上"将1的正因数4与14配对 "可知1的所有正因数之积为1 4#1$ $ " 因此"条件等价于 14#1$%+4#+$" ! 此式表明1!+有相同的素因子"可设 1%2!##2!$$)2!33 "+%2"##2"$$)2"33 " 其中2#(2$()(23为素数"!0与"0都是正整数"#'0'3! 代入!式"利用算术基本定理"可知 !04#1$%"04#+$"#'0'3" " 若4#1$%4#+$"则对#'0'3"都有!0("0"于是"!0*#("0*#"故 #!#*#$#!$*#$)#!3*#$(#"#*#$#"$*#$)#"3*#$"这导致4#1$( 4#+$"矛盾!同样"由4#1$(4#+$"利用"式也可导出矛盾!所以4#1$% 4#+$"进而由!式得1%+! 说明!一般地"由##1$%##+$#即考虑1!+所有正因数之和$并不能导 出1%+#例如##%$%####$%#$$"此题是对两个正整数的所有正因数作乘 积方面的思考得出的结论! 例%!求所有的正整数(!)"使得 !"(!!! "!整!!除 " )( %(+!! ! 解!设(!)为满足条件的正整数"并且(%2!##2!$$)2!33 为(的素因数分 解式"则 )%2 +!!# ( # 2 +!!$ ( $ )2 +!!3 ( 3 ! 由)为正整数"知对#'0'3"都有(&+!!0!现在先讨论(的素因子! 如果(有一个不同于$和+的素因子2"并设2!-("那么由前面的结果 知(&+!!"当然有2!&+!!"又2#$!+"故2!&!!但是"对任意素数2及正 整数!"有2!%!"所以"2!&!不能成立"这表明(的素因子只能为$或+! 于是"我们可设(%$!/+"#其中!!"为非负整数$"这时(&+!!"(&+!"" 故$!&+!!"+"&+!""前者要求$!/#&!"后者要求+"/$&"!注意到"当!&'时" $!/#%!"而"&'时"+"/$%""所以"!'!'$"!'"'$!这表明(只能 取#"$"$$"+"+$"$.+"$$.+"$.+$"$$.+$! 将(的上述取值逐个代入!式"可得到全部解为 #(")$% ##"#$" #$"$$+$"#$$"$$+$"#+"+#!$"#+$"+-$"##!"#!+$"#+!"+!$"##!!"#!$" 共(组解! 说明!上面两例直接用到算术基本定理"所涉及的变量数看似增加或会 变难"但这时不等式估计的手段可介入"问题求解反而有了着力点! 例&!给定正整数+%#"设4#"4$")"4+都是正整数"满足(#4#"4$")" 4+$%#"且对<%#"$")"+都有4<&. + 0%# 40#这里. + 0%# 40%4#*4$*)* 4+$! ##$证明(4#4$)4+&#. + 0%# 40$+/$% #$$举例说明(+%$时"上式右边的幂次不能减小! 证明!##$设2为4#4$)4+的素因数"且3为各40的素因数分解式中2 的幂次的最大值"则由4<&. + 0%# 40可知"23&. + 0%# 40"故23#+/$$&#. + 0%# 40$+/$! 而#4#"4$")"4+$%#"故存在40"使得240"结合2&. + 0%# 40"可知4#" 4$")"4+中至少有两个数不是2的倍数!所以"2在4#4$)4+ 中的幂次不 超过3#+"$$"依此可知结论成立! #$$设4#%#"4$%+/#"40%+"''0'+"则. + 0%# 40%+#+/#$是每 个40的倍数"且#40"4$")"4+$%#! !")!!! "!!整除!同余与不定方程 此时"4#4$)4+ %++/$#+/#$"结合#+"+/#$%#"可知满足++/$#+/ #$&#+#+/#$$1 的最小正整数1 %+/$! !!! !习 题 ! ! 设+为大于#的正整数!证明(+-*-+是一个合数! " 求使得&-($/#$(/$,&为素数的所有整数(! # 设1为大于#的正整数"且1
/#$,*#!证明(1是一个素数! $ 是否存在'个不同的素数2!$!9"使得下面的整除关系都成立+ $9&2$*4"92&$$*4"2$&9$*4" 其中##$4%#!%#$$4%##! % 设2为正整数"且$2/#是素数!求证(2为素数! & 设+为正整数"且$+*#是素数!证明(存在非负整数3"使得+%$3! . 求所有形如++*#且不超过#!#)的素数"这里+为正整数! / 设"!#!'!4都是整数"且"#'""/'&"#*'4!证明("/'&"4*#'! 0 设"!#!'!4为整数"且"'!#'*"4!#4都是某个整数,的倍数!证明( 数#'和"4也是,的倍数! !1 设"!#!+为给定的正整数"且对任意正整数3###$"都有#/3&"/3+!证 明("%#+! !! 已知正整数+的正因数中"末尾数字为!"#"$")")的正整数都至少有 一个!求满足条件的最小的+! !"求一个)位数?"使得?的数码两两不同且都不为零"并对1%$"'")" )"数?的左边1 位数都是1 的倍数! !#对于一个正整数+"若存在正整数"!#"使得+%"#*"*#"则称+是一 个&好数'"例如'%#.#*#*#"故'为一个&好数'!问(在#"$")"#!! 中"有多少个&好数'+ !$ 设素数从小到大依次为2#"2$"2'")!证明(当+&$时"数2+*2+*#可 以表示为'个大于#的正整数#可以相同$的乘积的形式! !% 设+为大于#的正整数!证明(+为合数的充要条件是存在正整数"!#! (!)"使得+%"*#"("* ) # %#! !& 证明(数列#!!!#"#!!!#!!!#"#!!!#!!!#!!!#") 中"每一个数都是 合数! !"*!!! "!整!!除 " !. 设"!#!'!4都是素数"且"%'#%%'%#$4""$/#$*'$/4$%#,-)! 求"$*#$*'$*4$的所有可能值! !/数列0"+1的每一项都是正整数""#'"$'"'')"且对任意正整数3"该 数列中恰有3项等于3!求所有的正整数+"使得"#*"$*)*"+是素数! !0 由正整数组成的数列0"+1满足(对任意正整数1!+"若1&+"1(+"则 "1&"+"且"1 ("+!求"$!!!的最小可能值! "1设2为奇素数"正整数1!+满足1+ %#* # $* )* #2/#! 证明(2&1! "! 设"!1!+为正整数""%#"且"1*#&"+*#!证明(1&+! "" 证明(对任意正整数+及正奇数1"都有#$1 /#"$+*#$%#! "#费马数;+定义为;+%$$ + *#!证明(对任意两个不同的正整数1!+"都 有#;+";1$%#! "$ 已知正整数"!#!'!4的最小公倍数为"*#*'*4!证明("#'4是'或 +的倍数! "% 记?+为正整数#"$")"+的最小公倍数!求所有的正整数+#%#$"使 得?+ %?+/#! "& 设"!1!+为正整数""%#!证明(#"1/#""+/#$%"#1"+$/#! ". 设"!+为正整数""%#"且"+*#是素数!证明(4#"+/#$&+! "/ 对怎样的正整数+#%$$"存在+个连续正整数"使得其中最大的数是其 余+/#个数的最小公倍数的因数+ "0 设正整数"!#!1!+满足(#""#$%#""%#"且"1*#1&"+*#+!证明( 1&+! #1 证明(存在$!#$个不同的正整数"使得其中任意两个不同的数"!#都满 足#"/#$$&"#! #! 设"!#为正整数"且#""#$%#!证明(对任意正整数1"数列 """*#""*$#")""*+#") 中"有无穷多个数与1互素! #" 已知正整数数对#""#$满足(数""/##在十进制表示下"末尾恰有)(个 零!求"#的最小值! ## 求所有的正整数1"使得1%4#1$-! #$ 证明(每一个正整数都可以表示为两个正整数之差"且这两个正整数的素 因子个数相同! #% 求所有的正整数"!#!'"使得"$*#和#$*#都是素数"且满足 #"$*#$##$*#$%'$*#! !#!!!! "!!整除!同余与不定方程 #& 用2#3$表示正整数3的最大奇因数!证明(对任意正整数+"都有 $'+( . + 3%# 2#3$ 3 ( $ ' #+*#$! #. 设"!#!'都是大于#的正整数!求代数式"*#*'$ " -""#.*-#"'.*-'"". "*#*' 的最小可能值! #/ 对任意给定的素数2"有多少个整数组#""#"'$"使得 ##$#'""#"''$2$% #$$-""'.*-#"'."*# % 2$*# 2$*$ /'! #0 黑板上写着数#"$")"''!每次允许进行下面的操作(从黑板上任取两 个满足($)的数(!)"将它们从黑板上去掉"写上数)(!直至黑板上不存 在这样的两个数!问(黑板上至少剩下多少个数+ $1 设+是一个正整数!证明(数#*++*+$+*+'+*+-+是一个合数!   《数学奥林匹克小丛书》    以专家讲座的形式展开  由浅入深、夹叙夹议、讲练结合  在知识学习中实现能力培养  薄薄的小册子助你透析每一个专题  从奥委会委员到国家队教练  从大学教授到金牌教练员  聚集了国内最顶尖的奥数辅导专家  为你打造了一套最经典奥数专题辅导丛书  数学奥林匹克小丛书（第二版）初中卷    初中卷 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：数学奥林匹克试题集锦》  “奥数”域外篇——《日本小学数学奥林匹克》、《全俄中学生数学奥林匹克》