(a^k (p-1) + b) mod (p) здесь p - простое число, a a, b, k - целое число, большее 1 и не делящееся на p. Является ли это значение таким же, как (a^b) mod (p)?

Question

Согласно теореме Малтона Ферма a^(p-1) mod (p) равно 1. Таким образом, a^k (p-1) mod (p) также будет 1, расщепив на k частей и применив модуль независимо, получим ' 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.