数论函数
【内容综述】
本讲介绍数论中常见的一些函数的概念、性质及其应用,主要有
除数函数
——自然数n的正因数的个数函数;——自然数n的全部正因数的和函数;
欧拉函数——设n是大于1的自然数,则欧拉函数是表示与n互素且不大于n的自然数的个数;(高斯函数或称方括号函数[X]在下讲介绍)为书写清楚,同学们应熟悉连加符号“”与连乘符号“”:
;
特别是“
“【要点讲解】
”表示对称式的和
”表示对称式的积abc……;
;
§1.约数个数函数§2.约数和函数§3.欧拉函数φ(n)
★
§1.约数个数函数
定义1定理1
设设
,则的正约数的个数称为函数,且
是质数
则
,
。
★
★
略证:由乘法原理,约数系由有
、、…、的不同取法而生成,它们的取法分别
种(含不取该约数的1种取法),故
得证
例1.求24的正约数个数。解:
事实上,易求得约数分别是1,2,3,4,6,8,12,24;个数正是8个。§2
约数和函数
定义设,
,则称的正约数和为函数
。
定理2自然数的正约数和函数
(其中
)。
略证
注意到(
)
为的素数,
,
展开后,其项数恰为的约数个数
,
又每项皆形如
,
,于是有
可见每项皆自然数的约数且每个约数只出现一次,由此可见该积即
例2.求780的正约数和解:
。
定理3若、是互质的自然数,即(a,b)=1,则
证明:设∵
,故
与
,,
各不相同(i=1,2,…,j=1,2,…,m)
§3.欧拉函数定义如
(∵每个小于。
关于欧拉函数定理4证明
,有以下性质定理
则
与
互素的充要条件是,且知在1和
,即有:
个数
设
互素且不大于的自然数的个数(),称为欧拉函数。
,易证
的自然数都与它互素);反之可见,若
是素数
是合数,必有
设P是素数,且
∵P是素数,显然有
,反之若
之间,有以下
是p的倍数:
,而其余的数都与
自然数个数。
互素,从而可知不超过
且与
互素的
当自然数的素因数分解式中,不只包含一个素因数时,有定理5
设大于1的自然数的素因数分解式为
,
其中
则有
证明:因为素因数的个数
数的自然数)。
(i)当
,故考虑采用数学归纳法(下设表有k个素因
;
(ii)设
注意到加入第个k+1素因数
后,有,
且当
于是由归纳假设就有
;
从而时,定理成立;
综上,对任意
(★的补证:引理设、、c∈N,则(i)若
,
从而可见故同理可证
(ii)若
,则存在素因数
,由
则
同理,若再证定理若
,则(★★)
注意到并把从1到
,故中有一个数为1时,(★★)显然成立,现假设
方阵:
的自然数排成长
1m+12m+1
2m+22m+2
……………………
rm+r2m+r
………………
m2m3m
(n-1)m+2……(n-1)m+rnm
与
则为上面这组数中与互素的自然数的个数,由引理知它等于这组数中同时都互素的自然数个数。
注意到(km+r,m)=(r,m),
所以当列数与
互素。
列的每列数中,恰好有
个自然数与互素,这样就能证明
时,第
列中的每一个数都与
互素,从而这
列数中共有
下面再证这
共有
·
个数,既与互素,也与互素,即定理为真。
事实上,从第列看,∵,
∴这列中的个数中,任意两个数被除时,所得余数都不会相同。(若不然,设
,
其中
因题设
可见这第列中的
序),而这
,于是有
)
个数被除的余数分别是0,1,2,3,…,(
,即第列中存在
-1)(不计顺
除同余,则
个数中与互素的自然数个数正是这就证明了例3解
。
个与互素的数。
求与300互素且不超过300的自然数的个数。所求的数即
★★★例4.试判断是否存在自然数解
设
,使
)
高中数学奥赛系列辅导材料
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)