python实现欧拉定理

欧拉定理是数论中的一个基本结果，它指出：对于任意两个正整数a和n，如果它们互质（即a和n的最大公约数gcd(a, n)等于1），那么a^φ(n) ≡ 1 (mod n)，其中φ(n)是欧拉函数，表示小于n且与n互质的正整数的数量。

在Python中，你可以使用内置的math库或者自定义函数来实现欧拉定理：

import math

def euler_theorem(a, n):
    # 检查是否互质
    if math.gcd(a, n) != 1:
        raise ValueError("a and n must be coprime")
    
    # 计算欧拉函数φ(n)
    phi_n = len([i for i in range(1, n) if math.gcd(i, n) == 1])
    
    # 使用模运算计算 a 的 φ(n) 次方除以 n 的余数
    result = pow(a, phi_n, n)
    
    return result

# 示例
print(euler_theorem(7, 10))  # 输出: 1，因为7^4 % 10 = 1

在这个例子中，`pow()`函数用于计算幂次运算，它会自动处理模运算，避免溢出。注意，如果你需要计算更大的数字，可能需要使用更高效的算法，如中国剩余定理等。