8] одно свойство Н.О.Д. 29

То же применимо и к разности двух чисел; чтобы доказать это, запишем второе число в виде ~ 2 (о возможно благодаря сделанному ранее замечанию) и вычтем его из первого. Тогда

{axi - byi) - {by - ах) = a{xi + х) - b{yi + у). Таким образом, свойство линейной зависимости от а и Ь сохраняется при сложении, вычитании и умножении на любое число.

Исследуем теперь в свете этого понятия алгоритм Евклида. Сами числа а и Ь, конечно, линейно зависят от а и Ь, так как

а = а(Ь + 1) - Ь(а), b = a{b) - b{a - 1). Первым уравнением алгоритма было уравнение

а = qb + с.

Так как b линейно зависит от а и Ь, то и qb линейно зависит от а и Ь, а так как а также линейно зависит от а и Ь, то этим свойством обладает и а - дЬ, т. е. с. Из следуюгцего уравнения тем же способом можно вывести, что d линейно зависит от а и Ь и так далее до тех пор, пока мы не дойдем до последнего остатка, равного h. Этим доказано, что h линейно зависит от а и Ь, а это и утверждалось.

В качестве иллюстрации рассмотрим пример, уже приводившийся в п. 6: положим а = 7200 и Ь = 3132. Используем уравнения алгоритма Евклида для того, чтобы выразить каждый из остатков через а и Ь, Первое уравнение

7200 = 2 . 3132 + 936

показывает, что

936 = а - 2Ь.

Второе уравнение

3132 = 3 • 936 + 324

дает

324 = Ь - 3(а - 2Ь) = 7Ь - За. Из третьего уравнения

936 = 2 . 324 + 288

получаем

288 = (а - 2Ь) - 2(76 - За) = 7а - 166. Четвертое уравнение

324 = 1 . 288 + 36

дает

36 = (76 - За) - (7а - 166) = 236 - 10а.

Это и есть искомое выражение наибольшего обгцего делителя 36 в виде разности двух кратных чисел а и Ь. Если мы хотим получить выражение, в котором а является первым слагаемым, достаточно положить

236 - 10а = (М - 10)а - {N - 23)6, где Ма = Nb.

Так как обгций делитель а и b равен 36, то (после сокрагцения на него) условия, связываюгцие М и 7V, принимают вид

200М = 87N.

Простейший выбор М и N {М = 87, N = 200) после подстановки дает

36 = 77а - 1776. Возврагцаясь к обгцей теории, выразим полученный результат в другой форме. Пусть а, 6, n - данные натуральные числа; требуется найти натуральные числа х и у так, чтобы выполнялось равенство

ах - by = п. (6)

Такое уравнение называется неопределенным (ибо оно однозначно не определяет х и у), или диофантовым, уравнением в честь Диофанта из Александрии (третий век нашей эры), написавшего знаменитый трактат по арифметике. Уравнение (6) не имеет решений, если п не кратно h - наибольшему обгцему делителю а и Ь, так как этот наибольший обгций делитель делит ах - by при любых X и у. Предположим теперь, что п кратно /г, скажем, п = mh. Тогда мы можем решить это уравнение; прежде всего решим уравнение

axi - byi = h.

(мы уже видели, как это сделать), после чего, умножив Xi и У1 на т, получим решение х = mxi, у = myi уравнения (6). Таким образом, линейное неопределенное уравнение (6) разрешимо в натуральных числах х иу тогда и только тогда, когда п кратно h, В частности, если а и b взаимно просты, так что /г = 1, то уравнение разрешимо для любого п.

Мы нашли условие разрешимости линейного неопределенного уравнения

ах -\- by = п

в целых числах х и у противоположных знаков: одно из них положительно, другое отрицательно. Вопрос о том, когда это

уравнение разрешимо в натуральных числах, труднее, и на него нельзя полностью ответить столь простым способом. Конечно, п должно быть кратно /г, но п должно быть также не слишком малым по отношению к а и Ь. Довольно легко доказать, что уравнение разрешимо в натуральных числах, если п кратно h и п > 2аЬ,

9. Разложение чисел на множители. Простейший способ разложить число на множители - это испытать, делится ли данное число на 2, на 3, на 5 и так далее, используя ряд простых. Если число N не делится ни на какое простое вплоть до \/]V, то оно само является простым, так как составное число имеет по крайней мере два простых множителя и они не могут быть оба больше \/N.

Это очень трудоемкий процесс, если раскладываемое число велико, поэтому составлены таблицы разложений на множители. Самой большой из доступных таблиц является таблица Ле-мера (Carnegie Institute, Washington Pub. No. 105, 1909), в которой приводится наименьший простой множитель любого числа вплоть до 10 000 000. Если наименьший простой множитель некоторого числа известен, то это число можно разделить на него; повторение этого процесса дает полное разложение числа на простые множители.

Многими математиками, в том числе Ферма и Гауссом, были открыты способы, сокраш;аюш;ие число шагов при разложении на множители большого числа. Для понимания большинства из этих способов нужно знать теорию чисел лучше, чем это здесь предполагается. Имеется, однако, один довольно простой метод Ферма, который описывается в нескольких словах.

Пусть N - данное число и m - наименьшее целое, для которого > N. Образуем числа

- 7V, (ш + If - TV, (m + 2)2 - TV, ... (7)

Если какое-нибудь из этих чисел будет равно точному квадрату, мы получим уравнение х - N = у из которого следует, что N = х - у = {х - у){х + у). Вычисление чисел (7) облегчается тем, что их последовательные разности возрастают с постоянной скоростью. С помош;ью таблицы квадратов Барлоу (Barlow) можно легко определить, какие из этих чисел являются точными квадратами. Этот метод удобен, если число N разлагается