摘要：傳送門這個(gè)就是主角歐拉函數(shù)。在數(shù)論中，對(duì)正整數(shù)，歐拉函數(shù)是小于或等于的正整數(shù)中與互質(zhì)的數(shù)的數(shù)目。歐拉函數(shù)實(shí)際上是模的同余類所構(gòu)成的乘法群即環(huán)的所有單位元組成的乘法群的階。

Author: Jasper Yang

School: Bupt

gamma函數(shù)的求導(dǎo)會(huì)出現(xiàn)所謂的歐拉函數(shù)（phi），在一篇論文中我需要對(duì)好幾個(gè)歐拉函數(shù)求值，結(jié)果不能理解，立即去google，發(fā)現(xiàn)了一個(gè)開(kāi)源的python庫(kù)可以用來(lái)計(jì)算歐拉函數(shù)

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.

這個(gè)函數(shù)到這里并不能看懂用法和意義，下面我通過(guò)介紹兩個(gè)概念來(lái)讓大家慢慢理解這個(gè)過(guò)程。

在數(shù)論中，一個(gè)給定的n的totative是一個(gè)符合大于0并且小于等于n的k,并且這個(gè)k和n是互質(zhì)數(shù)（什么是互質(zhì)數(shù)呢）。

互質(zhì)數(shù)為數(shù)學(xué)中的一種概念，即兩個(gè)或多個(gè)整數(shù)的公因數(shù)只有1的非零自然數(shù)。公因數(shù)只有1的兩個(gè)非零自然數(shù)，叫做互質(zhì)數(shù)。

歐拉方程 $$ phi(x) $$ 就是在計(jì)算n的totative個(gè)數(shù)。
在n的乘法模下的totatives形成了模n乘法群( Multiplicative group of integers modulo n )。 --->后面這句涉及的群的知識(shí)我去維基上了解下后沒(méi)看懂，放棄了，未來(lái)有機(jī)會(huì)看看中文資料理解一下再添加進(jìn)來(lái)吧。 wiki傳送門

這個(gè)就是主角歐拉函數(shù)。

在數(shù)論中，對(duì)正整數(shù)n，歐拉函數(shù) $$ varphi (n) $$ 是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)（由高斯所命名）或是歐拉總計(jì)函數(shù)[1]（totient function，由西爾維斯特所命名）。
例如 $$ varphi (8)=4 $$，因?yàn)?,3,5,7均和8互質(zhì)。
歐拉函數(shù)實(shí)際上是模n的同余類所構(gòu)成的乘法群（即環(huán) $$ {mathbb {Z}}/n{mathbb {Z}} $$ 的所有單位元組成的乘法群）的階。這個(gè)性質(zhì)與拉格朗日定理一起構(gòu)成了歐拉定理的證明。

若n是質(zhì)數(shù)p的k次冪， $$ varphi (n)=varphi (p^{k})=p^{k}-p^{{k-1}}=(p-1)p^{{k-1}} $$ ，因?yàn)槌藀的倍數(shù)外，其他數(shù)都跟n互質(zhì)。

若 $$ 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的最大整數(shù) $ 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 $$

為什么會(huì)有兩個(gè)法則，一個(gè)是基本的計(jì)算而另一個(gè)是連乘，其實(shí)就是因?yàn)檎J(rèn)為所有的數(shù)都可以拆解成兩個(gè)素?cái)?shù)的k次冪的形式。

我需要的知識(shí)以上就足夠了，如果需要更多的理解，看下面的鏈接

歐拉函數(shù)wiki

PHI

這是個(gè)開(kāi)源的python語(yǔ)言的實(shí)現(xiàn)庫(kù)
我們主要使用里面的

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

phi函數(shù)

使用過(guò)程，
e = eulerlib.numtheory.Divisors(10000) # 這里的10000是最大值，默認(rèn)是1000
e.phi(100) # 求phi(100)

使用十分簡(jiǎn)單。

這個(gè)函數(shù)的實(shí)現(xiàn)源碼如下： 源碼傳送門

    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):    # 這個(gè)素?cái)?shù)的table一開(kāi)始就有了，從別的包導(dǎo)來(lái)的，去看定義就是maxnum以內(nèi)的所有素?cái)?shù)
            return num-1
        pfs = self.prime_factors_only(num) # 這個(gè)步驟就是找出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        # 這個(gè)//= 和 /=似乎沒(méi)有區(qū)別
                    tnum //= pdiv
                    if(tnum in self.primes_table):
                        result.append(tnum)
                        break
                    elif(tnum == 1):
                        break
            self.pfactonly_table[num] = result
            return result

源碼看起來(lái)也十分的簡(jiǎn)潔易懂，就是為了找出p1和p2然后就可以分別求phi值再相乘了。

paper done : 2017/4/19