китайская теорема об остатках

Ответ от ЂАНЮШКА!!![эксперт]
Несколько связанных утверждений известны под именем китайской теоремы об остатках. Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» ( _zh. 孙子算经|sūnzǐ suànjīng), предположительно датируемом третим веком н. э. .Если натуральные числа a_1, a_2, dots, a_n попарно взаимно просты, то для любых целых r_1, r_2, dots, r_n таких, что 0 leq r_i < a_i при всех i = 1, 2, dots, n, найдётся число N, которое при делении на a_i даёт остаток r_i при всех i = 1, 2, dots, n.Hidertitle = Доказательствоhidden = 1title-style = text-align: left;content-style = text-align: left;content =Применим индукцию по n. При n = 1 утверждение теоремы очевидно. Пусть теорема справедлива при n = k - 1, т. е. существует число M, дающее остаток r_i при делении на a_i при i = 1, 2, dots, k - 1. Обозначим : d = a_1 a_2cdots a_{k-1}и рассмотрим числа M, M + d, M + 2d,dots, M + (a_{k} - 1)d. Покажем, что хотя бы одно из этих чисел даёт остаток r_k при делении на a_k. Допустим это не так. Поскольку количество чисел равно a_k, а возможных остатков при делении этих чисел на a_k может быть не более чем a_{k} - 1 (ведь ни одно число не даёт остаток r_{k}), то среди них найдутся два числа, имеющих равные остатки (принцип Дирихле) . Пусть это числа M + sd и M + td при 0 leq sleq a_k- 1 и 0 leq t leq a_k - 1. Тогда их разность (M + sd) - (M + td) = (s - t)d делится на a_{k}, что невозможно, т. к. 0 < |s - t| < a_{k} и d = a_1 a_2 cdots a_{k-1} взаимно просто с a_{k}, ибо числа a_1, a_2,dots, a_k попарно взаимно просты (по условию) . "Противоречие. "Таким образом, среди рассматриваемых чисел найдётся число N, которое при делении на a_k даёт остаток r_k. В то же время при делении на a_1, a_2, dots, a_{k-1} число N даёт остатки r_1, r_2, dots, r_{k-1} соответственно. "Теорема доказана. "

Ответ от 22 ответа[гуру]