китайская теорема об остатках
Sep. 3rd, 2013 07:47 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva"Имеются вещи, число их неизвестно. Если считать их тройками, то остаток 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г.)
Эта задача - из древнекитайского математического трактата Сунь Цзы (это имя автора; не путать с другим Сунь Цзы, автором "Искусства войны"). Трактат был написан где-то между 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г.)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-09-03 04:59 pm (UTC)no subject
Date: 2013-09-03 05:01 pm (UTC)Сейчас попробую перечитать и разобраться.
no subject
Date: 2013-09-03 05:21 pm (UTC)no subject
Date: 2013-09-03 07:58 pm (UTC)no subject
Date: 2013-09-03 05:39 pm (UTC)А Сунь Цзы просто решал себе задачу, и думать не думал, что из задачи через 1000 лет сделают теорему.
Могло такое быть?
no subject
Date: 2013-09-03 08:05 pm (UTC)Так и эта задача - нет причин считать, что именно набор в 3,5,7 был важен Сунь Цзы, скорее всего, он просто взял такой простой пример, чтобы продемонстрировать, как решать задачи такого типа. Конечно, вы правы в том, что он не считал, что вывел какую-то там теорему, а просто показывал, как решать практическую задачу (практическую, потому что подобного рода задачи встречаются при расчете календарей). Увы, в этом конкретном случае он не объясняет достаточно понятно читателю, как решать *любую* задачу такого рода, потому что непонятно из его текста, откуда взялись "магические числа". Возможно, это недочет, а возможно, он написал, но текст испортился по дороге, итд.
no subject
Date: 2013-09-03 06:24 pm (UTC)Что имеется в виду, если речь идёт о примере с конкретными делителями, конкретными остатками и с единственным ответом 23?
Если говориться о случаях, когда сумма больше 106, то это значит, что ответов Сунь Цзы предполагал множество, а 23 - это наименьшее из решений.
В таком случае, можно говорить о том, что Сунь Цзы предлагал алгоритм, но только алгоритм поиска решений именно этой задачи с конкретными делителями и остатками, а не алгоритм решения всей теоремы, как она была сформулирована в 13 веке.
То есть он по-видимому не знал, что по такому же принципу можно действовать и с другими делителями и другими остатками.
Как вы считаете?
no subject
Date: 2013-09-03 08:08 pm (UTC)no subject
Date: 2013-09-03 08:26 pm (UTC)no subject
Date: 2013-09-03 06:46 pm (UTC)попробую позже
no subject
Date: 2013-09-03 11:49 pm (UTC)no subject
Date: 2013-09-04 06:42 am (UTC)формула N=23+105k, сейчас попытаюсь понять почему.
3*5*7=105
23-первое правильное рещение.
Красивая задачка.
no subject
Date: 2013-09-04 07:55 am (UTC)3, 2 в отстатке, 5, 3 в остатке, 7 и 4 в остатке. Первый член получается 53, а почему не понятно.
Всего есть 48 сочетаний разных остатков.