Легенда гласит, что китайские военные использовали математическую хитрость, чтобы скрыть численность своих войск. Этот же метод используется во многих областях современных математических исследований.
Представьте, что вы — полководец в Древнем Китае и хотите скрыть численность своей армии от противника. Но вам также необходимо знать точное количество бойцов. Чтобы узнать численность армии и не дать противнику возможность получить эти сведения, можно прибегнуть к интересной математической хитрости.
Во время утреннего построения ваши солдаты выстраиваются в ряд по пять человек. Вы заметили, что в последнем ряду у вас осталось трое солдат. Затем вы перестраиваете их в ряд по восемь человек, в результате чего в последнем ряду останется семь, а затем в ряд по девять, в результате чего в одном ряду находится два солдата. Ни разу не подсчитав всех своих солдат, вы имеете достаточно информации, чтобы определить общую численность армии. И при этом можете не называть точную цифру, которую может узнать враг.
Согласно одной легенде, древнекитайские полководцы неоднократно прибегали к такой хитрости. Неизвестно, зачем они так поступали и поступали ли вообще. Зато известно, что эта математическая техника, также известная как «Китайская теорема об остатках», была изобретена где-то между третьим и пятым веками нашей эры китайским математиком Сунь Цзы (не тот Сунь Цзы, который написал «Искусство войны» за 1000 лет до него).
Эта теорема позволяет восстановить целое число по множеству его остатков от деления на числа из некоторого набора попарно взаимно простых чисел. Сунь Цзы не смог доказать теорему, но это сделал индийский математик и астроном Ариабхата, который придумал процесс решения любого конкретного случая теоремы.
Китайская теорема об остатках дает вам отличный способ определения числа.
Чтобы лучше понять эту теорему, вернёмся к нашему примеру. Наша цель: найти целое число X, которое имеет остаток 3 при делении на 5 и остаток 7 при делении на 8 (позже мы добавим третье условие, что при делении на девять остаток будет 2). Математики называют это системой конгруэнции (системой соответствий) и пишут так:
X ≡ 3(mod 5)
X ≡ 7(mod 8)
Решение первой конгруэнции равно 3, так как 3 по модулю 5 равно 3. Если мы увеличим 3 на 5, их суммы также будут удовлетворять первой конгруэнции X может быть любым числом в последовательности 3, 8, 13, 18, 23 и так далее.
Наличие второй конгруэнции позволяет уточнить решение. Числа, которые удовлетворяют этой конгруэнции — оставляя остаток 7 при делении на 8, — это 7, 15, 23, 31 и так далее. Теперь нам нужно найти число, которое появляется в обоих списках:
3, 8, 13, 18, 23, 28, 33
7, 15, 23, 31, 39, 47, 55
Видите его? Наше загадочное число — 23. Но это не единственное решение.
Мы всегда можем найти другое число, взяв произведение наших делителей и добавив кратные ему числа к 23. Наши делители равны 5 и 8. Их произведение равно 40. Прибавьте 40 к 23, и мы получим 63, что также удовлетворяет обеим конгруэнциям. Как и 103, 143, 183, 223 и так далее. Таким образом, вы можете найти решение каждые 40 чисел, подключив разные целые числа для K в следующей формуле:
X=23+40×K
Однако наименьшее целое число, удовлетворяющее этим конгруэнциям, равно 23.
Если вы генерал и знаете, что у вас не более 300 солдат, то числа 23, 63 или 103 могут быть недостаточно точными. Тогда вы добавляете третье равенство к первым двум (опять же, убедитесь, что ваше новое число попарно взаимно просто с 5 и 8):
X ≡ 3(mod 5)
X ≡ 7(mod 8)
X ≡ 2(mod 9)
Какое число удовлетворяет всем трём конгруэнциям? Мы возвращаемся к нашему списку чисел: 23, 63, 103, 143, 183, 223. Ни одно из них не оставляет остатка от 2 при делении на 9. Однако следующее число в последовательности: 263. И если бы мы хотели большей точности, мы могли бы добавить четвертую конгруэнциям — или столько, сколько захочется.
До сих пор мы использовали делители, которые являются взаимно простыми. Но что, если мы не сможем выбрать делители? Например, предположим, что мы астрономы, следящие за двумя кометами с орбитальными периодами в четыре года и 10 лет. В последний раз они достигли своего перигелия — точки, где комета находится ближе всего к Солнцу, — в 1991 и 1997 годах соответственно. Как нам определить, когда в следующий раз они оба достигнут своих перигелиев в один и тот же год?
Китайская теорема об остатках по-прежнему может нам помочь. Когда делители не являются взаимно простыми, вместо того, чтобы использовать кратные их произведения для определения возможных решений, мы используем кратные их наименьшему общему кратному. Поэтому в данном случае вместо умножения 4 и 10 мы используем их наименьшее общее кратное: 20.
Теперь мы ищем загадочный год X, который удовлетворяет следующей системе соответствий:
X ≡ 1991(mod 4)
X ≡ 1997(mod 10)
Если мы продолжим следовать процессу, который использовали в предыдущих примерах, в этом случае добавляя кратные 20 к наименьшему целому числу, которое удовлетворяет обеим конгруэнциям (которое оказывается равным 7), то мы найдём общий год, в котором обе кометы достигают своих перигелиев: 2007 г.
Этот пример демонстрирует широкую применимость теоремы, что делает её полезной в практических целях. Например, в астрономии для расчёта древних календарей или выборе кирпичей правильного размера для здания (теорема, вероятно, использовалась для строительства Великой китайской стены). Спустя более 1500 лет теорема остается полезным способом решения современных проблем, включая шифрование RSA, современный протокол безопасности.
Но китайская теорема об остатках — это не просто инструмент. Она лежит в основе операции в фундаментальной ветви теории чисел, называемой модульной арифметикой, которая представляет собой способ выполнения математических вычислений в системах с меньшими числами, как мы это делали в примерах, которые мы проработали выше, с участием войск и комет.
Математики часто используют модульную арифметику для исследования самых глубоких вопросов в своей области. На протяжении веков центральным направлением исследований в теории чисел было определение того, когда различные типы полиномиальных уравнений, таких как x2+y2=z2, имеют целочисленные решения. Для любого полиномиального уравнения существует бесконечно много комбинаций, которые вы могли бы вычислить, что делает поиск методом перебора неосуществимым.
Но для начала вы можете сначала попытаться ответить на вопрос в модульной системе счисления, где действительно можно проверить все возможные значения. Есть много примеров такого подхода в действии. Например, в 17 веке Пьер Ферма бросил вызов британским математикам, доказывая, что уравнение y2=x3−2 имеет только две пары целочисленных решений: (3, 5) и (3, -5). Математики обнаружили, что первым шагом к решению этой проблемы было изучение проблемы в mod 4, что помогло им найти «точку опоры» и установить, что, по крайней мере, x должно быть нечётным.
В других случаях модульная арифметика может исключить возможность того, что полиномиальное уравнение имеет целочисленные решения. Во-первых, ищите решения в модульных системах счисления. Если вы их не найдёте, то можете взять то, что узнали, и перевести это в утверждения об отсутствии решений одного и того же уравнения среди всех целых чисел.
Если нет решений по простому модулю, то это означает ваше знание о том, что решений нет.
Вот такой любопытный пример того, как спустя более 1000 лет китайская теорема об остатках по-прежнему даёт ключи к более важным истинам, что делает её мощным математическим инструментом, даже если полководцам больше не нужно скрывать численность своих армий.
Что ещё интересного есть в блоге Cloud4Y
→ Изучаем своё железо: сброс паролей BIOS на ноутбуках
→ Реклама в Windows 11 сломала «Пуск» и панель задач некоторых пользователей
→ Клавиатуры, которые постигла неудача
→ Мониторинг СУБД VMware Cloud Director и vCenter Server Appliance с помощью Zabbix
→ Космический вызов: защита суперкомпьютеров от внеземной угрозы
Подписывайтесь на наш Telegram-канал, чтобы не пропустить очередную статью. Пишем не чаще двух раз в неделю и только по делу.
Автор: Cloud4Y
