math - (a^k(p-1)+ b) mod(p) 这里 p 是一个素数，a,b,k 是一个大于 1 的整数，a 不能被 p 整除。这个值是否与 (a^b)mod(p) 相同？

Question

根据费马小定理，a^(p-1) mod(p) 为 1。因此，a^k(p-1) mod(p) 通过拆分为 k 个部分并独立应用模数也将为 1，我们得到“1” . 我错过了什么吗？

Answer 1

我们知道，

((a mod N) * (b mod N)) mod N = (a*b) mod N

a^(p-1) mod p = 1

因此

( a^(p-1) * a^(p-1) * a^(p-1) * ... * a^(p-1) ) mod p = ( 1 * 1 * 1 * ... * 1) mod p = 1

多田。

Answer 2

你说的对。一般来说，等式成立，因为 a^(k*phi(n)+b) 与 a^b 模 n 一致，其中 phi 表示欧拉-phi 函数，a 与 n 互质。