"Имеются вещи, число их неизвестно. Если считать их тройками, то остаток 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г.)