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