费马小定理 取模 python

费马小定理是一个基本的数论定理，它指出如果p是一个质数，a是任意整数且a与p互质（即它们的最大公约数为1），那么a^(p-1) 与 p 同余。在Python中，我们可以使用取模运算符 % 来实现费马小定理。例如，如果我们要计算a的p-1次幂对p取模的结果，可以使用以下代码：

def mod_exp(a, p, m):
    result = 1
    for _ in range(p):
        result = (result * a) % m
    return result

在这个例子中，函数mod_exp接受三个参数a、p和m，分别代表底数、指数和模数。函数使用了一个循环来计算a的p次幂，并在每一步都对m取模，以避免溢出。使用这个函数，我们可以很容易地验证费马小定理。例如，如果我们要验证3^6 与 7 同余，可以使用以下代码：

a = 3
p = 6
m = 7
result = mod_exp(a, p-1, m)
print(result)  # 输出为1，表示3^6 与 7 同余

通过这种方式，我们可以利用费马小定理快速计算底数的指数次幂对模数取模的结果，并验证费马小定理在Python中的应用。