5.27. Линейные диофантовы уравнения

Мы видели, как китайцы подошли к использованию евклидова алгоритма в задачах об остатках, где-то между третьим веком н. э. и Математическим трактатом Цинь Цзю-Шао 1247 года. Этот алгоритм также широко применялся в Индии в тот же самый период, начиная с Ариабхаты из Ариабхата в 499 г. н. э. Ариабхата родился в 476 г. н. э. и известен также как Ариабхата I, чтобы отличать его от другого математика с тем же именем, который жил около 950 г. н. э.

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

Теорема Критерий для решения в целых числах

Уравнение где — целые числа, имеет решение в целых числах делит с.

Доказательство. Если х и у — целые числа, тогда делит следовательно, если тогда делит с. Обратно, мы знаем из раздела 3.3, что есть целые числа тип, так что Следовательно, если делит с, мы имеем та делит с, стажем, Тогда решение уравнения

Как указано в разделе естественное следствие евклидова алгоритма, хотя Евклид, очевидно, не заметил его. Мы также не можем быть уверены, что его заметил Ариабхата, поскольку его книга содержит лишь несколько строк о задаче решения и они стали понятны усилиями позднейших комментаторов. Первым из них был Бхаскара I, который заметил в 522 г. н. э., что делением a и b на их задача сводится к решению задачи

где и что последняя задача всегда может быть решена. Таким образом, Бхаскара I допустил, что для некоторых целых чисел и отсюда следует, что после умножения обеих сторон на

Бхаскара I также ввел яркий термин для евклидова алгоритма, означающий пульверизатор. Числа a и b «пульверизуются» алгоритмом на меньшие и меньшие части, при этом меньшая часть является их Индийский пульверизатор был формой алгоритма деления с остатком, хотя, конечно, слово в равной степени применяется к вычитательной форме. Чтобы решить уравнение где делит с, пульверизатор сочетали с вычитанием, чтобы найти коэффициенты тип, так что та и умножением на соответствующий множитель, чтобы получить так что Примеры можно найти у Сринивасиенгара (1967).

Упражнения

(см. скан)

(см. скан)