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