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

где kZ.

Поскольку n , т ≥ 0, параметр k может быть равен только нулю. Поэтому найденное частное решение будет единственным решени­ем исходного уравнения в неотрицательных целых числах: n = 15, т = 5. Так как это решение, кроме того, удовлетворяет условию n, m≤ 20, найденное значение m = 5 и будет ответом задачи.

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

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

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

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

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

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

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

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

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

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

Поскольку число копеек не может быть больше, чем 99, справед­ливо двойное неравенство: 1 ≤ n , m ≤ 99 . Оно, в частности, влечет, что сдача не превышает первоначальную сумму в 100 рублей, которая была у Темы.

Хотя уравнение (8) является стандартным уравнением в целых числах вида ах + by = с, найти его частное решение (чтобы свести дело к однородному уравнению) простым подбором весьма непро­сто. На этом примере мы продемонстрируем общий метод поиска частного решения (алгоритм Евклида), который автоматически приводит к успеху.

Рассмотрим коэффициенты при неизвестных (а = 97 и b = 299) и разделим больший коэффициент на меньший. В результате получим неполное частное 3 и остаток 8. Иначе говоря, справедливо равен­ство 299 = 3• 97 + 8, или, что то же самое, 8 = 299 -3• 97.

Теперь заменим больший коэффициент (то есть 299) на остаток (то есть 8) и проделаем с парой 97, 8 ту же процедуру: разделим 97 на 8. В результате мы получим неполное частное 12 и остаток 1. Иначе говоря, справедливо равенство 97 = 12• 8 + 1, или, что то же самое, 1 = 97 — 12• 8. Заменим в этом равенстве число 8 выражением 299 – 3 • 97, найденным в предыдущем абзаце:

1 = 97-12• (299 – 3 • 97) = 37 • 97 – 12 • 299.

Итак, мы представили число 1 (это наибольший общий делитель чисел 97 и 299) в виде линейной комбинации чисел 97 и 299. Ум­ножая последнее равенство на 140, мы получим искомое частное решение уравнения (8): т₀ = 37 • 140 = 5180, п₀ = 12 • 140 = 1680.

Это частное решение обычным образом приводит к следующему общему решению уравнения (8) в целых числах:

Условия 1 < n , т ≤99 однозначно определяют значение пара­метра k : k = -17, что приводит к следующим значениям основных неизвестных n и m=31, m=97.