Пособие ДИОФАНТОВЫ УРАВНЕНИЯ, ТИПЫ И СПОСОБЫ РЕШЕНИЯ

Левая часть последнего уравнения делится на m и правая часть: k – qy = mt, где t Z, t – новое неизвестное.

1. Повторение процедуры уменьшения коэффициентов. Новое уравнение отличается от старого только тем, что его коэффициенты по модулю меньше коэффициентов старого. За конечное число шагов добьемся того, что коэффициент при одном из новых неизвестных будет равен 1.

2. Возврат к исходным переменным.

Пример 2. Решить уравнение 79y – 23x = 1 в целых числах.

Решение. Проведем деление с остатком: 79 = 23*3 + 10 и перепишем исходное уравнение в виде 23x = 79y - 1 = (23*3 + 10)y – 1 = 69y + 10y - 1 23x - 69y = 10y - 1.

Левая часть уравнения делится нацело на 23, поэтому должна делиться на 23 и правая часть: 10y – 1 = 23t или 10y = 23t + 1; t Z – новое неизвестное.

Полученное новое уравнение по типу точно такое же, как исходное. Однако коэффициенты при неизвестных в нем уменьшились по модулю. Повторим процедуру уменьшения коэффициентов еще раз: 10y = 23t + 1 = (10*2 + 3)t + 1 10y – 20t = 3t +1 3t + 1 = 10u, u Z – новое неизвестное. Проведем процедуру уменьшения коэффициентов в последний раз: 3t + 1 = 10u = (3*3 + 1)u 3t - 9u = u - 1 u - 1 = 3v, v Z.

Осталось выразить x и y через v. Поскольку u = 3v + 1, то

1. 3t = 10u – 1 = 10(3v + 1) - 1 = 30v + 9 t = 10v + 3.

2. 10y = 23t +1 = 23(10v + 3) + 1 = 230v + 70 y = 23v + 7.

3. 23x = 79y – 1 = 79(23v + 7) - 1=79*23v + 552 x = 79v + 24.

Ответ: {(79v + 24, 23v + 7)}; v ∈ Z.

Пример 3. Решить уравнение = 1.

Решение. Преобразуем данное уравнение следующим образом:

= 1 = 0

Решим два уравнения в целых числах. Рассмотрим сначала первое уравнение:

= 5k = 6n – 1.

Перебирая все возможные остатки при делении n на 5, находим, что решением последнего уравнения являются n = 5l + 1; l . Значит, решением задачи будут служить x = , где

n , n 5l + 1; l . Теперь рассмотрим второе уравнение:

6n = 2 + k.

Ясно, что любое целое n является решением этого уравнения. Таким образом, ни одно значение x из серии x = не удовлетворяют условию задачи.

Ответ: ; n , n 5l + 1; l .

Решение диофантового уравнения с помощью алгоритма Евклида.

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

Пример 4. Решить в целых числах уравнение 2х + 7y = 4.

Решение. 2х + 7y = 4

2(x + 3y) + y = 4

Введем новую неизвестную z = x + 3y, тогда уравнение запишется так:

2z + y = 4.

Мы получили уравнение с коэффициентом один! Тогда z — любое число, y = 4 − 2z.

Осталось найти x: x = z − 3y = z − 3(4 − 2z) = 7z − 12.

Пусть z = 1. Тогда y = 2, x = -5. 2 * (-5) + 7 * 2 = 4

Пусть z = 5. Тогда y = -6, x = 23. 2 * 23 + 7 * (-6) = 4

Ответ: {(-5, 2); (23, -6)}.

В этом примере важно понять, как мы перешли от уравнения с коэффициентами 2 и 7 к уравнению с коэффициентами 2 и 1. В данном случае (и всегда!) новый коэффициент (в данном случае - единица) это остаток от деления исходных коэффициентов друг на друга (7 на 2).

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

Пример 5. Решить уравнение в целых числах 13х – 36у = 2.

