Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

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

"Имеются вещи, число их неизвестно. Если считать их тройками, то остаток 2; если считать их пятерками, то остаток 3; если считать их семерками, то остаток 2. Спрашивается, сколько вещей?"

Эта задача - из древнекитайского математического трактата Сунь Цзы (это имя автора; не путать с другим Сунь Цзы, автором "Искусства войны"). Трактат был написан где-то между 3 и 5 веками нашей эры, точнее неизвестно. Требуется найти число, которое при делении на три дает остаток 2, на пять остаток 3, на семь остаток 2. Что такое число существует, и как его найти - есть частный случай теоремы, которую называют "Китайской теоремой об остатках" именно из-за этой задачи. На западе ее открыли на тысячу лет позже, в 13-м веке.

Вот решение задачи, из того же трактата:

"Ответ: 23.

Способ: при счете их тройками и остатке 2 установи 140; при счете их пятерками и остатке 3 установи 63; при счете их семерками и остатке 2 установи 30. Сложи это, получишь 233. Из этого вычти 210 и получишь [искомое]. Вообще [если] при счете их тройками остаток 1, то установи 70; [если] при счете их пятерками остаток 1, то установи 21; [если] при счете их семерками остаток 1, то установи 15. [Если сумма] больше 106, то вычитай 105 и получишь [искомое]".

Сначала не вполне понятно, откуда берутся эти числа, но можно разобраться. Здесь вторая половина решения, начиная со слов "вообще", важнее первой. Объясняется, как поступать в частном случае, когда требуется добиться остатка 1 по модулям 3,5,7. Казалось бы, зачем тогда нужно что-то считать, просто возьми число 1, у него тривиальным образом есть нужные остатки. Но дело в том, что способ решения для этого частного случая потом обобщается на любые желаемые остатки.

Предлагается взять числа 70,21,15 и сложить, и легко проверить, что их сумма 106 дает остаток 1 при делении на 3,5,7. Почему так получилось, и что это за числа? Число 70 дает остаток 1 при делении на 3 и делится без остатка на оба остальных числа, 5 и 7. То же самое с другими: 21 дает остаток 1 при делении на 5, и делится без остатка на 3 и 7, и так далее. Значит, если мы возьмем их сумму, и посмотрим на остаток при делении на 5, например, то первое и третье слагаемое дадут остаток 0, т.к. они делятся на 5, а второе даст остаток 1. И то же самое случится при делении на 3 и 7: одно из слагаемых даст нужный остаток 1, остальные будут делится без остатка.

Теперь предположим, что мы хотим добиться не остатков 1,1 и 1, а остатков 2,3 и 2, как в условии. Просто берем эти "магические" числа 70, 21 и 15 и умножаем вначале на желаемые остатки, перед сложением: 70*2 + 21*3 + 15*2 = 233. Теперь при делении на 3, скажем, первое слагаемое даст остаток 2, а остальные два слагаемых как делились на 3 без остатка, так и продолжают делиться, так что они не мешают. Из этого числа 233 можно вычесть любое кратное 105 (105 = 3*5*7, произведение всех делителей), и это не изменит остатки от деления на 3,5,7, так что можно заменить 233 на 233-210=23. Это и есть то, что написано в первой части решения. Из того, что есть вторая часть, понятно, что в первой части числа 140,63,30 взялись не "от фонаря", а именно по этому методу, хоть это и не сказано прямо.

Откуда же нашлись числа 70,21,15? В тексте это не объясняется никак. Может, так: поскольку мы хотим, чтобы первое число делилось на 5 и 7 без остатка, ясно, что оно должно быть кратным 5*7=35. Поэтому просто будем брать кратные 35: 35,70,105 итд. пока не дойдем до числа, которое дает 1 при делении на 3 (второе требование к этому числу). Это получается 70. С двумя оставшимися "магическими" числами нам повезло: это просто произведения 21=3*7 и 15=3*5, и так удачно получилось, что они уже дают нужный остаток 1 при делении на 5 и 7 соответственно. Если б не давали, мы бы тоже брали их кратные, пока не нашли бы нужное.

Вышеописанное - уже полное описание алгоритма решения китайской теоремы об остатках в общем случае. Его можно применять к любому набору попарно простых делителей, а не только 3,5,7. Но поскольку в трактате это подробно не написано, считается, что Сунь Цзы решил только частный случай. Мне кажется, однако, что он нашел что-то вроде вышеописанного - иначе я не понимаю, откуда он взял числа 70,21,15.

(цитаты из русского перевода Эльвиры Березкиной, который был опубликован ровно полвека назад, в 1963г.)
Tags: математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 13 comments