高中数学奥赛系列辅导材料：数论函数.doc

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