欧拉函数有很多好玩的性质这裏补充一下...下次再说原根的事。
当然一般性的规律很难找不过还是能看出一些特性的,比如下面这个:
证明当然很容易只需注意到两個和为 m 的数要么都与 m 0与1互素吗,要么都不与 m 0与1互素吗(事实上这两个数分别与 m 的最大公约数是相同的)这样, {0,1,2,3,...,m-1} 中的绝大多数都可以配对剩下的只有 0 ,如果 m 是偶数则还剩下 m/2 而当 m>=3
时这两个数都不会与 m 0与1互素吗。
也就是说两个0与1互素吗的正整数相乘再求欧拉函数,等于两個数先求欧拉函数再相乘证明用到了计数的方法:我们用两种方法数一下 0,1,2,3,...,ab-1 中与 ab 0与1互素吗的整数的个数。
由前者推出后者:若一个整数与 ab 0與1互素吗它当然与 a,b 都找不出大于 1 的公因子。
由后者推出前者:若一个整数与 a,b 均0与1互素吗则这个整数拥有的素因子 a,b 都没有,把 a,b 乘起来也湊不出这些素因子中的任意一个
当然,这些用裴蜀定理也容易推出来
这样,这个整数除以 a 的余数有 φ(a) 种情况除以 b 的余数有 φ(b) 种情况。又由中国剩余定理这个整数除以 a,b 的两个余数唯一确定了这个整数除以 ab 的余数(当然,如果这个整数在 0,1,2,3,...,ab-1
的范围内则这个整数显然也是唯一确定的)。再根据乘法原理这个整数就可以取 φ(a)φ(b) 个不同的值。
接下来我们的工具已经凑齐了,我们来推导任意正整数的欧拉函數计算公式:
第一步把 m 进行分解分解后的各个底数是互不相等的素数,各个指数是正整数;后面的计算则利用了上面的第三、四条性质图中第三行已经可以作为公式,但是我们习惯上也用最后一行进行运算
最后再来看一个很好玩的结论:对于任意正整数 n ,则它的所有囸因子的欧拉函数求和恰好等于 n
看起来很神奇,这个结论还有一个很简单的证法:
任取 n 的一个正因子 d 考虑小于 d 的与 d 0与1互素吗的非负整數组成的集合。这个集合显然有 φ(d) 个数现在让这个集合的每个数都乘以 n/d (这当然也是个整数),则这个集合恰好是所有 0,1,2,3,...,n-1 中与 n 的最大公约數为 n/d 的数构成的集合(不妨记作
一个整数大于等于 0 小于 d 等价于这个整数乘以 n/d 之后大于等于 0 小于 n 。这个是显然没问题的
一个整数与 d 0与1互素吗即 (x,d)=1 ,等价于 x 乘以 n/d 之后与 n 的最大公约数为 n/d 即 (x*(n/d),n)=n/d,这显然就是求最大公约数的两个数同时扩大某个倍数结果当然也会扩大同样的倍数。
後面就快了考虑 n 的所有正因子 d ,那么由上述操作得到的所有 A(d) 显然两两交集为空并集为 0 到 n-1 的所有整数(因为它们与 n 的最大公约数肯定是 n 嘚约数,而 n/d 恰好可以取到 n 的所有约数)我们立即得到所有 φ(d) 的和为 n 。
另外当然可以去直接计算我们把 n 和它的任意一个正因子 d 分解素因數:
这样的话,利用欧拉函数的性质就可以进行如下变形:
右边每个中括号里的式子都好求把求和的式子拆开来写,会发现可以一项一項消掉最后每个中括号恰好等于 p_i 的 k_i 次方。这就证明了这个式子等于 n