36 / 13 = 2 (10 в остатке). Таким образом, исходное уравнение можно переписать следующим образом:

13x – 13 * 2y - 10y = 2.

13(x - 2y) - 10y = 2.

Введем новую переменную z = x - 2y.

Теперь мы получили уравнение: 13z - 10y = 2.

13 / 10 = 1 (3 в остатке). Исходное уравнение 13z - 10y = 2 можно переписать следующим образом:

10z - 10y + 3z = 2.

10(z - y) + 3z = 2.

Введем новую переменную m = z - y.

Теперь мы получили уравнение: 10m + 3z = 2.

10 / 3 = 3 (1 в остатке). Исходное уравнение 10m + 3z = 2 можно переписать следующим образом:

3*3m + 3z + m = 2.

3(3m + z) + m = 2.

Введем новую переменную t = 3m + z. Теперь мы получили уравнение:

3t + m = 2.

Мы получили уравнение с коэффициентом единица!

m = 2 – 3t, причем t может быть любым числом. Однако нам нужно найти x и y. Проведем замену переменных в обратном порядке. Помните, мы должны выразить x и y через t, которое может быть любым числом.

y = z - m; z = t - 3m, m = 2 – 3t ⇒ z = t - 3*(2 – 3t), y = t - 3*(2 – 3t) - (2 – 3t) = 13t - 8; y = 13t - 8

x = 2y + z ⇒ x = 2(13t – 8) + (t - 3*(2 - 3t))=36t - 22; x = 36t - 22

Пусть t = 1. Тогда y = 5, x = 24. 13*14 - 36*5 = 2

Пусть t = 5. Тогда y = 57, x = 158. 13*158 - 36*57 = 2

Ответ: {(24, 5); (158, 57)}.

Диофантовым уравнением второго порядка с двумя неизвестными x, y будем называть уравнение вида

Ax² + Bxy + Cy² + Dx + Ey = F,

где A, B, C, D, E, F, x, y и хотя бы одно из чисел A, B, C отлично от нуля.

Рассмотрим основные методы решения данных уравнений.

Разложение на множители. Этот метод состоит в том, что левая часть данного уравнения каким-либо образом раскладывается на множители (чаще всего путем нахождения дискриминанта), и задача сводится к перебору конечного числа вариантов.

Пример 1. Найти все пары целых чисел (x, y), каждая из которых удовлетворяет уравнению 2x² + 5 = 3y² + 5xy.

Решение. Преобразуем данное уравнение следующим образом:

2x² + 5 = 3y² + 5xy 3y² + 5xy - 2x² = 5 (3y - x)(y + 2x) = 5

или или .

Первые две системы не имеют решений в целых числах, третья и четвертая имеют решением пары (x, y) = (2, 1) и (x, y) = (-2, -1) соответственно.

Ответ: {(2,1); (-2, -1)}.

Пример 2. Найти все тройки чисел (x, y, z), удовлетворяющие системе уравнений

Решение. Рассмотрим второе уравнение системы как квадратное относительно x. Это уравнение будет иметь решение тогда и только тогда, когда его дискриминант больше либо равен нулю. Имеем:

