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

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

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

Из этой таблицы ясно, что второе число из первой строки (то есть -4), которое соответствует х = -2, и третье число из второй строки (то есть 5), которое соответствует у = -1, и дают в сумме 1. Та­ким образом, уравнение 2х- b у = 1 имеет частное решение х₀ = -2, у₀ = -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)

Чтобы решить это уравнение, прежде всего, найдем какое-нибудь частное решение в целых (не обязательно неотрицательных) числах. Мы это уже сделали выше, когда разбирали пример, иллюстрирую­щий метод поиска частных решений линейных диофантовых урав­нений; в нашем случае в качестве такого частного решения можно взять, например, х₀ =- 2, y ₀ = -1, так что верно равенство

2• (-2)-5• (-1)=1. (7)

Вычитая из уравнения (в) равенство (7), получим:

2(х + 2) = 5( y + 1).

Общее решение этого уравнения в целых числах имеет вид:

х + 2 = 5 k , у + 1 = 2 k ,

где k — произвольное целое число. Чтобы числа х и у были неотри­цательными, параметр k должен быть натуральным числом. Теперь для числа n имеем:

n = 6х + 4 = 6(5 k - 2) + 4 = 30 k - 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 — т) руб. По условию задачи эти величины равны:

7 n + 10 m = 4(20 - n ) + 9(20 - т) 11 n + 19 m = 260.

Решим уравнение 11n + 19m = 260:

1. Найдем частное решение; им будет, например, n ₀ = 15, т₀ = 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. Соответственно, общее решение исходного уравнения в целых числах имеет вид: