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