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