Решение уравнений в целых числах

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

« Решение задач ─ практическое искусство, подобное плаванию, катанию на лыжах или игре на фортепиано; научиться ему можно, только подражая хорошим образцам и постоянно практикуясь».

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

Решение уравнений в целых числах.

Линейное уравнение с одним неизвестным ax = b, где a, b – целые числа, a ≠0, можно привести к виду, где a >0. Оно имеет единственное целочисленное решение

, если a ─ делитель b, и не имеет целочисленных решений в противном случае.

Пример. Найти целочисленное решение уравнения x3 + 3x2 – x – 6 = 0.

Решение: преобразуем уравнение к виду х(x2 + 3x -1) = 6; это равенство показывает, что если х – целочисленное решение, то 6: x. Следовательно, достаточно проверить значения x = 1, -1, 2, 2, 3, -3, 6, -6. Подставляя, данные значения х, убеждаемся, что подходит только (- 2).

ОТВЕТ: x = ─ 2.

Задача. Квадратные керамические плитки были приготовлены, чтобы выложить ими комнату размерами (2n + 1) на (n + 2) плиток. Можно ли этими плитками выложить стенку высотой (n + 4) плиток и какой длины?

Решение: если х – длина ряда плитки, то общее количество плиток равно

(n + 4)х = (2n + 1)(n + 2), так что при условии, что дробь является целым числом. Преобразуем, числитель дроби:

(2n + 1)(n + 2)= 2n2 +5n +2 = 2n(n +4) – 3n +2 =

2n(n + 4) –3( n + 4 ) + 14, так что

Таким образом, х может быть целым в двух случаях: при n = 3, тогда х = 6 – 3 14:7 = 5 и при n =10, тогда х = 20 – 3 + 14:14 = 18.

Ответ: при n =3 размеры плитки 7х7 или при n= 10 размеры плитки 14х18.

Простейшим примером диофантова уравнения служит линейное уравнение вида аx + by = c в целых числах (естественно, с целыми коэффициентами a,b,c). Оно может быть решено разными способами.

Пусть теперь а, b, и с ─ целые числа и а ≥ b > 0. Рассмотрим уравнение ax + by=c, (1) где неизвестные x и у ─ целые числа. Обозначим d = НОД (a, b) ─ наибольший общий делитель a и b. Если х0 и у0 –целочисленное решение уравнения (1), то из равенства ax0 + by0=c следует, что c также должно делиться на d.

Если c не делится на наибольший общий делитель (a, b), то уравнение (1) не имеет решений в целых числах.

Задача. Покупатель, имеющий только монеты по 5 рублей и 2 рубля, выбрал в палатке продукты на 43 рубля. Продавец, не желая принять металлические деньги, сослался на то, что 43 рубля нельзя уплатить по 2 и 5 рублей. Прав ли он? Если нет, какое наименьшее количество монет потребуется?

Решение: пусть потребуется х монет по 2 рубля и у монет по 5 рублей, тогда получим уравнение:

2x+5у=43.

Если решение существует, то 43 – 5y должно делиться на 2. Подходит y = 1, тогда и для любого нечетного у,

1 ≤ y≤ 7, найдем значение х. Итак, решениями будут (19;1), (14;3), (9;5), (4;7).

Ответ: можно заплатить четырьмя способами, наименьшее количество монет 11.

Необходимое и достаточное условие разрешимости уравнения ах + bу = с в целых числах.

Пусть a, b, c – ненулевые целые числа. Если число c делится на наибольший общий делитель пары чисел a и b, то уравнение ax + by = c имеет целочисленное решение. Это условие выполнено, если а и b взаимно простые числа.

Если с не делится на наибольший общий делитель (a, b), то уравнение (1) не имеет решений в целых числах.

Доказательство: пусть НОД(a,b)=d и число c не делится на d, тогда если уравнение (1) имеет целочисленное решение x = x0, y = y0, то верно числовое равенство ax0 + by0 = c, в котором левая часть делится на d, а правая нет. Полученное противоречие доказывает, что указанное уравнение в целых числах не может иметь решений.

Пример. Найти все натуральные числа x и y такие, что

4x2 – y2 = 28, т. е. найти все решения уравнения в натуральных числах.

Решение: разложим левую часть уравнения на множители:

4x2 ─ y2 = (2x – у)(2x + y).

