§ 8.3. Китайский алгоритм остатков: взаимно простые модули

Китайский алгоритм остатков так назван потому, что впервые был найден в «Учебнике математики мастера Сана», написанном между 287 и 473 годами нашей эры. В своей книге мастер Сан решал численные примеры, а потом выводил из них общие правила решения аналогичных задач. Более общий анализ той же проблемы с несколькими примерами можно найти в книге, написанной Цзинь Цзю-шао (Qin Jiushaq) в 1247 году. Аналогичные задачи рассматривались многими другими математиками, включая индийца Бхаскару (Bhaskara, VI век нашей эры) и Никомаха из Герасы. Историческую справку о теореме см. в [27].

Китайский алгоритм остатков — это простое обобщение метода, использованного при решении системы из § 8.2. Подробному изучению алгоритма и посвящен настоящий параграф.

Рассмотрим систему

Как и в § 8.2, из первого сравнения следует, что , где у — целое число. Подставляя вместо х во втором сравнении а , мы получаем: Другими словами,

Но благодаря § 8.1 мы знаем, что это сравнение имеет решение тогда и только тогда, когда наибольший общий делитель

тип делит . Для уверенности в том, что это условие выполнено, достаточно предположить, что Предположение равносильно тому, что имеет обратный элемент в скажем, а.

Теперь сравнение (3.2) легко решается. Умножая обе его части на а, получаем: Следовательно, где целое. Так как , то

Но Значит, найдется такое целое при котором Итак,

Преимущество такой записи решения в том, что а и 0 легко вычисляются. Действительно, так что находятся расширенным алгоритмом Эвклида, примененным к В итоге, если то при любом целом к число является решением системы (3.1).

А сколько решений имеет такая система сравнений? Бесконечно много, если мы имеем в виду целочисленные решения. Ведь при каждом конкретном выборе мы получаем новое решение, согласно формуле, выписанной выше. Рассмотрим этот момент более подробно. Предположим, что целые у удовлетворяют системе (3.1). Тогда Разность этих сравнений приводит к соотношению: т.е. у делится на Проделывая то же самое со вторым сравнением, получаем, что делится на А ввиду взаимной простоты шипи леммы из § 3.4, это доказывает делимость у на Значит, если х и у — целые решения системы (3.1), то Поэтому, хотя система и имеет бесконечно много решений, все они сравнимы друг с другом по модулю Другими словами, система имеет только одно решение в Но нельзя забывать, что все

наши выводы справедливы только благодаря предположению: Сведем все полученные факты в следующую теорему.

Китайская теорема об остатках. Пусть — взаимно простые натуральные числа. Система

имеет одно и только одно решение в

Хороший способ разобраться, действительно ли Вы поняли эту теорему, — рассмотреть ее геометрическую интерпретацию. Предположим, что у Вас есть таблица с клетками. Столбцы таблицы пронумерованы элементами а строки — элементами . В клетку таблицы, стоящую на пересечении столбца, соответствующего а и строки, соответствующей поместим целое число х, удовлетворяющее следующим условиям:

Скажем, что соответствующая клетка таблицы имеет координаты Поскольку мы можем считать число х представителем класса сопряженности по модулю т.е. реально х представляет некоторый класс

Что говорит об этой таблице китайская теорема об остатках? Предположим, что Из теоремы следует, что каждая клетка таблицы соответствует в точности одному целому, заключенному между т. е. одному классу из Таким образом, в разных клетках стоят разные числа и наоборот. Еще раз напомним, что модули у нас взаимно

просты. Приведем таблицу для

(см. скан)

Заметим, что таблица соответствует прямому произведению С первого взгляда может показаться, что для заполнения таблицы необходимо решить 20 систем линейных сравнений. Но китайская теорема об остатках подсказывает заполнять таблицу «в обратном порядке». Для целого числа х между найдем место в таблице, вычисляя его вычеты по модулю тип. Например, в нашем случае вычет 14 по модулю 4 равен 2, а по модулю Поэтому ему соответствует клетка с координатами (2,4).

Но это не последнее слово в науке; можно сделать еще проще. Реально, существует возможность заполнить всю таблицу целиком, не производя вычислений для отдельных чисел! Чтобы понять как, вспомним, что у нас есть геометрическая интерпретация множества четыре точки, расположенные на равных расстояниях друг от друга вдоль окружности, каждая из которых представляет один класс в Похожая картинка есть и для

В действительности нашу таблицу можно интерпретировать как плоскую карту, или план, представляющий некую расположенную в пространстве двумерную поверхность. Чтобы найти эту поверхность, мы поступаем следующим образом. Поскольку классы (горизонтальные координаты) можно считать расположенными вдоль окружности, мы склеим правую сторону таблицы с левой. Получится цилиндр. Но классы (вертикальные координаты) также удобно представлять

точками на окружности. Поэтому верх таблицы нужно склеить с низом. В результате получится поверхность, которая называется тором, напоминающая по форме бублик или баранку.

Вернемся к задаче о заполнении таблицы. Поскольку числа О, 1, 2 и 3 меньше и четырех, и пяти, они совпадают со своими вычетами по обоим этим модулям. Поэтому нам не нужно делать каких-либо вычислений для определения их координат, и мы сразу можем поместить их в таблицу:

(см. скан)

Заметим, что расставляя по очереди эти классы по клеткам таблицы, мы, начав с левого верхнего угла таблицы, переходили каждый раз на одну клетку вправо и одну вниз. А проставив четыре первых класса, уперлись в правую границу таблицы. Если бы в таблице был еще один столбец, то, придерживаясь сформулированного правила, мы поместили бы в нем 4, но на одну строчку ниже 3, т.е. в последней строке. Однако у нас нет этого лишнего столбца, не так ли? На помощь приходит геометрическая интерпретация таблицы. Склеив ее вертикальные границы, мы видим, что первый левый столбец таблицы можно считать идущим сразу за ее последним правым столбцом. В терминах несклеенной таблицы это означает, что мы должны «перепрыгнуть» с последнего столбца на первый, одновременно спустившись на одну строчку вниз. Следовательно, 4 нужно поставить на пересечение первого столбца

и последней строки таблицы:

(см. скан)

Кажется, у нас появилась новая проблема: мы дошли до нижней границы и опять не можем двигаться дальше. Но в силу геометрической картинки, нижняя и верхняя границы таблицы склеены, и мы можем перейти к первой строке таблицы. Только теперь нужно сместиться на один столбец вправо относительно предыдущего положения. Сделав это в нашем случае, мы получим:

(см. скан)

Мы можем повторять этот процесс, пока не заполним все клетки таблицы.