ax + by = z\ (6)

где а и b - натуральные числа, ни одно из которых не является точным квадратом.

Отметим прежде всего, что такое уравнение может вообще не иметь решения (кроме тривиального решения х = у = z = О, которое мы не рассматриваем). Например, уравнение

2х + Зу = z

не разрешимо. В самом деле, можно считать, что х, у, z не имеют общего множителя, большего 1, откуда, в частности, следует, что ни j;, ни 2: не делятся на 3. Но тогда сравнение 2х = z (mod 3) невозможно, ибо 2 - квадратичный невычет по модулю 3.

Аналогичные рассмотрения применимы и к общему уравнению (6) и дают необходимые условия разрешимости этого уравнения; эти условия требуют разрешимости некоторых сравнений. Мы можем предполагать, что а и & свободны от квадратов, т. е. не делятся ни на какой квадрат, больший 1, ибо введение в коэффициенты а и Ь квадратных множителей не влияет на разрешимость уравнения.

Если уравнение (6) разрешимо, то, разделив в его решении числа X, у, Z на их общий множитель, мы получим решение этого уравнения, в котором х, у, z не имеют отличного от 1 общего множителя. Из уравнения (6) вытекает сравнение ах = z (mod b). При этом х иЬ должны быть взаимно просты; действительно, если бы они имели общий простой множитель, то этот множитель должен был бы делить х и z, поэтому Ьу делилось бы на квадрат этого множителя; с другой стороны, так как Ь свободно от квадратов, то этот простой множитель делил бы у, что невозможно. Умножая сравнение на х, где хх = 1 (mod &), получаем сравнение вида

а = а (mod&), (7)

в котором а = xz. Аналогично

Ь = (mod а) (8)

для некоторого целого (3. Другими словами, а должно быть квадратичным вычетом по mod Ь, аЬ - квадратичным вычетом

3] УРАВНЕНИЕ ах + by = 159

по mod а. Здесь мы используем термин квадратичный вычет в более общем смысле, чем в главе III: модули а и & не обязаны быть взаимно простыми.

Если Н. О. Д. чисел а и & равен /г > 1, то, помимо сравнений (7) и (8), для разрешимости уравнения (6) должно выполняться еще одно сравнение. Положим а = hai и & = /г&1, так что ai, &i, h попарно взаимно просты. В каждом решении (6) z должно делиться на /г, значит, aix + biy также должно делиться на h. Умножая aix + biy на bix., получаем сравнение вида

ai&i = -7 (mod h). (9)

Разрешимость сравнений (7), (8), (9) накладывает ограничения на а и &, необходимые для разрешимости уравнения (6). Заранее, однако, не очевидно, что если сравнения (7), (8), (9) разрешимы, то разрешимо и уравнение (6). Докажем теперь, следуя Лежандру, что в действительности это все же так. Мы хотим доказать таким образом, что уравнение (6), в котором а и b - свободные от квадратов натуральные числа, разрешимо тогда и только тогда, когда разрешимы сравнения (7), (8), (9).

Если а или b равно 1, то уравнение (6), очевидно, разрешимо. Если а = &, то условия (7) и (8) удовлетворяются тривиальным образом, а (9) приводит к 1 = -7 (mod а). В силу (VI, 5) отсюда следует, что а представимо в виде р + и наше уравнение удовлетворяется при х = р у = q z = р + q,

Предположим теперь, что а > & > 1. План доказательства состоит в том, чтобы вывести из (6) аналогичное уравнение с тем же самым b и с А вместо а, где 0<Л<аиЛ, & удовлетворяют таким же трем сравнениям, как а и Ь. Повторение этого процесса приводит к уравнению, в котором либо один из коэффициентов равен 1, либо оба коэффициента равны между собой. Как мы видели, такое уравнение разрешимо.

По предположению сравнение (8) разрешимо. Выберем решение для которого /? < а. Число 0 - Ь кратно а, поэтому можно выбрать Аи к так, чтобы выполнялось сравнение

/?2-& = аЛА:2, (10)

где к и А - целые числа и А свободно от квадратов (все квадратные множители - & входят в А:). Заметим, что к взаимно

просто с &, так как b свободно от квадратов. Отметим также, что А положительно, так как

аАе = -&>-&> -а,

значит, Ак О и поэтому >0, ибо b не является точным квадратом.

Подставив выражения у и z через новые переменные Y и Z по формулам*)

z = bY + (3Z, y = pY + Z, (11)

получим

z-by = {P-b){Z-bY).

Ввиду (10) уравнение (6) в новых переменных х, У, Z принимает вид

aAkiZ - bY) = ах". Полагая х = к АХ, получим новое уравнение

AX + bY = Z.

Если это уравнение разрешимо, то разрешимо и (6), так как подстановка (И) и уравнение х = кАХ дают целые, отличные от нуля значения х, у, z по X, У, Z,

Новый коэффициент а положителен, свободен от квадратов и удовлетворяет условию

ак ак а 4

так что А меньше а. Остается доказать, что АиЬ удовлетворяют сравнениям, аналогичным (7), (8), (9). Аналог (8) очевиден, ибо & = (mod А) ввиду (10).

Для доказательства аналога (7) заметим, что (10) можно разделить на /г, получив равенство

/г/?2 -bi= aiAP.

Кроме того, (7) эквивалентно сравнению ai = haf (mod &i). Следовательно,

hpl = hA{aikY (mod &i),

Вид подстановки (11) определяется равенством z - yVb = iP - Vb){Z - YVb).