§ 8.2. Астрономический пример

В этом параграфе мы описываем один из методов решения систем линейных сравнений. Это очень древний алгоритм. Он применялся еще в античности для решения проблем астрономии. Мы начнем с задачи, сформулированной на современном языке, которая могла бы рассматриваться древними астрономами.

Три спутника пересекут меридиан города Лидса сегодня ночью: первый — в 1 ночи, второй — в 4 утра, а третий — в 8 утра. У каждого спутника свой период обращения. Первому на полный оборот вокруг Земли требуется 13 часов, второму третьему — 19 часов. Сколько часов пройдет (от полуночи) до того момента, когда спутники одновременно пересекут меридиан Лидса?

Посмотрим, как эта задача переводится на язык сравнений. Пусть х - количество часов, которые пройдут с 12 часов ночи до момента одновременного прохождения спутниками над меридианом Лидса. Первый спутник пересекает этот меридиан каждые 13 часов, начиная с часу ночи. Это можно записать как для некоторого целого Другими словами, Соответствующие уравнения для остальных спутников имеют вид:

Таким образом, три спутника одновременно пересекут меридиан Лидса через х часов, если х удовлетворяет эти трем уравнениям. Следовательно, для ответа на поставленный вопрос достаточно решить систему сравнений:

Заметим, что мы не можем складывать или вычитать уравнения системы, поскольку модули сравнений в них разные. Будем решать эту задачу, переходя от сравнений к уравнениям в целых числах. Так, сравнение соответствует диофантову уравнению: Заменяя х во втором сравнении системы на получаем:

Но 13 обратимо по модулю 15, обратный к нему элемент — это 7. Умножая последнее сравнение на 7 и переходя в нем к вычетам по модулю 15, имеем:

Значит, 4 может быть записан в виде: для какого-то целого и. Следовательно,

Заметим, что все числа вида являются целыми решениями первых двух сравнений системы (2.1). Наконец, подставим в третье сравнение вместо х выражение

Ввиду обратимости остатка 5 по модулю 19, на него можно сократить и увидеть, что . Переписывая это сравнение как диофантово уравнение, мы получим для некоторого целого Итак,

Какой отсюда можно сделать вывод относительно спутников? Напомним, что х - количество часов, которые пройдут от полуночи до момента одновременного прохождения спутников над меридианом Лидса. Поэтому нам нужно было найти наименьшее натуральное значение переменной х, удовлетворяющее системе (2.1). Мы это сделали. Поскольку решение системы: то ответ: 274. Итак, спутники одновременно пройдут над меридианом Лидса через 274 часа после 0 часов сегодняшней ночи, что соответствует 11 дням и 10 часам. Но общее решение системы дает больше информации. Прибавляя к 274 любое кратное 3705, мы получаем другое решение системы. Иначе говоря, спутники одновременно пересекают означенный меридиан каждые 3705 часов после первого такого момента, что соответствует 154 дням и 9 часам.

В следующем параграфе мы проведем детальный анализ примененного метода решения системы линейных сравнений. Заметим, что мы решали эту систему трех сравнений, рассматривая по два сравнения за раз. Действительно, сначала мы получили решение первых двух сравнений: что равносильно . Для поиска решений третьего сравнения мы решаем другую систему двух уравнений, а именно

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