导读 你们好，最近小活发现有诸多的小伙伴们对于欧拉函数公式，欧拉函数这个问题都颇为感兴趣的，今天小活为大家梳理了下，一起往下看看吧。1、...
你们好，最近小活发现有诸多的小伙伴们对于欧拉函数公式，欧拉函数这个问题都颇为感兴趣的，今天小活为大家梳理了下，一起往下看看吧。
1、性质1：当p为素数时，p^n的欧拉函数值，等于(p-1)p^(n-1)。
2、下面，我们举例验证。首先使用Prime函数产生10个素数，依次令n等于2,3,4,5,10计算欧拉函数。
3、产生的10个素数为第一行所示。
4、下边是对公式的验证，可见数值都是一致的。
5、下边我们举例简要说明原因。
6、p^n的质因子只有p。故与p^n不互素的只有p的倍数，即0,p,2p,3p...p^n-p。
7、这些不互素的一共有p^n/p个。
8、用完系中所有元素减去不互素的元素，剩下的元素就是缩系的元素。
9、元素个数为p^n-p^n/p=(p-1)p^(n-1)
10、性质2：欧拉函数的极性。
11、如图，计算m*n的欧拉函数值，其中m和n互素。
12、则EulerPhi[m*n]=EulerPhi[m]*EulerPhi[n]。
13、如果m和n不互素则不成立。
14、然后是一般情况下，欧拉函数的计算流程。其中用到了前两个性质。
15、把n质因数分解，然后把各个质因子带入最终公式，计算欧拉函数值。
16、证明过程如图。
17、如图举了一个实际的例子，计算EulerPhi[738]。
18、把这个数质因子分解，质因子有2,3,41。
19、把这三个数带入最终公式，算得240。
以上就是欧拉函数这篇文章的一些介绍，希望对大家有所帮助。
标签：
免责声明：本文由用户上传，如有侵权请联系删除！