数论函数
【内容综述】
本讲介绍数论中常见的一些函数的概念、性质及其应用，主要有
除数函数
——自然数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.欧拉函数定义如
（∵每个小于。
关于欧拉函数定理４证明
，有以下性质定理
则
与
互素的充要条件是，且知在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.试判断是否存在自然数解
设
，使
）
高中数学奥赛系列辅导材料
