Глава IV. Диофантовы уравнения

Покупка свитера

Диофантовы уравнения

Задача

Вы должны уплатить за купленный в магазине свитер 19 руб. У вас одни лишь трехрублевки, у кассира - только пятирублевки. Можете ли вы при наличии таких денег расплатиться с кассиром и как именно?

Вопрос задачи сводится к тому, чтобы узнать, сколько должны вы дать кассиру трехрублевок, чтобы, получив сдачу пятирублевками, уплатить 19 рублей. Неизвестных в задаче два - число (х) трехрублевок и число (у) пятирублевок. Но можно составить только одно уравнение:

3x - 5y = 19.

Хотя одно уравнение с двумя неизвестными имеет бесчисленное множество решений, но отнюдь еще не очевидно, что среди них найдется хоть одно с целыми положительными хну (вспомним, что это - числа кредитных билетов). Вот почему алгебра разработала метод решения подобных "неопределенных" уравне-" ний. Заслуга введения их в алгебру принадлежит первому европейскому представителю этой науки, знаменитому математику древности Диофанту, отчего такие уравнения часто называют "диофантовыми".

Решение

На приведенном примере покажем, как следует решать подобные уравнения.

Надо найти значения х и у в уравнении

3x - 5y = 19, 

зная при этом, что х и y - числа целые и положительные.

Уединим то неизвестное, коэффициент которого меньше, т. е. член 3x; получим:

3х = 19 + 5у,

откуда

x = (19 + 5y)/3 = 6 + y + (1 + 2y)/3.

Так как х, 6 и у - числа целые, то равенство может быть верно лишь при условии, что (1 + 2y)/3 есть также целое число. Обозначим его буквой t. Тогда

x = 6 + y + t,

где

t = (1 + 2y)/3,

и, значит,

3t = 1 + 2y, 2y = 3t - 1.

Так как у и t - числа целые, то и (t - 1)/2 должно быть некоторым целым числом t₁. Следовательно,

y = t + t1,

причем

t1 = (t - 1)/2,

откуда

2t1 = t - 1 и t = 2t1 + 1.

Значение t = 2t₁ + l подставляем в предыдущие равенства:

y = t + t1 = (2t1 + 1) + t1 = 3t1 + 1, 
x = 6 + y + t = 6 + (3t1 + 1) + (2t1 + 1) = 8 + 5t1.

Итак, для х и у мы нашли выражения^*

x = 8 + 5t1 
y = 1 + 3t1

^* Строго говоря, мы доказали только то, что всякое целочисленное решение уравнения 3х - 5y = 19 имеет вид x = 8 + 5t₁, y = 1 + 3t₁, где t₁ - некоторое целое число. Обратное (т. е. то, что при любом целом t₁ мы получаем некоторое целочисленное решение данного нам уравнения) доказано не было. Однако в этом легко убедиться, проводя рассуждения в обратном порядке или подставив найденные значения х и у в первоначальное уравнение.

Числа х и у, мы знаем, - не только целые, но и положительные, т. е. большие чем 0. Следовательно,

8 + 5t1 > 0, 
1 + 3t1 > 0.

Из этих неравенств находим:

 5t1 > -8 и t1 > -8/5, 
 3t1 > -1 и t1 > -1/3. 

Этим величина t₁ ограничивается; она больше чем -1/3 (и, значит, подавно больше чем -8/5). Но так как t₁ - число целое, то заключаем, что для него возможны лишь следующие значения:

t1 = 0, 1, 2, 3, 4, ...

Соответствующие значения для х и у таковы:

 x = 8 + 5t1 = 8, 13, 18, 23..... 
 у = 1 + 3t1 = 1, 4, 7, 10, ... 

Теперь мы установили, как может быть произведена уплата:

 вы либо платите 8 трехрублевок, получая одну пятирублевку сдачи: 

 8 × 3 - 5 = 19, 

 либо платите 13 трехрублевок, получая сдачи 4 пятирублевки: 

 13 × 3 - 4 × 5 = 19 

 и т. д. 

Теоретически задача имеет бесчисленный ряд решений, практически же число решений ограничено, так как ни у покупателя, ни у кассира нет бесчисленного множества кредитных билетов. Если, например, у каждого всего по 10 билетов, то расплата может быть произведена только одним способом: выдачей 8 трехрублевок и получениемеда Как видим, неопределенные уравнения практически могут давать₁вполне определенные пары решений.

Возвращаясь к нашей задаче, предлагаем читателю в качестве упражнения самостоятельно решить ее вариант, а именно рассмотреть случай, когда у покупателя только пятирублевки, а у кассира только трехрублевки. В результате получится такой ряд решений:

 x = 5, 8, 11, ..., 
 у = 2, 7, 12, ... 

Действительно,

  5 × 5 -  2 × 3 = 19, 
  8 × 5 -  7 × 3 = 19, 
 11 × 5 - 12 × 3 = 19,

Мы могли бы получить эти результаты также и из готового уже решения основной задачи, воспользовавшись простым алгебраическим приемом. Так как давать пятирублевки и получать трехрублевки все равно, что "получать отрицательные пятирублевки" и "давать отрицательные трехрублевки", то новый вариант задачи решается тем же уравнением, которое мы составили для основной задачи:

3х - 5y = 19,

но при условии, что х и у - числа отрицательные. Поэтому из равенств

 x = 8 + 5t1, y = 1 + 3t1

мы, зная, что x< 0 и у < 0, выводим:

8 + 5t1 < 0, 1 + 3t1 < 0

и, следовательно,

t1 < -8/5

Принимая t₁ = -2, -3, -4 и т. д., получаем из предыдущих формул следующие значения для х и у:

t1 = -2, -3, -4,
x =  -2,  -7,  -12,
У = - 5,  -8,  -11.

Первая пара решений, x = -2, y = -5, означает, что покупатель "платит минус 2 трехрублевки" и "получает минус 5 пятирублевок", т. е. в переводе на обычный язык - платит 5 пятирублевок и получает сдачи 2 трехрублевки. Подобным же образом истолковываем и прочие решения.