博客

欧拉函数，也称为积性函数φ(n)，定义为小于等于n的正整数中与n互质的数的个数。具体地，如果n是一个正整数，那么φ(n) 应该等于满足1≤k≤n且gcd(k,n)=1的k的数量。

使用欧拉函数的一个主要应用是用于计算模n意义下的逆元，即令a是整数，m是正整数，求解ax≡1 (mod m)，其解x就是a的模m意义下的逆元，可以用欧拉函数求解。

计算公式是φ(n) = n × (1 – 1/p1) × (1 – 1/p2) × … × (1 – 1/pk)，其中p1,p2,…,pk是n的质因子。

下面展示两个使用欧拉函数的Python代码示例：

1.求解模m意义下的逆元

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

# 计算 4 在模 7 意义下的逆元
print(mod_inv(4, 7)) # output: 2

2.计算欧拉函数的Python代码示例

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# 计算10的欧拉函数
print(phi(10)) # output: 4

以上是关于欧拉函数的详细讲解和使用攻略，希望可以帮助到你。