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

Источником этой теоремы является следующая задача, встречающаяся в Mathematical Manual (Математическом наставлении) Сунь-цзы в конце третьего века н. э. Требуется найти число, которое при делении на 3 дает остаток 2, при делении на 5 — остаток 3 и при делении

на 7 — остаток 2. Ответ легко можно найти с помощью эксперимента: это 23, но Сунь-цзы предлагает следующее объяснение, предположительно, чтобы указать общий метод.

[Из перевода Математического наставления Сунь-цзы Лама и Анга (1992), с. 178]

Числа 140, 63 и 30 выбраны из-за следующих свойств:

Следовательно, их сумма 233 обязательно дает остатки 2, 3, 2 при делении на 3, 5, 7, соответственно. Поскольку дает остаток при делении на 3, 5 и 7, мы можем вычесть 105 из 233 и получить меньшее число, которое дает те же самые остатки при делении на 3, 5 и 7. Вычитание 105 дважды дает наименьшее решение, 23.

Но почему, в частности, выбираем 140, 63 и 30? Не будет ли проще выбрать 35 вместо 140, потому что

Сунь-цзы продолжает объяснение:

Видимо, он начал с потому что это наименьшее кратное 5 и 7, дающее остаток 1 при делении на 3, затем умножил на 2, чтобы получить число, дающее остаток 2 при делении на 3.

Числа 63 и 30 также можно объяснить таким образом. Наименьшее кратное 3 и 7, которое дает остаток 1 при делении на Поэтому, есть кратное 3 и 7, которое дает остаток 3 при делении на 5. Аналогичным образом, есть наименьшее кратное 3 и 5, которое дает остаток 1 при делении на 7, поэтому 30 — наименьшее кратное 3 и 5, которое дает остаток 2 при делении на 7.

В этот момент возникает интересный вопрос. Если Сунь-цзы имел в виду, что это является общим методом, с целыми числами вместо 3, 5 7, ему необходимо было знать, что имеется кратное которое дает остаток 1 при делении на Знал ли он это? Такое число это то, что сейчас мы называем обратной величиной и задача Сунь-цзы, вероятно, первый случай в истории математики, где потребовались эти обратные величины.

Метод решения Сунь-цзы в полной общности впервые дан в Математическом трактате в девяти книгах Цинь Цзю-Шао в 1247 году. Он решил ключевую задачу отыскания обратных величин с помощью евклидова алгоритма. При заданных мы из раздела 2.4 знаем, что есть целые числа тип, так что

Но тогда

поэтому дает остаток 1 при делении на обратная величина Цинь Цзю-Шао нашел пробежав евклидовым алгоритмом по затем подставив обратно, чтобы найти тип при Он назвал это «методом отыскания 1».

Нетрудно показать (упражнение 5.2.1), что имеет обратную величину а только, если Таким образом в китайской задаче об остатках нам, в целом, нужны делители, которые должны быть относительно простым числом. Метод обратных величин тогда дает следующее.

Теорема Китайская теорема об остатках. Если взаимно простые целые числа, и любые целые числа 0, тогда есть целое число так что дает остаток при делении на для каждого

Эта теорема множество раз появлялась в истории теории чисел и часто была средством продвижения новых важных понятий и результатов. Ее позднейшее развитие в Китае описано у Либбрехта (1973). Когда ее, наконец, открыли в Европе, Эйлер и Гаусс отлично ею воспользовались.

Упражнения

(см. скан)