Согласно теореме Малтона Ферма a^(p-1) mod (p) равно 1. Таким образом, a^k (p-1) mod (p) также будет 1, расщепив на k частей и применив модуль независимо, получим ' 1' . Я что-то упускаю?(a^k (p-1) + b) mod (p) здесь p - простое число, a a, b, k - целое число, большее 1 и не делящееся на p. Является ли это значение таким же, как (a^b) mod (p)?
-2
A
ответ
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
Тада.
0
Вы правы. В общем случае уравнение имеет вид a^(k * phi (n) + b) совпадает с a^b по модулю n , где phi обозначает функцию Эйлера-phi, а a взаимно проста с n.
Смежные вопросы
- 1. Является ли вероятность P (A, B) равной P (пересечение A)?
- 2. Являются {a^n | n> = 0} и {a^p | p = простое число} не является регулярным?
- 3. REGEX: \ b \ p [A-Z] + \ b
- 4. int * p = & a ++ и int * p = & ++ a
- 5. P (A заданный -B), если у вас есть P (A, данный B)
- 6. Как вычислить обратный k mod p
- 7. Является ли P таким же, как P-Complete?
- 8. Расчет (a^b)% MOD
- 9. Печать значения «p + p [3] -p [1]»
- 10. Как «unrender» a p: inputText на основе p: selectManyCheckbox выбор
- 11. разница между * p ++ и ++ * p
- 12. Как найти результат (2^n)% p?
- 13. A p: commandLink внутри p: dataTable не работает
- 14. Что такое тире в git? Например: -a -b -p
- 15. Быстрый n выбрать k mod p для больших n?
- 16. проверяет, находится ли нецелое число в диапазоне [a, b) - или [a, b], (a, b), (a, b]
- 17. Как "for (; * p; ++ p) * p = tolower (* p);" работа в c?
- 18. Вычисление nCr mod p эффективно, когда n очень велико
- 19. Учитывая, что a и b найдут m таких, что mod m = b mod m
- 20. Как `* (* (p + 1) +1) [7]` equal `p [1] [8] [0]`?
- 21. Нахождение найти a^s mod b
- 22. Новое в PARI/GP .. Как использовать PARI/GP для h (p-1/q) mod p
- 23. Распечатайте число с вероятностью P
- 24. Какова была бы сложность p = B^E?
- 25. recurDescents (p) и recurAncestors (p)
- 26. Python Pollard P-1 факторизация
- 27. Разница между `* p = &` и `p = &`
- 28. Имеет ли a/b mod m = (mod m)/(b mod m)?
- 29. В Mathematica, Как вычислить P (A), где P - многочлен, а A - квадратная матрица?
- 30. P завернуть или Обертка P
math.stackexchange.com? – Barmar
Я не получил никакого ответа там – Alex
@Alex вы разместили свой вопрос там ** десять минут назад **. Обычно вы должны подождать немного больше, чем ** десять минут **, прежде чем принимать решение переходить на другой сайт. И в любом случае этот вопрос явно не соответствует теме. – AakashM