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

Теорема 2. Если наибольший общий делитель dкоэффициентов а и bбольше 1, а свободный член с не делится на d, то уравнение ах + by = с не имеет решений в целых числах.

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

Задача

2. Дока­зать, что число не является рациональным числом.

Решение. Допустим противное, что — число рациональное.

Тогда существуют натуральные т, п такие, что .

Избавляясь от радикала и дроби, получим:

2n3 = т3(5)

Разложим числа т и n на простые множители (мы явно указы­ваем только простой множитель 2):

т = 2х• .

n = 2y• .

где х, у — неотрицательные целые числа (отсутствие простого мно­жителя 2 в разложении озна­чает, что соответствующий показатель степени равен нулю).

Тогда равенство (5) примет вид:

23y + 1• . = 23х• .

В силу единственности разложения натурального числа на про­стые множители

Зу + 1 = 3x 3(х - у) = 1.

Последнее уравнение является линейным диофантовым уравнени­ем вида ах + Ьу = с, причем коэффи­циенты а = 3, b = -3 делятся на 3, в то время как свободный член с = 1 — нет. Значит, это уравнение не имеет целочисленных решений, что означает ложность исходного предположения о рациональности числа .

.Будем теперь рассматривать только такие уравнения вида ах + by = с, в которых свободный член с делится на d = НОД(а; b). После деления обеих частей уравнения на d мы получим уравнение того же вида, но уже со взаимно простыми коэффициентами при неизвестных. Только такие уравнения мы будем рассматривать ниже в этом разделе.

В этом случае со стороны теоремы 2 нет препятствий к тому, что­бы уравнение имело целочислен­ные решения. Но отсюда, конечно, не следует, что решения обязаны быть.

На самом деле ответ на этот вопрос положительный.

Теорема 3. Любое уравнение ах + by = с, где НОД(а; b) = 1, имеет хотя бы одно решение в целых числах.

Доказательство. Уравнение ах + by = с имеет решение тогда и только тогда, когда число с входит в область значений М функции f(x; у) = ах + by от двух целочисленных аргументов х, у. Поэтому наша теорема фактически утверждает, что М = Z. Именно этот факт мы и будем доказывать.

Прежде всего отметим, что множество М содержит бесконечно мно­го чисел, например, 0= f (0; 0), а = f (1; 0), -а = f (-1; 0), а + b = f (1; 1) и т.д. Поскольку f(-x; -у) = -f(x; у), это множество имеет вид:

{ ., -и2, -п1, 0, n1, n2, .},

где n1 < n2 < . — натуральные числа.

Рассмотрим наименьшее положительное число из М, то есть n1 и докажем, что оно равно 1. Для этого разделим число |а| на n1 с остатком, то есть найдем такие целые числа q (неполное частное) и r (остаток), что |а| = n1q + r, причем 0 r п . Поскольку число n1 принадлежит множеству М, для некоторых целых х0 и у0 верно равенство n] = ах0 + bу0. Кроме того,

| а | = sgn (a) • а,

где sgn(а) = +1, если а > О, и sgn(а) = -1, если а < 0.

Тогда

г = | а | - n1g = sgn (а) •а - (ах0 + by0) -q = ax + by,

где x: = sgn(а) - x0q, у = -y0q — некоторые целые числа. Поэтому неотрицательное целое число г также принадлежит множеству М. Если бы число г было положительным, то условие 0 < r < n , кото­рому удовлетворяет г как остаток от деления на л,, означало бы, что в множестве М есть положительное число, меньшее, чем n1 чего быть не может. Значит, r = 0, то есть | а| (а вместе с ним и а) делится без остатка на n1.

Аналогичные рассуждения показывают, что и b делится без остатка на n1. Следовательно, n1 — общий делитель чисел а и b, a поскольку эти числа взаимно простые, число n1 равно 1.

Функция f(x; y) = ax + by обладает свойством: f(kx; ky) = k • f(x; у). Поэтому если некоторое число с М, то и число kc M. Как мы установили, 1 М. Значит, и любое целое число k входит в М, то есть М = Z. Это и означает справедливость нашей теоремы.

Имея в виду более сложные задачи, мы в качестве простого следствия из доказанной теоремы 3 получим еще одну важную теорему.

Теорема 4. Если числа а и b— целые, то множество значений функции f(x; y) = ax + byот двух целочис­ленных аргументов х и у совпадает с множеством чисел, кратных d = НОД(а; b), то есть с множеством { ., —2d, —d, 0, d, 2d, .}.

Доказательство. Так как d = НОД(а; b), числа а и b можно запи­сать в виде: а = da', b = db', причем числа а', b' — взаимно простые. Тогда f(x; у) = d •(а'х + bу). В силу теоремы 3, любое целое число n можно представить в виде а'х + b'у. Поэтому множество чисел, которые могут быть записаны в виде ах + by, есть { ., -2d, -d, 0, d, 2d, .}.

Приведенное доказательство теоремы 3 дает удобный метод нахождения частного (то есть конкрет­ного) решения при решении конкретных уравнений вида ах + by = с (если а и b взаимно простые целые числа):

1) нужно образовать две последовательности чисел:

- ., -2а, -а, О, а, 2а, . и - ., -2b, -b, О, b, 2b, .

(обычно достаточно выписать по несколько членов в обе стороны), и расположить их друг под другом так, чтобы положительные члены одной стояли под отрицательными членами другой;

2) затем в уме находить всевозможные суммы пар членов этих последовательностей, пока не най­дем пару, дающую в сумме с.

Рассмотрим, например, уравнение 2х - bу =1. Выпишем ряды чисел, кратных коэффициентам а = 2 и b = -5:

Из этой таблицы ясно, что второе число из первой строки (то есть -4), которое соответствует х = -2, и третье число из второй строки (то есть 5), которое соответствует у = -1, и дают в сумме 1. Та­ким образом, уравнение 2х- bу = 1 имеет частное решение х0 = -2, у0 = -1. Конечно, эту пару можно найти и проще, просто подставляя в исходное урав­нение в уме небольшие числа с тем, чтобы полу­чить верное равенст­во. Для несложных уравнений обычно поступают именно так.

В ряде случаев приходится выписывать довольно много (несколь­ко десятков) членов последовательно­стей ах и by. Тогда, конечно, описанный прием не очень удобен, так как требует больших затрат времени. В этой ситуации обычно рекомендуют использовать ал­горитм Евклида для нахождения наибольшего общего делителя коэффициентов а и b (само доказательство замечатель­ной теоремы 3 также может быть получено с помощью алгоритма Евклида). Мы продемонст­рируем этот алгоритм при решении задачи 6.

 Скачать реферат