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