数论学习笔记(3):欧拉函数

作者:氯化钡和硫酸银

时间:2014年2月4日 22:34

来源:http://blog.sina.cn/dpool/blog/s/blog_a661ecd50101axgy.html

欧拉函数有很多好玩的性质,这里补充一下…下次再说原根的事。

设 m为任意正整数,则欧拉函数 φ(m) 定义为 {1,2,3,…,m} 中与 m互素的整数的个数。不妨先观察一下一些比较小的数的欧拉函数:

φ( 1)= 1 φ( 2)= 1 φ( 3)= 2 φ( 4)= 2 φ( 5)= 4

φ( 6)= 2 φ( 7)= 6 φ( 8)= 4 φ( 9)= 6 φ(10)= 4

φ(11)=10 φ(12)= 4 φ(13)=12 φ(14)= 6 φ(15)= 8

φ(16)= 8 φ(17)=16 φ(18)= 6 φ(19)=18 φ(20)= 8

……

当然一般性的规律很难找,不过还是能看出一些特性的,比如下面这个:

1.若 m>=3 为整数,则 φ(m) 为偶数。

证明当然很容易,只需注意到两个和为 m 的数要么都与 m 互素,要么都不与 m 互素(事实上这两个数分别与 m的最大公约数是相同的)。这样, {1,2,3,…,m} 中的绝大多数都可以配对,剩下的只有 m ,如果 m 是偶数则还剩下m/2 ,而当 m>=3 时这两个数都不会与 m 互素。

2.若 p 为素数,则 φ(p)=p-1 。

这个容易理解,因为1,2,3,4,…,p-1 都与 p 互素。

3.若 p 为素数, k 为正整数,则 φ(p^k)=p^k-p^(k-1) 。

这个也不难。因为某个整数与 p^k 互素的充要条件是这个整数不能被 p 整除。从总数 p^k 中减去被 p 整除的数p^(k-1) 就是 φ(p^k) 的值。

下面的这个性质就比较牛B了:

4.若 a,b 是互素的正整数,则 φ(ab)=φ(a)*φ(b) 。

也就是说,两个互素的正整数相乘再求欧拉函数,等于两个数先求欧拉函数再相乘。证明用到了计数的方法:我们用两种方法数一下1,2,3,…,ab中与 ab 互素的整数的个数。

首先用定义立即得到这个数为 φ(ab) 。

然后,注意到一个整数与 ab 互素,当且仅当它与 a,b 均互素。

由前者推出后者:若一个整数与 ab 互素,它当然与 a,b 都找不出大于 1 的公因子。

由后者推出前者:若一个整数与 a,b 均互素,则这个整数拥有的素因子 a,b 都没有,把 a,b乘起来也凑不出这些素因子中的任意一个。

当然,这些用裴蜀定理也容易推出来。

这样,这个整数除以a 的余数有 φ(a) 种情况,除以 b 的余数有 φ(b) 种情况。又由中国剩余定理,这个整数除以 a,b的两个余数唯一确定了这个整数除以 ab 的余数(当然,如果这个整数在1,2,3,…,ab 的范围内,则这个整数显然也是唯一确定的)。再根据乘法原理,这个整数就可以取 φ(a)φ(b)个不同的值。

至此即证明了φ(ab)=φ(a)*φ(b) 是成立的。

接下来,我们的工具已经凑齐了,我们来推导任意正整数的欧拉函数计算公式:

第一步把 m进行分解,分解后的各个底数是互不相等的素数,各个指数是正整数;后面的计算则利用了上面的第三、四条性质。图中第三行已经可以作为公式,但是我们习惯上也用最后一行进行运算。

最后再来看一个很好玩的结论:对于任意正整数 n ,则它的所有正因子(所有约数)的欧拉函数求和恰好等于 n 。

写成公式就是

看起来很神奇,这个结论还有一个很简单的证法:

任取 n的一个正因子 d ,考虑在1,2,3,…, d 中与 d 互素的整数组成的集合。这个集合显然有 φ(d) 个数。现在让这个集合的每个数都乘以n/d (这当然也是个整数),则这个集合恰好是所有 1,2,3,…,n 中与 n 的最大公约数为 n/d的数构成的集合(不妨记作 A(d) ),它也含有 φ(d) 个数(这是因为两个数分别除以二者的最大公约数后,商互质)。

一个整数大于等于 1 小于等于 d ,等价于这个整数乘以 n/d 之后大于等于 1 小于等于 n。这个是显然没问题的。

一个整数与 d 互素即 (x,d)=1 ,等价于 x 乘以 n/d 之后与 d乘以n/d后(即n)的最大公约数为 n/d ,即(x*(n/d),d*(n/d))=1*n/d,这显然就是求最大公约数的两个数同时扩大某个倍数,二者的最大公约数当然也会扩大同样的倍数。

后面就快了,考虑n 的所有正因子 d ,那么由上述操作得到的所有 A(d) 显然两两交集为空,并集为 1 到 n 的所有整数(因为它们与 n的最大公约数肯定是 n 的约数,而 n/d 恰好可以取到 n 的所有约数)。我们立即得到所有 φ(d) 的和为 n 。

另外当然可以去直接计算。我们把 n 和它的任意一个正因子 d 分解素因数:

这样的话,利用欧拉函数的性质就可以进行如下变形:

注意左边的 r个求和号恰好表示 0<=l_i<=k_i 的意思。利用乘法分配律,这个式子显然是成立的:

右边每个中括号里的式子都好求,把求和的式子拆开来写,会发现可以一项一项消掉,最后每个中括号恰好等于 p_i 的 k_i次方。这就证明了这个式子等于 n 。

相关文章:

发表回复

您的电子邮箱地址不会被公开。