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

На примере следующей задачи мы продемонстрируем, как с по­мощью частного решения уравне­ния ах + 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 и будет ответом задачи.

Ответ: 5 стаканов.

Практически дословное повторение рассуждений, проведенных при решении задач 3 и 4, позволяет доказать, что общее решение уравнения ах + bу = с представляет собой сумму частного решения (х0 ; у0) этого уравнения и общего решения соответствующего одно­родного уравнения ах + by = 0. Отсюда, в свою очередь, вытекает следующая важная общая теорема.

Теорема 5. Если числа а и b— взаимно простые, то уравнение ах + by= с имеет бесконечно много решений в целых числах, которые находятся во взаимно однозначном соответствии с мно­жеством целых чисел Z(то есть могут быть занумерованы целыми числами) и описываются формулой: хn= х0 + bn,yn = y0- an, где nZ — «номер» решения, а х0, у0 — частное решение (которое существует в силу теоремы 3).

Важно подчеркнуть, что в рассмотренном методе решения урав­нений вида ах + by = с частное решение мы ищем только для того, чтобы свести дело к однородному уравнению. Иногда, как, напри­мер, в следующей задаче, этого можно добиться и проще.

Задача 5. Найти все наборы натуральных чисел х, у, z, удовлетворяющие следующим условиям:

Решение. Исключим г из второго уравнения системы: г = у + 7. Тогда первое уравнение примет вид:

11х - 6у = y + 7 11x – 7y = 7

Если перенести свободный член 7 из правой части и сгруппиро­вать члены 7у и 7, то мы получим уравнение

11x-7(y + 1) = 0,

которое является однородным относительно хи«ву+ 1. В силу теоремы 1 его общее решение в целых числах имеет вид: х = 7n, у + 1 = 11n, где n — произвольное целое число. Соответственно, (x; у) = (7n; 11n -1), n Z. Чтобы x и у были натуральными, долж­ны быть выполнены условия 7n > 0 и 11n -1 > 0, что равносильно тому, что n — натуральное число. Если у — натуральное число, то z = y + 7 автоматически будет натуральным.

Итак, общее решение системы из двух первых уравнений в на­туральных числах имеет вид: (х; у; z) = (7n; 11n - 1; 11n + 6), где n — произвольное натуральное число.

Дополнительное условие, что х ≤ 20, означает, что параметр n < 2. Итак, для n есть всего два возможных значения: 1 и 2. Им соответ­ствует два набора неизвестных (х; у; z): (7; 10; 17) и (14; 21; 28).

Ответ: (7; 10; 17), (14; 21; 28)

Теперь решим более трудные задачи.

Задача 6. Тёма сделал несколько мелких покупок в супермарке­те, имея при себе 100 рублей. Давая сдачу с этой суммы, кассир ошиблась, перепутав местами цифры, и выплатила рублями то, что должна была вернуть копейками, и, наоборот, копейками то, что полагалось вернуть рублями. Купив в аптеке набор пипеток за 1 руб. 40 коп., Тема обнаружил ошибку кассира и, пересчитав деньги, нашел, что оставшаяся у него сумма втрое превышает ту, которую ему должны были вернуть в супермаркете. Какова стоимость всех покупок Темы?

Решение. Пусть правильная сдача равна n руб. и т коп., то есть (100n + т) коп. Реально кассирша выплатила сумму т руб. и n коп., то есть (100m + n) коп. После покупки пипеток у Темы останется (100т + n —140) коп. По условию эта сумма в три раза больше, чем 100n + т. Это дает следующее уравнение для неизвестных n и т:

100т + n - 140 - 3 • (100n + т) 97m – 299m - 140. (8)

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