Китайская теорема об остатках
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Пусть 
— натуральное число, а 
— простые числа. Обозначим через 
произведение первых 
из них.
Докажите, что существует натуральное число 
такое, что для каждого 
от 
до 
числа 
и 
взаимно
просты.
Подсказка 1
Рассмотрим одно фиксированное простое pᵢ. Какой остаток по модулю pᵢ нужно избежать, чтобы числа Pₙ и k+pᵢ не имели общих делителей?
Подсказка 2
Все числа Pₙ дают при делении на pᵢ не так уж много разных остатков. Посчитаем, сколько именно, и почему этого недостаточно, чтобы покрыть все возможные остатки.
Подсказка 3
Если некоторый остаток по модулю pᵢ никогда не встречается, то можно выбрать k так, чтобы именно он появился. Как совместить такие условия сразу для всех простых p₁, …, pₙ?
Рассмотрим произвольное число 
из набора. Попробуем подобрать для 
такой остаток по модулю 
чтобы 
никогда не входило в
Понятно, что 
иначе при 
условие нарушится. Числа 
суммарно дают не более 
остатка при делении на 
Таким образом мы поняли, что числа 
имеют не более 
различных остатков по модулю 
Нетрудно
понять, что 
потому что 
не меньше 
-го простого числа из натурального ряда, которое, в свою очередь, больше 
Но тогда
существует такой остаток 
который не встречается среди остатков чисел 
при делении 
Таким образом, можно взять
Осталось заметить, что по КТО существует такое 
что 
при 
что и
требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