Так как x и y ─ натуральные числа, то 2x +y также натуральное число, делящее 28. Если 2x+ y нечетно, то 2x –y = (2x+y)- 2y также не делится на 2, и их произведение не может быть четным. Следовательно, числа 2x ─y и 2x+y четные, причем

2x─y<2x+y. В результате этих рассуждений получаем систему уравнений которая имеет единственное решение:

Ответ: x = 4, y = 6.

Пример. Найти х2 + у2, если х и у ─ натуральные числа, удовлетворяющие уравнению

3х2 – 2ху – у2 – 23 = 0.

Решение: левую часть уравнения разложим на множители. Представим слагаемое ( - 2ху ) как сумму двух величин: (- 3ху) и ху: ( 3х2 – 3ху ) + (ху – у2) = 23, 3х(х – у) + у(х – у) = 23,

(х – у)(3х + у) = 23. Так как 23 ─ простое число, то выполняются равенства:

следовательно, х = 6, у = 5; х2 + у2 = 61.

Ответ: 61.

Задача. На складе имеются гвозди, упакованные в ящики по 16 кг, 17 кг, 40 кг. Может ли кладовщик отпустить 140 кг гвоздей, не вскрывая ни одного ящика?

Решение: задача сводится к решению уравнения

16 x + 17 y + 40z = 140 в целых неотрицательных числах. Число y не может быть равным 0, так как иначе уравнение

16x + 40z = 140 в целых числах имело бы решение, что противоречило бы утверждению задачи. Далее, число x также не может быть равным 0, так как иначе было бы выполнено равенство 17y = 140 – 40z = 10 (14 – 4z) и неотрицательное число 14 – 4z делилось бы на 17 при целом неотрицательном значении z , что невозможно. Число z также не может быть равным 0 , так как иначе из равенства 17y = 140 – 16x = 4 (35 – 4x) следовало бы, что число 35 – 4x кратно 17 при x > 0, что невозможно.

Таким образом, число x , y , z должны быть положительными, а число x1 = x – 1, y1 = y – 1 , z1 = z – 1 ─ целыми неотрицательными, удовлетворяющими уравнению

16 x1 + 17 y1 + 40 z1 = 67.

Аналогичные рассуждения показывают, что у1 ≠ 0 и x1 ≠ 0 , т. е. числа x2 = x1 – 1 и y2 = y1 ─1 должны удовлетворять уравнению

16 x2 + 17 y2 + 40 z1 = 34, в целых неотрицательных числах, которое имеет единственное решение x2 = 0 , y2 = 2 , z1 = 0. Таким образом, возвращаясь к исходным неизвестным, мы получаем единственное решение первоначального уравнения x = 2, y = 4, z = 1.

Ответ: 140 кг гвоздей можно отпустить только с помощью 2 ящиков по 16 кг , 4 ящика по 17 кг и 1 ящик по 40 кг.

Пример. Выясним, имеет ли уравнение x2 – xy – 2y2 =12 решения в целых числах.

Решение: покажем, что не существует таких чисел x и y, для которых x2 – xy -2y2 = 12. Разложим на множители левую часть уравнения: х2 – xy – 2y2 = x2 – xy –y2 –y2 = (x2 – y2) –

( xy+y2)=(x – y)(x + y) – y (x + y)= (x + y)(x – 2y).

Пусть x – 2y =(x+y) ─ 3y , тогда 12 = (x+y)((х + y) – 3y). Так как 12 делится на 3, то по свойству хотя бы один из множителей должен делиться на 3.

Если x + y делится на 3 , то ( x + y) ─ 3y также делится на 3 и произведение( x+ y)(x – 2y) делится на 9. Аналогично из делимости на 3 множителя x – 2y = (x+y) – 3y также вытекает делимость на 3 числа x + y.

Следовательно, (x+y)(x – 2y) делится на 9 для любых чисел x и y, поэтому x2 – xy – 2y2 ≠12.

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

ПРАВИЛО. Если c делится на наибольший общий делитель НОД(a,b) коэффициентов уравнения (1), то следует упростить это уравнение, разделив обе его части на НОД(a, b).

Предположим, что u и v – два натуральных числа, u > v и для некоторых чисел x1, y1, x2, y2 выполняются равенства аx1 + by1=u, (2) аx2 + by2 = v, (3) т. е. пары чисел (x1, y1) и (x2, y2) есть решения уравнения (1) при c = u и c = v. Разделим u на v с остатком: u= v · q + r, 0 ≤ r

