欧拉函数(Euler' totient function )

摘要：传送门这个就是主角欧拉函数。在数论中，对正整数，欧拉函数是小于或等于的正整数中与互质的数的数目。欧拉函数实际上是模的同余类所构成的乘法群即环的所有单位元组成的乘法群的阶。

Author: Jasper Yang

School: Bupt

gamma函数的求导会出现所谓的欧拉函数（phi），在一篇论文中我需要对好几个欧拉函数求值，结果不能理解，立即去google，发现了一个开源的python库可以用来计算欧拉函数

class eulerlib.numtheory.Divisors(maxnum=1000)
    Implements methods related to prime factors and divisors.

    Parameters:    maxnum – Upper limit for the list of primes. (default = 1000)
    divisors(num)
        Returns a list of ALL divisors of num (including 1 and num).
        
        Parameters:    num – An integer for which divisors are needed.
        Returns:    A list [d1,d2,...dn] of divisors of num
    
    phi(num)
        Returns the number of totatives of num

        Parameters:    num – Integer for which number of totatives are needed.
        Returns:    Number of totatives of num

Note A totative of an integer num is any integer i such that, 0 < i < n and GCD(i,num) == 1.
Uses Euler’s totient function.

这个函数到这里并不能看懂用法和意义，下面我通过介绍两个概念来让大家慢慢理解这个过程。

在数论中，一个给定的n的totative是一个符合大于0并且小于等于n的k,并且这个k和n是互质数（什么是互质数呢）。

互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。

欧拉方程 $$ phi(x) $$ 就是在计算n的totative个数。
在n的乘法模下的totatives形成了模n乘法群( Multiplicative group of integers modulo n )。 --->后面这句涉及的群的知识我去维基上了解下后没看懂，放弃了，未来有机会看看中文资料理解一下再添加进来吧。 wiki传送门

这个就是主角欧拉函数。

在数论中，对正整数n，欧拉函数 $$ varphi (n) $$ 是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数[1]（totient function，由西尔维斯特所命名）。
例如 $$ varphi (8)=4 $$，因为1,3,5,7均和8互质。
欧拉函数实际上是模n的同余类所构成的乘法群（即环 $$ {mathbb {Z}}/n{mathbb {Z}} $$ 的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。

若n是质数p的k次幂， $$ varphi (n)=varphi (p^{k})=p^{k}-p^{{k-1}}=(p-1)p^{{k-1}} $$ ，因为除了p的倍数外，其他数都跟n互质。

若 $$ n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}} $$

则 $$ varphi (n)=prod _{{i=1}}^{r}p_{i}^{{k_{i}-1}}(p_{i}-1)=prod _{{pmid n}}p^{{alpha _{p}-1}}(p-1)=nprod _{{p|n}}left(1-{frac {1}{p}} ight) $$
其中 $$ alpha _{p} $$ 是使得 $$ p^{{alpha }} $$ 整除n的最大整数 $ alpha $（这里 $$ alpha _{p_{i}}=k_{i} $$ )。

例如 $$ varphi (72)=varphi (2^{3} imes 3^{2})=2^{{3-1}}(2-1) imes 3^{{2-1}}(3-1)=2^{2} imes 1 imes 3 imes 2=24 $$

为什么会有两个法则，一个是基本的计算而另一个是连乘，其实就是因为认为所有的数都可以拆解成两个素数的k次幂的形式。

我需要的知识以上就足够了，如果需要更多的理解，看下面的链接

欧拉函数wiki

PHI

这是个开源的python语言的实现库
我们主要使用里面的

eulerlib.numtheory.Divisors(maxnum=1000)下的

phi函数

使用过程，
e = eulerlib.numtheory.Divisors(10000) # 这里的10000是最大值，默认是1000
e.phi(100) # 求phi(100)

使用十分简单。

这个函数的实现源码如下： 源码传送门

    def phi(self,num):
        """Returns the number of `totatives 
        `_ of *num*
        
        :param num: Integer for which number of totatives are needed.
        :returns: Number of totatives of *num*
        
        .. note::
        
            A totative of an integer *num* is any integer *i* such that,
            0 < i < n and *GCD(i,num) == 1*.
        
        Uses `Euler"s totient function 
        `_.
        """
        if(num < 1):
            return 0
        if(num == 1):
            return 1
        if(num in self.primes_table):    # 这个素数的table一开始就有了，从别的包导来的，去看定义就是maxnum以内的所有素数
            return num-1
        pfs = self.prime_factors_only(num) # 这个步骤就是找出p了
        prod = num
        for pfi in pfs:
            prod = prod*(pfi-1)/pfi
        return prod



    
    def prime_factors_only(self,num):
        """Returns the `prime factors 
        `_ *pf* :sub:`i` of *num*.
        
        :param num: An integer for which prime factors are needed
        :returns: A list [pf1,pf2,...pfi] of prime factors of *num*
        """
        if num in self.pfactonly_table:
            return self.pfactonly_table[num]
        elif ((num < 2) or (num > self.limit)):
            return []
        elif num in self.primes_table:
            self.pfactonly_table[num] = [num]
            return [num]
        else:
            result = []
            tnum = num
            for prime in self.primes_table:
                if(tnum%prime==0):
                    result.append(prime)
                    pdiv = prime*prime
                    while(tnum%pdiv == 0):
                        pdiv *= prime
                    pdiv //= prime        # 这个//= 和 /=似乎没有区别
                    tnum //= pdiv
                    if(tnum in self.primes_table):
                        result.append(tnum)
                        break
                    elif(tnum == 1):
                        break
            self.pfactonly_table[num] = result
            return result

源码看起来也十分的简洁易懂，就是为了找出p1和p2然后就可以分别求phi值再相乘了。

paper done : 2017/4/19