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

            Линейным уравнением с двумя переменными называется уравнение вида ax+by=c, где x и у – переменные, а, b и с – некоторые числа.

Пара чисел (a, b) называется решением уравнения с двумя переменными, если при замене x на а и y на b получаем истинное равенство.

Каждому уравнению с двумя переменными соответствует множество его решений, т. е. множество, состоящее из всех пар чисел (a, b), при подстановке которых в уравнение получается истинное равенство.

Два уравнения с двумя переменными, имеющие одни и те же решения называются равносильными.

Например, равносильны уравнения х+2у=5 и 3х+6у=15 – любая пара чисел, удовлетворяющая одному из этих уравнений, удовлетворяет и второму.

Уравнения с двумя переменными обладают такими же свойствами, как и уравнения с одной переменной:

1) если в уравнении перенести слагаемое из одной части в другую, изменив его знак, то получится уравнение, равносильное данному;

2) если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному.

Существует несколько способов решения диофантовых уравнений:

1.  Метод перебора вариантов

2.  Использование алгоритма Евклида

3.  С использованием цепной дроби

4.  Метод рассеивания (измельчения)

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

      Андрей работает летом в кафе. За каждый час ему платят 10 р. И высчитывают 2 р. за каждую разбитую тарелку. На прошедшей неделе он заработал 180 р. Определите, сколько часов он работал и сколько разбил тарелок, если известно, что он работает не более 3 ч в день.

Решение.

Пусть x часов он всего работал в неделю, тогда 10х р. ему заплатили, но он разбил у тарелок, и с него вычли 2у р.

Имеем уравнение 10х – 2у =180, причем x меньше или равен 21.

Получим: 5х-у=90, 5х=90+у, х=18+у:5.

Так как x целое число, то у должно нацело делится на 5, чтобы в правой части получилось целое число. Возможны четыре случая

1.  у=0, х=18, т. е. решением является пара – (18, 0);

2.  у=5, х=19, (19, 5);

3.  у=10, х=20, (20, 10);

4.  у=15, х=21, (21, 15).

Ответ содержит четыре возможных варианта.

Решим ещё одну задачу:

        Из двухрублевых и пятирублевых монет составлена сумма в 23 рубля. Сколько среди этих монет двухрублевых?

Решение.

Пусть x – количество двухрублевых монет, у – количество пятирублевых монет.

Составим и решим уравнение: 2х+5у=23;

2х=23–5у; 

x =(23 – 5у):2; 

x=(22+1 – 5у):2,

Почленно поделим 22 на 2 и (1 – 5у) на 2, получим: 

x = 11 + (1 – 5у):2.

Так как x и y натуральные числа по условию задачи, то левая часть уравнения есть натуральное число, значит, и правая часть должна быть натуральным числом. К тому же, чтобы получить в правой части число натуральное, нужно чтобы выражение (1 – 5у) нацело делилось на 2. Осуществим перебор вариантов.

1.  y=1, х=9, то есть двухрублевых монет может быть 9;

2.  у=2, при этом выражение (1 – 5у) не делится нацело на 2;

3.  у=3, х=4, то есть двухрублевых монет может быть 4;

4.  при у больше или равном 4 значение x не является числом натуральным.

Таким образом, ответ в задаче следующий: среди монет 9 или 4 двухрублевых.

          Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей

Решение.

Сказочнице потребуется x + у ночей, где x и у – натуральные корни уравнения 3х+5у=1001

x = (1001 – 5у):3; так как x – натуральное число, то и в правой части равенства также должно быть натуральное число, а значит выражение (1001 – 5у) должно нацело делиться на 3.

Осуществим перебор вариантов.

у=1, 1001 – 5у=1001-5= 996, 996 делится на 3, следовательно, х=332; решение (332;1);

у=2, 1001– 10=991, 991 не делится на 3;

у=3, 1001 – 15 = 986; 986 не делится на3;

у =4, 1001 – 20 = 981, 981 делится на 3, следовательно, x = 327, решение (327;4) и т. д.

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

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

Разберем метод решения с использованием алгоритма Евклида.

Задача 4. В магазине продаётся шоколад двух видов: молочный и горький. Весь шоколад хранится в коробках. Молочного шоколада на складе имеется 7 коробок, а горького 4. Известно, что горького шоколада было на одну плитку больше. Сколько плиток шоколада находятся в коробках каждого вида?

Решение. Пусть х – количество плиток молочного шоколада в одной коробке,

у – количество плиток горького шоколада в одной коробке,

тогда по условию этой задачи можно составить уравнение:

4у-7х=1.

Решим это уравнение, используя алгоритм Евклида.

4у-7х=1;

      Выразим 7=4∙1+3, тогда  3=7-4∙1.

      Выразим 4=3∙1+1, тогда  1= 4-3∙1= 4-(7-4∙1)= 4-7+4∙1= 4∙2-7∙1=1.

      Итак, получается х=1; у=2.

А это значит, что молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки.

Если материал оказался сложным для вас, просмотрите его ещё раз с помощью видеоурока.

Попробуйте теперь решить практические задания  👍