Алгебра и пакет Mathematica 5
Китайская теорема об остатках — функция ChineseRemainder
Хитрый китаец Сунь Цю около 2000 лет назад (конечно, это могло быть и 200 лет до нашей эры, и 200 лет после начала нашей эры) открыл правило "гай-йен" ("большое обобщение"), которое является частным случаем целочисленного аналога интерполяционной формулы Лагранжа для полиномов. (Правда, примерно в то же самое время, в 100 г. н. э., греческий математик Никомах знал точно тот же частный случай.) Полностью формула была сформулирована и доказана впервые, по-видимому, в 1734 году Л. Эйлером. Сформулируем китайскую (или греко-китайскую, как назвал ее Акритас, автор одного из широко известных учебников по компьютерной алгебре?) теорему об остатках и укажем соответствующее правило (формулу).
Пусть m1, m2, ..., mr — попарно взаимно простые модули (попарно взаимно простые положительные целые числа), m = m1, m2, ... mr — их произведение, а а, u1, u2, ..., ur — произвольные целые числа. Тогда существует ровно одно целое число и, такое, что а<u<а+m, удовлетворяющее всем сравнениям u = ui(modmi). Более того,
где ci — произведение всех модулей, кроме mi: сi = m/mi, a di=ci-1 (modmi) (т.е. dici = 1(modmi)).
Эта теорема имеет многочисленные применения в математике, информатике (машинная арифметика) и криптологии (секретные ключи). Для нахождения числа и, существование которого гарантировал хитрый китаец Сунь Цю, в пакете теории чисел существует "китайская" функция ChineseRemainder. ChineseRemainder [список_1, список_2] — это такое наименьшее целое неотрицательное число и, что Mod [и, список_2] = список_1. Чтобы ею воспользоваться, нужно сначала загрузить пакет теории чисел.
<<NumberTheory`NumberTheoryFunctions`
После загрузки пакета можно вызвать эту функцию.
ChineseRemainder[{0,1,2), {4, 9,121}]
244
Полученный ответ означает, что 244=0(mod4), 244=1(mod19) и 244=2(mod121)-С помощью функции Mod это легко проверить.
Mod[244,{4,9,121}]
{0,1,2}
Пример 7.5. "Задача о корзинке с яйцами". Есть одна очень старая задача, в которой используется китайская теорема об остатках. Вот современная формулировка задачи. Крестьянка (наверняка отличница местной школы, а может даже победительница олимпиад по поднятию тяжестей) несла по проселочной дороге на базар яйца. Однако по дороге очень быстро ехал экипаж с сеньором, и экипаж нечаянно зацепил корзинку, в которой были яйца. Корзинка опрокинулась, и яйца разбились. Сеньор пожелал возместить убытки и спросил, сколько яиц было в корзинке. Крестьянка ответила, что не помнит, однако вспомнила, что когда вынимала яйца парами, то оставалось одно яйцо, когда тройками, то — два яйца, когда семерками — то 6 яиц и, вообще, когда она вынимала по pi (pi — i-e простое число) яиц, то в корзинке оставалось ровно i яиц. И еще вспомнила, что так она делала для всех первых ста простых чисел. Спрашивается, какое наименьшее число яиц могло быть в корзинке. С помощью функции ChineseRemainder это число можно найти так.
Ну и корзинка, которая вмещала столько яиц!
