文档介绍：膁莆芆学科:奥数莇教学内容:数论函数肈羄【内容综述】膂本讲介绍数论中常见的一些函数的概念、性质及其应用,主要有螈除数函数——自然数n的正因数的个数函数;蒆——自然数n的全部正因数的和函数;螃欧拉函数——设n是大于1的自然数,则欧拉函数是表示与n互素且不大于n的自然数的个数;(高斯函数或称方括号函数[X]在下讲介绍)为书写清楚,同学们应熟悉连加符号“”与连乘符号“”:膂;腿芈特别是“”表示对称式的和;螆“”表示对称式的积abc……;芁薀【要点讲解】蚆§§§(n)羁★★★莈§,则的正约数的个数称为函数。蒁定理1设,且是质数,则肈袆略证:由乘法原理,约数系由、、…、的不同取法而生成,它们的取法分别有膃种(含不取该约数的1种取法),。薈解:膆蚁事实上,易求得约数分别是1,2,3,4,6,8,12,24;个数正是8个。袀§2约数和函数羅定义设,,则称的正约数和为函数。羅定理2自然数的正约数和函数蚁(其中为的素数,)。芀略证注意到()螇蚃,螁展开后,其项数恰为的约数个数蚁,膅又每项皆形如,螆可见每项皆自然数的约数且每个约数只出现一次,由此可见该积即,。蒅解:羀艿定理3若、是互质的自然数,即(a,b)=1,则虿芄证明:设,,肀∵,故与各不相同(i=1,2,…,j=1,2,…,m)蚀肇§(),称为欧拉函数。膀如,易证是素数(∵每个小于的自然数都与它互素);反之可见,若是合数,必有。肁关于欧拉函数,有以下性质定理蝿定理4设P是素数,且则肆证明∵P是素数,显然有与互素的充要条件是,即有:,反之若,且知在1和之间,有以下个数是p的倍数:芀,而其余的数都与互素,从而可知不超过且与互素的自然数个数。膈芇当自然数的素因数分解式中,不只包含一个素因数时,有袅定理5设大于1的自然数的素因数分解式为芀,蕿其中则有羈蚀证明:因为素因数的个数,故考虑采用数学归纳法(下设表有k个素因数的自然数)。螀(i)当;肆(ii)设;蒃注意到加入第个k+1素因数后,有蚃,螀且当蒇于是由归纳假设就有膄蒂从而时,定理成立;袀综上,对任意袇(★的补证:引理设、、c∈N,则蚂(i)若则芀,羀从而羄可见莄故罿同理可证肀(ii)若,则存在素因数,由莅袂同理,若肂再证定理若,则膀(★★)螆注意到,故中有一个数为1时,(★★)显然成立,现假设并把从1到的自然数排成长方阵:薄袁艿***1羂2薀……荿r芄……蚄m荿m+1荿m+2蚅……膂m+r莂……葿2m肆2m+1袃2m+2膁……蕿2m+r薆……莁3m罿虿羇……肃羂蝿肄(n-1)m+1螅(n-1)m+2螁……衿(n-1)m+r蒅芃nm蒀羈袆则为上面这组数中与互素的自然数的个数,由引理知它等于这组数中同时与都互素的自然数个数。羅注意到(km+r,m)=(r,m),艿所以当时,第列中的每一个数都与互素,从而这列数中共有列数与互素。羈下面再证这列的每列数中,恰好有个自然数与互素,这样就能证明共有·个数,既与互素,也与互素,即定理为真。芇事实上,从第列看,∵,莃∴这列中的个数中,任意两个数被除时,所得余数都不会相同。节(若不然,设除同余,则肈,莄其中,于是有肅因题设)肁可见这第列中的个数被除的余数分别是0,1,2,3,…,(-1)(不计顺序),而这个数中与互素的自然数个数正是,即第列中存在个与互素的数。膈这就证明了。螅例3求与300互素且不超过300的自然数的个数。薂解所求的数即袀芈★★★,使膅解设)芄则袂莈即薆这里应估计到中必有一个是奇数(否则若它们全是偶数,则,于是螂蚁但必是2的倍数,但它不等于14,(否则,只有,且,不妨令(★★★)蒈而7是素数,★★★式中也是素数,因而不可能成立!),于是只能是羇蒄莀薇因此也不是成立的!膄综上知,不存在。:腿薇证明:薅(i)当是奇数时,,注意到,于是蚄(ii)当是偶数时,不妨设节蚇综i,ii,原命题成立。,其中。肂证明:(i)当=1,2时,()=1;羁(ii)当>2时,若则螇是偶数;莇若,于是螄螀袇螈【能力训练】 (即) 。 (共,求证。参考答案【能力训练】