欧拉函数φ(n)的计算及欧拉定理

3 年前

Drifter

?he=human&level=vegetable"--

1 欧拉函数定义

在数论中，对正整数 n ， 欧拉函数φ(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 φ函数 （由高斯所命名）或是 欧拉总计函数 （totient function，由西尔维斯特所命名）。

例如φ(8) = 4，因为1,3,5,7均和8互质。

也可以从简化剩余系的角度来解释，简化剩余系(reduced residue system)也称既约剩余系或缩系，是m的完全剩余系中与m 互素的数构成的子集，如果模m的一个剩余类里所有数都与m互素，就把它叫做与模m互素的剩余类。在与模m互素的全体剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模m的一个简化剩余系。

（1，3，5，7）就构成了8的一个简化剩余系。

2 标准分解式

标准分解式：将质因数分解的结果，按照质因数大小，由小到大排列，并将相同质因数的连乘积，以指数形式表示，此种表示法称为标准分解式。

如2020的标准分解式是

3 欧拉函数计算方法

（1）先化为标准分解式形式

（2）再依照下式规则计算

例如：

上面的例子

但是获得大整数的标准分解式却很困难

RSA公钥密码体制的安全性就基于大整数的素数分解问题的难解性、

python代码：

import fractions
def phi(n):
    amount = 0
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1: