Показатели и первообразные корни
Ошибка.
Попробуйте повторить позже
Найдите все простые 
такие, что остатки чисел 
при делении на 
различны.
Подсказка 1
Для начала стоит понять хоть что-то про вычеты пятой степени. Поймите сколько их, как они устроены. Для этого обратитесь к первообразным корням.
Подсказка 2
Докажите, что вычетов пятой степени ровно k, и их можно записать как первообразный корень в степенях 1, 2, 3, ..., k. Непонятно, как в терминах первообразных корней понять, что нужные нам числа - это именно 1, 2, 3, ..., k. Раз не получается сказать про объекты по отдельности, то нужно посмотреть сразу на все объекты. Рассмотрите какие-либо симметричные функции от k переменных.
Подсказка 3
Вычеты пятой степени, как мы уже поняли, образуют геом. прогрессию. У нее хорошо считается сумма и оказывается, что по модулю p она равна 0. Тогда и сумма пятых степеней чисел 1, 2, 3, ..., k равна 0. Как ее можно посчитать?
Подсказка 4
Попробуйте выразить сумму пятых степеней первых чисел через симметрические функции, либо угадать ответ и проверить его по индукции.
Для начала покажем, что вычетов пятой степени ровно 
по модулю 
Пусть 
первообразный корень по модулю 
Тогда все ненулевые остатки можно записать как 
Так как
первообразный корень, то если пятые степени каких-то остатков 
совпадают, то 
кратно 
то есть 
кратно 
значит, все остатки разбиваются на 
групп по 
чисел, пятые степени которых дают одинаковый результат по модулю
Все эти остатки пятой степени можно записать как 
Сумма всех этих остатков равна 
Значит, если остатки чисел 
при делении на 
различны, то это все остатки пятой степени, а, значит, по доказанному ранее
сумма пятых степеней этих чисел равна нулю по модулю 
Воспользуемся следующей формулой
которую можно доказать по индукции. Если это выражение равно нулю по модулю 
то 
кратно 
Далее все
сравнения по модулю 
Тогда 
Нетрудно проверить, что такое 
действительно подходит.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
