Линейные диофантовые уравнения (стр. 2 из 4)
.Будем теперь рассматривать только такие уравнения вида ах + 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.
На примере следующей задачи мы продемонстрируем, как с помощью частного решения уравнения ах + by = с можно свести дело к решению соответствующего однородного уравнения ах + by= 0 и, применяя теорему 1, получить полное решение.
Задача 3. Остаток от деления некоторого натурального числа n на 6 равен 4, остаток от деления nна 15 равен 7. Чему равен остаток от деления nна 30?
Решение. Тот факт, что остаток от деления числа nна 6 равен 4, означает, что существует неотрицательное целое х такое, что n = 6х + 4. Аналогично, существует неотрицательное целое yтакое, что n= 15у + 7. Исключая из этих равенств число n, для х и у получим уравнение
2х-бу-1. (6)
Чтобы решить это уравнение, прежде всего, найдем какое-нибудь частное решение в целых (не обязательно неотрицательных) числах. Мы это уже сделали выше, когда разбирали пример, иллюстрирующий метод поиска частных решений линейных диофантовых уравнений; в нашем случае в качестве такого частного решения можно взять, например, х0 =-2, y0 =-1, так что верно равенство
2• (-2)-5• (-1)=1.(7)
Вычитая из уравнения (в) равенство (7), получим:
2(х + 2) = 5(y + 1).
Общее решение этого уравнения в целых числах имеет вид:
х + 2 = 5k, у + 1 = 2k,
где k— произвольное целое число. Чтобы числа х и у были неотрицательными, параметр kдолжен быть натуральным числом. Теперь для числа nимеем:
n= 6х + 4 = 6(5k - 2) + 4 = 30k - 8 = 30(k - 1) + 22.
Поскольку целое число (k — 1) неотрицательно, это равенство означает, что остаток от деления nна 30 равен 22.
Ответ: 22.
Задача 4. Фирма продавала чай в центре города по 7 руб., а кофе по 10 руб. за стакан; на вокзале — по 4 руб. и 9 руб. соответственно. Всего было продано за час 20 стаканов чая и 20 стаканов кофе, при этом выручка в центре и на вокзале оказалась одинаковой. Сколько стаканов кофе было продано в центре?
Решение. Пусть nи т соответственно — количество стаканов чая и кофе, проданных в центре города. Тогда количество стаканов чая и кофе, проданных на вокзале, будет равно 20 - nи 20 — т соответственно. По смыслу задачи переменные n и т — неотрицательные целые числа, не превосходящие 20: n, т = 0,1,..., 20.
Общая выручка в центре равна 7n + 10m руб., а на вокзале равна 4(20 — n) + 9(20 — т) руб. По условию задачи эти величины равны:
7n+ 10m = 4(20 - n) + 9(20 - т)
11n + 19m = 260.Решим уравнение 11n + 19m = 260:
1. Найдем частное решение; им будет, например, n0= 15, т0 = 5.
2. Вычитая из равенства 11n + 19m = 260равенство 11 • 15 +19 • 5= 260, мы получим однородное уравнение: 11(n- 15) = 19(5 - m).
3. Общее решение этого однородного уравнения в целых числах имеет вид:
n-15=19k, 5-m=11k,
где k
Z. Соответственно, общее решение исходного уравнения в целых числах имеет вид:n = 15 + 19k, т = 5 – 11k,
где k
Z.Поскольку n, т ≥ 0, параметр k может быть равен только нулю. Поэтому найденное частное решение будет единственным решением исходного уравнения в неотрицательных целых числах: n= 15, т = 5. Так как это решение, кроме того, удовлетворяет условию n, m≤ 20, найденное значение m = 5 и будет ответом задачи.