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