Теория чисел на ЮМШ
Ошибка.
Попробуйте повторить позже
— некий полином с целыми коэффициентами, 
и 
— целые числа. Построим последовательность 
, где 
, и 
и пусть 
— остаток от деления 
на 
.
1. Пусть 
. Докажите, что период последовательности 
(то есть, такое наименьшее 
, что
при достаточно больших 
) равен 2.
2. Найдите длину предпериода той же последовательности (то есть такое наибольшее 
, что 
, где 
—
период).
3. Назовем полином стабильным по модулю 
, если существует 
, такое что для любого 
найдется 
, для которого
. Докажите, что полином 
нестабилен по модулю 
, если 
является квадратом нечётного
числа.
4. Докажите, что многочлен 
стабилен для бесконечного числа натуральных 
.
Пункт 1, подсказка 1
Если мы докажем, что с какого-то момента a_(n+2) - a_n = a_(n+1) - a_(n-1) (mod 3^2022), то и требуемое тоже будет доказано. Попробуйте выразить a_(n+2) - a_n через a_(n+1) и a_(n-1).
Пункт 1, подсказка 2
Мы получаем, что если a_(n+1) - a_(n-1) делится на 3^k, то и a_(n+2) - an делится на 3^k. Теперь, если мы докажем, что a_(n+1) - a_(n-1) делится на 3^(k+1), то сможем сказать, что с какого-то момента k станет >= 2022. Попробуйте для этого доказать, что a_(n+1) и a_(n-1) имеют одинаковые остатки при делении на 3.
Пункт 1, подсказка 3
Для этого посмотрите на значение a_n по mod 3.
Пункт 2, подсказка 1
Как подсказывает нам прошлый пункт задачи, нужно рассматривать остатки от деления a_n на степени 3. Попробуйте найти таким способом зацикливание.
Пункт 2, подсказка 2
Отлично! Теперь мы знаем, что остатки от деления a_n на 9 и на 27 зацикливаются. Тогда, зная, что степень вхождения 3 в выражение a_(n+1) - a_(n-1) каждый раз растёт, попробуйте вывести рекуррентную формулу для этой степени вхождения.
Пункт 2, подсказка 3
Если v_n - степень вхождения 3 в a_(n+1) - a_(n-1), то v_2 = 1, v_3 = 2, v_(2k+1) = v_2k + 2 и v_(2k+2) = v_(2k+1). Теперь осталось лишь решить неравенство v_k < 2022.
Пункт 3, подсказка 1
Нам нужно определить такое B, чтобы для него нашлось A, такой, что ни один r_k не равен B. Сразу сделать это довольно трудно. Попробуйте для начала подставлять небольшие A и посмотреть на значения полинома.
Пункт 3, подсказка 2
Отлично! Мы знаем, что f(2) = 2. Очень удобно будет доказывать, что есть такое A, что не будет остатка 2, ведь M - квадрат нечётного числа. Осталось лишь подобрать такое A и доказать, что r_k никогда не равен 2. Попробуйте найти A так, чтобы в нём как слагаемое присутствовало q (M = q^2).
Пункт 3, подсказка 3
Можно взять A = 2 + k*q (k и q взаимно просты). Теперь попробуйте рассмотреть f(A) по mod M.
Пункт 4, подсказка 1
Доказать, что это верно для произвольного множество бесконечных чисел, не представляется возможным. Поэтому нужно определить, для каких чисел мы это будем делать. Предыдущие пункты задачи явно подсказывают, что M должна быть степенью какого-то числа. Попробуйте перебирать небольшие числа и посмотреть, является ли стабильным полином по этому модулю.
Пункт 4, подсказка 2
Так, теперь мы знаем, что для 7 многочлен стабилен. Тогда попробуем доказать, что это верно и для 7^k. Легче всего сделать это по индукции. База уже есть, осталось доказать переход. И победа!
1. Легко видеть, что остатки 
от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю 
тем более не равен 1.
Покажем что он равен 2.
Заметим, что 
Отсюда следует, что если 
делится на 
, то тем же свойством обладает и 
, а если вдобавок 
, 
дают
остаток от 1 деления на 3, то 
делится на 
.
Учитывая, что такая ситуация имеет место при каждом четном 
, получаем, что соответствующее 
может неограниченно увеличиваться,
в частности, 
делится на 
при некотором 
(а значит и при всех 
). Поэтому период 
равен
двум.
2. Выпишем остатки от деления 
на 9 и на 27: легко убедиться, что это 2-периодические последовательности 
и
соответственно.
Поэтому число 
не делится на 3 при нечетных 
, делится на 3, но не на 9 при 
и делится на 9, но не на 27 при
четных 
.
То есть если 
— степень вхождения 3 в число 
, то 
, 
а дальше 
и 
.
Отсюда легко видеть, что наибольшее 
такое, что 
равно 2022, то есть 
— последняя среди разностей вида
не кратная 
.
3. Пусть 
, тогда 
- нечетное число.
Заметим, что 
,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы
не получим 2.
Рассмотрим числа вида 
, где НОД
Нетрудно заметить, что 
То есть числа вида 
, где НОД
переходят в себя, но число 2 не имеет такого вида, поэтому полином 
нестабилен по модулю 
, если 
является квадратом нечётного числа.
4. Индукцией по 
докажем, что для 
многочлен 
стабилен.
Обозначим через 
, то что 
База 
Таким образом, имеем цикл длины 3 везде одинаковый.
Переход 
Пусть по модулю 
многочлен стабилизируется так, что всегда встретится 
Тогда по модулю 
остаток 
будет 
, что не зависит от 
, при 
, что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю 
.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