Если обе части равенства (3) умножить на q и вычесть из (2), получится а( x1 ─ qx2) + b(y1 –qy2) = r, т. е. числа x1 – qx2 и y1 – qy2 образуют решение уравнения ax + bx = r, (10)

Зная решения уравнений ax + bx = v и ax + by = r, точно так же можно получить решение уравнения (1), где вместо v стоит остаток от деления v на r. Этот процесс можно продолжать и дальше. Мы будем находить решения уравнений (1), где справа будут стоять все меньшие и меньшие натуральные числа.

Покажем, как свести решение уравнения аx + by = c в целых числах с ненулевыми целыми коэффициентами a, b, c к решению уравнения a1x + b1y = c1 в целых числах, коэффициенты a1, b1, c1 которого являются натуральными числами, причем числа a1 и b1 взаимно просты.

Решение: если в правой части уравнения ax + by = c стоит отрицательное число, то умножим обе части уравнения на (- 1) и получим уравнение с положительным числом в правой части. Если коэффициент a отрицателен, то заменим неизвестную x неизвестной x1 = ─ x и получим уравнение

─ax1 + by = с с положительным коэффициентом ─a. Аналогично, если b < 0 , то замена y1 = ─ y приводит к уравнению аx – by1 = c с положительным коэффициентом ─b. Поэтому каждый из коэффициентов a и b соответствующей заменой неизвестной можно сделать положительным. Если числа a и b не являются взаимно простыми, то НОД (a,b) = d чисел a и b должен быть делителем числа c. Поэтому имеем a = a1d, b = b1d , c = c1d и, поделив обе части уравнения на d , получим уравнение a1 x + b1 y = c1 с взаимно простыми коэффициентами a1 и b1.

Задача. На станцию привезли 420 т угля в вагонах вместимостью по 15 т, по 20 т, и по 25 т. Сколько каких вагонов было использовано, если известно, что всего было 27 вагонов?

Решение: пусть было использовано x , y и z вагонов вместимостью по 15 т, по 20 т и по 25 т соответственно. Тогда имеем

15x + 20y + 25z = 420, x + y + z = 27, т. е. числа y и z должны удовлетворять уравнению

15(27 ─ y ─ z) + 20y + 25z = 420 в натуральных числах. Преобразовывая это уравнение, получаем y + 2z = 3, т. е. y = z = 1 и x = 25.

Ответ: было использовано 25 вагонов по 15 т , 1 вагон в 20 т и

1 вагон в 25 т.

Задача. Пусть пара чисел x = x0 , y = y0 удовлетворяет уравнению аx + by = c в целых числах с взаимно простыми коэффициентами a и b.

Докажем, что формулы х = x0 + bk, y = y0 – ak с целым параметром k задают все решения этого уравнения.

Доказательство: предположим, что пары чисел (х,у) и (х0,у0) удовлетворяют уравнению ах + by = c в целых числах с взаимно простыми коэффициентами а и b, то ах + by = c = ax0 +by0, а(х – х0) + b(y – y0) = 0. Так как число является целым, а числа b и а не имеют общих делителей, то число k = также является целым. Поэтому х – х0 = bk и y – y0 = ak, откуда получаем равенства x = x0 + bk, y = y0 – ak.

Задача. Для перевозки зерна имеются мешки, в которые входит либо 60 кг, либо 80 кг зерна. Сколько надо заготовить тех и других мешков для загрузки 1 т зерна таким образом, чтобы все мешки были полными? Какое наименьшее количество мешков при этом может понадобиться?

Решение: для неизвестных x и y , обозначающих количество мешков по

60 кг и по 80 кг , имеем уравнение

60x + 80y = 1000 , 3x + 4y = 50 в целых неотрицательных числах. Одно целочисленное решение этого уравнения нетрудно угадать, воспользовавшись равенством

─ 3 × 50 + 4 × 50 = 50.

Учитывая формулы общего решения, получаем все целочисленные решения этого уравнения: x = ─ 50 + 4k, y = 50 – 3k.

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

4k – 50 ≥ 0, 50 – 3k ≥ 0, из которых выведем оценки

12 < < 17.

Таким образом, последовательно придавая значения k = 13, 14, 15, 16, найдем все неотрицательные решения: x1 = 2 , y1 = 11 ; x2 = 6 , y2 = 8 ; x3 = 10 , y3 = 5 ; x4 = 14 , y4 = 2.

Наименьшее количество мешков x + y = 13 достигается при первом из найденных решений.

Ответ: 2 мешка и 11 мешков.

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