Мода сезона (Теория Чисел)

lodanap


Знаю как в лоб решать, но не хочется все пятые степени от 1 до 17ти считать...
Может есть какой-нибудь более элегантный способ?

XTC-XTC

только одна задача?

lodanap

Нет, конечно, над второй думаю пока

margo11

ответ: ноль.
Группа вычетов по модулю p - циклическая. Пусть g - порождающий. Тогда, g^5 - тоже порождающий, т.к. порядок группы равен фи(17) = 16 - взаимно прост с 5. Значит, при разных x от 0 до 16 (17 = 0 mod 17) x^5 тоже бегает от нуля до 16. Значит и x^5 + 2 бегает от нуля до 16. Значит, это сумма равно сумме просто (x/p). Дальше понятно?

lodanap


Прикольно
Спасибо большое!
Оставить комментарий
Имя или ник:
Комментарий: