Неопределенные (диофантовы) уравнения

Неопределенные уравнения – уравнения, содержащие более одного неизвестного. Под одним решением неопределенного уравнения понимается совокупность значения неизвестных, которая обращает данное уравнение в верное равенство.

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

Определение 1. Диофантовым уравнением 1-й степени с n неизвестными называется уравнение вида , (1)

Где все коэффициенты и неизвестные – целые числа и хотя бы одно .

Определение 2. Решением диофантова уравнения (1) называется комплекс целых чисел , удовлетворяющий этому уравнению.

Теорема 1. При взаимно простых коэффициентах и при b=1 диофантово уравнение (1) имеет решение в целых числах.

Пусть . Диофантово уравнение (1) имеет решение тогда и только тогда, когда . Число решений такого уравнения равно либо нулю, либо бесконечности.

Для решения в целых числах уравнения (2), где - целые числа, отличные от нуля, приведем ряд теоретических положений, которые позволят установить правило решения. Эти положения основаны также на уже известных фактах теории делимости.

Теорема 2. Если , то существуют такие целые числа x и y, что имеет место равенство (3).

Это равенство называется линейной комбинацией или линейным представлением наибольшего общего делителя двух чисел через сами эти числа. Доказательство теоремы основано на использовании равенств алгоритма Евклида для нахождения наибольшего общего делителя двух чисел (наибольший общий делитель данных чисел выражается через неполные частные и остатки, начиная с последнего равенства в алгоритме Евклида).

Теорема 3. Если в уравнении (4) , то уравнение (4) имеет, по крайней мере, одно целое решение.

Справедливость этой теоремы следует из теоремы 2. Таким образом, чтобы найти одно целое решение уравнения (4), если , достаточно представить число 1 в виде линейной комбинации чисел a и b.

Теорема 4. Если в уравнении (5) и c не делится на d, то уравнение целых решений не имеет.

Для доказательства теоремы достаточно предположить противное.

Теорема 5. Если в уравнении (6) и , то оно равносильно уравнению (6’), в котором .

При доказательстве теоремы следует показать, что произвольное целое решение первого уравнения является также решением второго уравнения и обратно.

Теорема 6. Если пара целых чисел , удовлетворяет уравнению (6), где - целые числа, отличные от нуля и , то

, , (7)

где t – произвольное целое число, является общим решением этого уравнения в целых числах.

Доказательство. По условию теоремы (8) Вычитая почленно из уравнения (6) равенство (8), получим уравнение

, (9)

равносильное уравнению (6). Покажем, что формулы (7) задают множество всех целых решений уравнения (9), а, следовательно, и уравнения (6). Очевидно, что каждая пара целых чисел, заданная формулами (7), удовлетворяет уравнению (9). Наоборот, если пара целых чисел , удовлетворяет уравнению (9), то есть ,то . Отсюда, поскольку , вытекает, что , то есть , аналогично, доказывается, что , где t – некоторое целое число. Следовательно, каждая пара целых чисел , удовлетворяющая уравнению (9), задается формулами (7). Что и требовалось доказать.

Таким образом, чтобы решить уравнение (6) в целых числах, надо найти какое-нибудь частное решение этого уравнения или частное решение уравнения (4) и умножит это решение на c, получим частное решение уравнения (6).

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

Теорема 7. Общее решение в целых числах уравнения (6),где - целые числа, отличные от нуля и , можно представить в виде

, , (10)

где t – произвольное целое число, а и - числитель и знаменатель предпоследней подходящей дроби разложения числа в цепную дробь.

Доказательство. Пусть = - разложение числа в цепную дробь, а (s=1,2,…,n) – подходящие дроби этого разложения. Тогда = . По условию дробь - несократимая и дробь также несократимая, поэтому , . По свойству подходящих дробей , то есть . Умножив обе части последнего равенства на , получим равенство . Это равенство означает, что пара чисел и является целым решением уравнения (6).

Примеры. 1. Найти целые решения уравнения .

Решение. Упрощаем данное уравнение, приводя его к виду . Решаем уравнение . 256=37·6+34, 37=34·1+3, 34=3·11+1. 1=34 – 3·11= 256 – 37∙6 – 11(37 – 256 + 37∙6) = 256∙12 – 37∙83 =

= 37∙(-83) – 256∙(-12), то есть . Общий вид всех целых решений данного уравнения:

.

2.Транспортной организации, имеющей грузовые автомашины грузоподъемностью 3,5 и 4,5 т, предложено перевезти 53т груза. Определить, сколько грузовых автомашин того и другого типа должен выделить диспетчер для перевозки указанного груза одним рейсом при условии полного использования грузоподъемности всех выделенных автомашин.

Решение. Пусть x,y – число выделенных машин грузоподъемностью соответственно 3,5 и 4.5т. для получения ответа нужно решить уравнение то есть в целых числах с учетом того, что . Разложив дробь в цепную дробь, будем иметь . Подсчитаем подходящие дроби: . Предпоследней подходящей дробью является . Следовательно, по формулам общим решением в целых числах заданного уравнения является: , где t – любое целое число. Теперь из всех решений выберем неотрицательные: . Учитывая, что t – целое число, получим: или , то есть или .

Поиск по сайту: