Показатели и первообразные корни
Ошибка.
Попробуйте повторить позже
Дано 
-значное число 
Докажите, что найдётся такое натуральное 
что число 
имеет хотя бы 
цифр, и в десятичной
записи этого числа можно зачеркнуть не более, чем 
цифр с конца так, чтобы полученное число оканчивалось числом
Подсказка 1
Все подобные задачи, где какие-то цифры зачеркиваются в конце решаются похожими методами. Нужно научиться изменять число так, чтобы свойства из условия сохранялись, а после зачеркивания число менялось не очень сильно, например, не более чем на 1. Что подобного можно сделать в этой задаче?
Подсказка 2
Для решения задачи достаточно доказать, что существуют степени 2, дающие при делении на 10^(2n) остаток между A*10^n и (A+1)*10^n. Как искать такие степени? Что означает сформулированное утверждение на языке сравнений и показателей?
Подсказка 3
Докажите, что число 2 принадлежит к показателю 4*5^{m - 1} по модулю 5^m, и существует бесконечно много таких k, что 2^k сравнимо с r по модулю 10^{2n}. Выведите из этих двух утверждений решение задачи. Осталось лишь доказать эти два утверждения. Индукция вам в поможет.
Докажем, что для любого 
кратного 
и не кратного 
существует бесконечно много таких 
что 
Очевидно,
достаточно найти такие 
что 
(поскольку 
при 
Заметим, что число 
принадлежит к
показателю 
по модулю 
(то есть 
но никакие меньшие степени 
не сравнимы с 
по этому
модулю). Это утверждение несложно доказать по индукции: база 
проверяется непосредственно, а переход вытекает
из формулы 
— если 
делится на 
то вторая скобка делится на 
но не на 
поэтому для делимости произведения на 
первая скобка должны делиться на 
Тем самым мы
доказали, что все вычеты по модулю 
не кратные 
сравнимы со степенями двойки. При 
это даёт нам нужное
утверждение.
Докажем теперь, что в условии задачи всегда можно зачеркнуть ровно 
цифр, то есть, что существуют степени 
дающие при
делении на 
остаток между 
и 
Число 
является остатком степени 
(оно не кратно 
и кратно
Оно попадает в нужный интервал, потому что 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