D = 3(

В первом случае y = 2k, z = 2n; k, n , при этом x = . Первое уравнение системы в этом случае примет вид 4

уравнения всегда будет получаться целое число.

Во втором случае , при этом x = - . Первое уравнение системы в этом случае преобразуется к виду 2

Дискриминант этого уравнения (которое мы рассматриваем как квадратное относительно n) равен D = 49 + 16 – 8k = (4k - 1)² + 48 – m² ; m , иначе число n не может быть целым. Последнее уравнение принимает вид: (m + 4k - 1)(m - 4k + 1) = 48.

Разность первого и второго чисел, стоящих в скобках, равна 8k - 2, т.е. дает остаток 6 при делении на 8. В соответствии с этим получаем четыре варианта:

или или

или

В первых двух случаях получаем k = 3, n = - 5, откуда y = 7, z = - 9; в третьем и четвертом случаях находим, что k = n = 0 и y = z = 1.

Ответ: {(- , 7, - 9); (- , 1, 1)}.

Если в уравнении отсутствует член, содержащий или , т.е. A либо С равно нулю, но при этом В 0, то такое уравнение решается методом выделения целой части. Пусть, например, A = 0. Выразим x через у:

Bxy + Cy² + Dx + Ey = F x(By + D) = F – Ey - Cy², откуда x = . Далее делим многочлен F – Ey - Cy² на многочлен By + D с остатком, т.е. представляем данную дробь в виде

= Py + Q + ,

где P, Q, R – рациональные числа. Подобрав, при необходимости, целое число T и домножив на него обе части уравнения

x = Py + Q + ,

получим уравнение

Tx = P’y + Q’ + ,

где P’, Q’ и R’ уже являются целыми числами. Дальнейшее решение сводится к перебору всех делителей числа R’ (если R’ = 0, то уравнение становится линейным).

Пример 3. Решить в целых числах уравнение

Решение. Выразим в данном уравнении y через x:

y = = x + 1 - .

Из полученного равенства видно, что дробь должна быть целым числом. Это возможно, когда x – 3 принимает значения Разбирая четыре случая, находим все пары (x, y), удовлетворяющие данному уравнению: (x, y) = {(10, 10); (-4, -2); (4, -2); (2, 10)}.

Ответ: {(10, 10); (-4, -2); (4, -2); (2, 10)}.

Если диофантово уравнение второго порядка каким-либо образом (например, выделением полных квадратов) приводится к виду Ax² + Cy² = F, где A, C и F – целые, отличные от нуля, числа, то метод решения зависит от знаков коэффициентов при переменных. Если А и С имеют один и тот же знак, то используются следующие оценки (пусть A, C, F 0):

Ax² + Cy² = F x²

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

Пример 4. Найти целочисленные решения уравнения 14x⁴ – 5y⁴ – 3x²y² + 82y² – 125x² + 51 = 0.

Решение. Рассмотрим данное уравнение как квадратное относительно x². Имеем: 14x⁴ – 5y⁴ – 3x²y² + 82y² – 125x² + 51 = 0 14x⁴ – x² (3y² + 125) - 5y⁴ + 82y² + 51 = 0.

Дискриминант этого уравнения равен D = (3y² + 125)² + 56(5y⁴ - 82y² – 51) = 289y⁴ - 3842y² + 12769 = (17y² - 113)².

Корни уравнения равны

x² =

или

x² = .

Таким образом, левая часть исходного уравнения раскладывается на множители следующим образом:

(7x² – 5y² – 3)(2x² + y² – 17) = 0,

и задача сводится к решению двух уравнений в целых числах.

Докажем сначала, что уравнение 7x² = 5y² + 3 не имеет целочисленных решений. Для этого посмотрим, какие остатки могут давать при делении на 3 левая и правая части этого уравнения. Так как любой полный квадрат дает при делении на 3 остаток 0 или остаток 1, число 7x² также дает при делении на 3 остатки 0 и 1. Остатки от деления на 3 числа 5y² + 3 могут быть равны 0 или 2. Таким образом, равенство может иметь место только в том случае, когда x и y кратны 3. Но в этом случае числа x² и 5y² делятся без остатка на 9, поэтому равенство также не может иметь место (поскольку 3 не делится на 9).

Рассмотрим теперь уравнение 2x² + y² – 17. Из оценки x² 8,5 сразу следует, что x по модулю не превосходит 2. Перебирая все возможные варианты, находим, что решением задачи будут служить пары чисел (x, y) = {(2, 3); (-2, 3); (-2, -3); (2, -3)}.

Ответ: {(2, 3); (-2, 3); (-2, -3); (2, -3)}.

Наконец, рассмотрим уравнение вида Ax² + Dx + Ey = F, где A, D, E, F – целые числа и А, и Е отличны от нуля. Это уравнение решается перебором остатков при делении на Е числа F – Dx - Ax². Но в отличие уравнений первого порядка разрешимость данного уравнения может быть и при нескольких значениях остатка q. Кроме того, может оказаться, что такое уравнение и вовсе не имеет решений.

Пример 5. Решить в целых числах уравнение 3x² + 2x + 3y = 2.

Решение. Перепишем исходное уравнение в виде 3y = 2 – 2x - 3x².

Левая часть полученного уравнения делится на 3, значит, должна делиться на 3 и его правая часть. Рассмотрим три случая.

1. Если x = 3k; k , то 2 – 2x - 3x² = 2 – 6k – 27k² не делится на 3.

2. Если x = 3k + 1, то 2 – 2x - 3x² = 2 – 2(3k + 1) – 3(3k + 1)² = - 27k² - 24k – 3 делится на 3.

3. Если x = 3k + 2, то 2 – 2x - 3x² = 2 – 2(3k + 2) – 3(3k + 2)² = - 27k² - 42k – 14 не делится на 3.

Итак, x = 3k + 1, откуда y = - 9k² - 8k – 1, где k .

Ответ: {(3k + 1, - 9k² - 8k – 1)}; k .

Рассмотрим на примере метод выделения полного квадрата.

Пример 6. Найти целочисленные решения

Решение.

Значит, y = 0; ; .

Перебрав все варианты значений y, и найдя соответствующие значения x, запишем ответ.

Ответ: {(2, -1); (-2; 1); (8; 1); (-8; -1)}.

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

Пример 1. Решить в целых числах уравнение x² + 5y² + 34z² + 2xy – 10xz – 22yz = 0.

Решение. Преобразуем данное уравнение следующим образом:

x² + 5y² + 34z² + 2xy – 10xz – 22yz = 0

(x² + 2x(y - 5z) + y² – 10yz + 25z²) + 4y² - 12yz + 9z² = 0

(x + y – 5z)² + (2y – 3z)² = 0

n

Ответ: x = 7n, y = 3n, z = 2n; n

Пример 2. Найти все пары целых чисел (x, y), каждая из которых удовлетворяет уравнению (x² + y²)(x + y – 3) = 2xy.

Решение. Ясно, что пара (0, 0) является решением данного уравнения. Предположим теперь, что хотя бы одно из чисел x и y отлично от нуля. Имеем

(x² + y²)(x + y – 3) = 2xy x + y – 3 = при всех значениях x и y. Так как x + y – 3 – целое число, то возможны три варианта.

1. Если x + y – 3 = - 1, то x = - y, нет решений.

2. Если x + y – 3 = 0, то либо x = 0, y = 3, либо x = 3, y = 0.

3. Если x + y – 3 = 1, то x = y, следовательно, x = 2 и y = 2.

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

(x, y) = {(2, 2); (3, 0); (0, 3); (0, 0)}.

Ответ: {(2, 2); (3, 0); (0, 3); (0, 0)}.

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

Пример 1. Длина дороги, соединяющей пункты А и В, равна 2 км. По этой дороге курсируют два автобуса. Достигнув пункта А или пункта В, каждый из автобусов немедленно разворачивается и следует без остановок к другому пункту. Первый автобус движется со скоростью 51 км/час, а второй – 42 км/час. Сколько раз за 8 часов движения автобусы встретятся в пункте В, если известно, что первый стартует из пункта А, а второй – из пункта В?

Решение. Первый автобус проезжает путь между А и В за часа, второй – за часа. Если оба автобуса встретились в пункте В, то за одинаковое время первый проехал этот путь нечетное число раз, второй – четное число раз. Имеем:

* (2n + 1) = * 2k 8; n, k N

Из последнего уравнения видно, что k нечетно и кратно 7. Таких чисел в интервале от 1 до 84 шесть, это 7, 21, 35, 49, 63 и 77. Каждому такому k соответствует целое значение n. Таким образом, за 8 часов движения автобусы встретятся в пункте В шесть раз.

Ответ: 6 раз.

Пример 2. Мастер делает за 1 час целое число деталей, большее 5, а ученик – на 2 детали меньше. Один мастер выполняет заказ за целое число часов, а два ученика вместе – на 1 час быстрее. Из какого количества деталей состоит заказ?

Решение. Пусть х 5 деталей делает мастер за 1 час, тогда ученик за один час делает х – 2 детали. Пусть также мастер выполняет заказ за t часов, где t – целое число. Согласно условиям задачи имеем уравнение

xt = 2(x – 2)(t – 1) t = = 2 + .

Дробь должна быть целым числом. При х 5 это возможно, когда х = 6 или х = 8. В первом случае получаем, что t = 4, во втором – t = 3. В обоих случаях заказ состоит из xt = 24 деталей.

Ответ: Из 24 деталей.

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

Пример 1. В двух ящиках находится более 29 одинаковых деталей. Число деталей в первом ящике, уменьшенное на 2, более чем в три раза превышает число деталей во втором ящике. Утроенное число деталей в первом ящике превышает удвоенное число деталей во втором ящике, но менее чем на 60. Сколько деталей в каждом ящике?

Решение. Обозначим через x число деталей в первом ящике, а через y – число деталей во втором. Тогда, согласно условию, имеет место система неравенств

Перепишем эту систему в виде

Отсюда следует, что справедливы неравенства

Первое из них можно переписать в виде , а второе – в виде . Так как y – натуральное число, то y равен либо 6, либо 7. Если y равен 6, то система неравенств перепишется в виде

Ясно, что нет натуральных чисел x, удовлетворяющих ей. Значит, y = 7. Тогда исходная система перепишется в виде

Отсюда вытекает, что существует единственное натуральное число x = 24, ей удовлетворяющее. Следовательно, в первом ящике 24 детали, а во втором – 7 деталей.

Ответ: 24 детали и 7 деталей.

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

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

Решение. Пусть t = x – 1, тогда данная система примет следующий вид:

На координатной плоскости Oty полученная система определяет множество точек.

Из рисунка видно, что в полученном множестве содержатся только три точки с целочисленными координатами – это (t, y) = {(-1, 0); (1, 0); (1, 1)}. Таким образом, ответом к задаче будут служить пары чисел (x, y) = {(0, 0); (2, 0); (1, 1)}.

Ответ: {(0, 0); (2, 0); (1, 1)}.

Пример 2. Найти все пары целых чисел x, y, удовлетворяющих системе

Решение. Преобразуем данную систему следующим образом:

На координатной плоскости Oxy полученная система определяет множество точек.

Из рисунка видно, что этому множеству принадлежат только две точки с целочисленными координатами – это точки (3, -4) и (4, -5).

Ответ: {(3, -4); (4, -5)}.

Пример 1. Каким может быть наибольший общий делитель натуральных чисел m и n, если при увеличении числа m на 6 он увеличивается в 9 раз?

Решение. Пусть d – наибольший общий делитель чисел m и n, тогда 9d – наибольший общий делитель чисел m + 6 и n. Так как d – делитель m и m + 6, то d – делитель разности этих чисел, т.е. делитель числа 6. Следовательно, d = 1, d = 2, d = 3 или d = 6. Так как числа m + 6 и n делятся на 9, то числа m и n делятся на 3, следовательно, d делится на 3. Таким образом, d = 3 или d = 6. Осталось проверить, что оба случая имеют место. Если d = 3, то, например, m = 21, n = 27; если d = 6, то m = 48, n = 54.

Ответ: 3 или 6.

Пример 2. На клетчатой бумаге отмечен прямоугольник m * n клеток, причем числа m и n взаимно просты и m n. Диагональ этого прямоугольника не пересекает ровно 116 его клеток. Найти все возможные значения m и n при денных условиях.