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