УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ МЕТОДЫ РЕШЕНИЯ ДИОФАНТОВЫХ УРАВНЕНИЙ ПРИ ПОДГОТОВКЕ ШКОЛЬНИКОВ К ОЛИМПИАДАМ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«Брестский государственный университет имени А.С. Пушкина»

Е.П. Гринько, А.Г. Головач

УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ

МЕТОДЫ РЕШЕНИЯ

ДИОФАНТОВЫХ УРАВНЕНИЙ

ПРИ ПОДГОТОВКЕ ШКОЛЬНИКОВ

К ОЛИМПИАДАМ

                                                                                            Брест                                                                                           1

БрГУ имени А.С. Пушкина

2013

Авторы:

Гринько Е.П. – заведующий кафедрой методики преподавания математики и информатики, кандидат педагогических наук, доцент Головач А.Г. – магистрант БрГу имени А.С. Пушкина

Рецензенты:

Савчук В.Ф. – директор Брестского филиала ГУО «Институт непрерывного образования», кандидат физико-математических наук, доцент

Сендер Н.Н. – заведующий кафедрой высшей математики, кандидат физико-математических наук, доцент Редактор:

Сохор И.Л. – преподаватель кафедры информатики и прикладной математики БрГУ имени А.С. Пушкина

2

СОДЕРЖАНИЕ

Введение                         . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                            5

1.   История диофантовых уравнений . . . . . . . . . . . . . . . . . .    7

2.   Методы решения диофантовых уравнений . . . . . . . . . . . . .        12

2.1       Метод полного перебора всех возможных значений переменных,

                                   входящих в уравнение . . . . . . . . . . . . . . . . . . . . . . .                    13

2.2       Метод разложения на множители . . . . . . . . . . . . . . . . . 17

2.3       Метод, основанный на выражении одной переменной через дру-

гую и выделении целой части дроби . . . . . . . . . . . . . . . 34

2.4       Метод, основанный на выделении полного квадрата . . . . . . .         43

2.5       Метод решения уравнения с двумя переменными как квадрат-

ного относительно одной из переменных . . . . . . . . . . . . . 47

2.6       Метод, основанный на оценке выражений, входящих в уравнение 51

2.7       Метод бесконечного (непрерывного) спуска . . . . . . . . . . . .   59

2.8       Решение диофантовых уравнений с помощью алгоритма Евклида 64

2.9       Решение диофантовых уравнений с помощью цепных дробей . .  74

2.10  Решение диофантовых уравнений с помощью сравнений . . . .       91

2.11  Уравнение Пелля . . . . . . . . . . . . . . . . . . . . . . . . . .  96

2.12  Уравнение Каталана . . . . . . . . . . . . . . . . . . . . . . . . 108    3

2.13  Уравнение Маркова         . . . . . . . . . . . . . . . . . . . . . . . . 109

2.                 14.Методы решения диофантовых уравнений второй степени и

выше . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

2.15 Некоторые приложения теории диофантовых уравнений . . . 147 3 Практикум по решению уравнений в целых числах . . . . . . . . 155 4 Задачи для самостоятельного решения . . . . . . . . . . . . . . . 173 5. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . 175

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

4

Введение

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

Целью ЭУМП «Методы решения диофантовых уравнений при подготовке школьников к олимпиадам» является формирование у студентов знаний о типах диофантовых уравнений и основных методах решения в аспекте их реализации при подготовке школьников к олимпиадам разного уровня.

Задачи ЭУМП:

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

2)     систематизировать знания о типах и методах решения диофантовых уравнений, полученные студентами в различных математических курсах («Теории чисел», «Методы решения школьных олимпиадных задач», «Методы решения алгебраических олимпиадных задач» и др.);

3)способствовать формированию у студентов потребности и навыков 5 использования представленного материала в будущей профессиональной деятельности (при подготовке школьников к олимпиадам).

Структура ЭУМП:

1.     Теоретический раздел, содержащий необходимые теоретические сведения.

2.     Практический раздел, содержащий задачный материал с решениями.

3.     Раздел контроля знаний, содержащий вопросы для самопроверки,задачи для самостоятельного решения.

4.     Вспомогательный раздел, содержащий рекомендуемую литературу.

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

6

1 История диофантовых уравнений

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

Диофантовы уравнения связаны с именем древнегреческого математика Диофанта Александрийского. О подробностях жизни Диофанта Александрийского практически ничего не известно. С одной стороны, Диофант цитирует Гипсикла (II век до нашей эры); с другой стороны, о Диофанте пишет Теон Александрийский (около 350 года нашей эры) — откуда можно сделать вывод, что его жизнь протекала в границах этого периода. Возможное уточнение времени жизни Диофанта основано на том, что его «Арифметика» посвящена «достопочтеннейшему Дионисию». Полагают, что этот Дионисий — не кто иной, как епископ Дионисий Александрийский, живший в середине III века нашей эры. В

Палатинской антологии содержится эпиграмма-задача, в которой гово- 7 рится:

Прах Диофанта гробница покоит; дивись ей и камень Мудрым искусством его скажет усопшего век.

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

И половину шестой встретил с пушком на щеках.

Только минула седьмая, с подругой он обручился.

С нею, пять лет, проведя, сына дождался мудрец;

Только полжизни отцовской возлюбленный сын его прожил.

Отнят он был у отца ранней могилой своей.

Дважды два года родитель оплакивал тяжкое горе, Тут и увидел предел жизни печальной своей.

Решение этой задачи подсказывает, что Диофант прожил 84 года. До нас дошли 7 книг Диофанта из, возможно, 13, которые были объединены в «Арифметику» — сборник задач (их всего 189), каждая из которых снабжена решением и необходимым пояснением. В книге II решаются задачи, связанные с неопределенными уравнениями и системами уравнений с 2, 3, 4, 5, 6 неизвестными степени не выше второй. Диофант использовал для решения уравнений различные приемы. Методы, разработанные в книге II, Диофант применял и к более трудным задачам книги III, связанным с системами трех, четырех и большего числа урав- 8 нений степени не выше второй. В книге IV встречаются определенные и неопределенные уравнения третьей и более высоких степеней.

Индусские математики примерно с пятого века также рассматривали неопределенные уравнения первой степени. Некоторые такие уравнения с двумя и тремя неизвестными появились в связи с проблемами, возникшими в астрономии, например, при рассмотрении вопросов, связанных с определением периодического повторения небесных явлений. Первое общее решение уравнения ax+by = c, где a,b,c — целые числа, встречается у индийского мудреца Брахмагупты (около 625 года). В 1624 году вышла книга французского математика Баше де Мезирьяка «Problemes plaisans et delectables que se font par les nombres». Баше де Мезирьяк для решения уравнения ax + by = c применил процесс, сводящийся к последовательному вычислению неполных частных и рассмотрению подходящих дробей. После Баше де Мезирьяка в XVII и XVIII веках различные правила для решения неопределенного уравнения первой степени с двумя неизвестными давали Роль, Эйлер, Саундерсон и другие математики.

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

Одним из ярких представителей класса диофантовых уравнений второй степени является уравнение Пелля (его еще называют неопределён-

ным уравнением Ферма), то есть уравнение: x² + ay² = 1, где a — це-

9 лое положительное число, не являющееся полным квадратом. Первые упоминания об уравнении Пелля, были найдены в работах математиков Древней Греции и Древней Индии. Общий способ решения уравнения – так называемый «циклический метод» — присутствует в работах индий-

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

В 1630 г. французский математик Пьер Ферма (1601 — 1665) сформулировал гипотезу, которую называют великой (или большой) теоремой Ферма: «Уравнение xⁿ + yⁿ = zⁿ для натурального n ≥ 3 не имеет решений в натуральных числах». Ферма не доказал свою теорему в общем случае, но известна его запись на полях «Арифметики» Диофанта: «...невозможно куб записать в виде суммы двух кубов, или четную степень в виде суммы таких же степеней, или вообще любое число, которое является степенью большей, чем вторая, нельзя записать в виде суммы двух таких же степеней. У меня есть поистине удивительное доказательство этого утверждения, но поля эти слишком узки, чтобы его уместить». Позднее в бумагах Ферма было найдено доказательство его теоремы для

n = 4. С тех пор более 300 лет математики пытались доказать великую

10 теорему Ферма. В 1770 г. Л.Эйлер доказал теорему Ферма для n = 3; в 1825 г. Лежандр (1752 — 1833) и Дирихле (1805 — 1859) – для n = 5. Доказательство великой теоремы Ферма в общем случае не удавалось долгие годы. И только в 1995 г. Эндрю Уайлс доказал эту теорему.

На протяжении веков математики надеялись отыскать общий способ решения любого диофантова уравнения. Однако в 1970 г. ленинградский математик Ю.В. Матиясевич доказал, что такого общего способа быть не может.

11

2 Методы решения диофантовых уравнений

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

Рассмотрим более подробно каждый из названных выше методов.

12

2.1 Метод полного перебора всех возможных значений переменных, входящих в уравнение

Пример 1. Найти множество всех пар натуральных чисел, которые являются решениями уравнения:

49x + 51y = 602.

Решение. Выразим из уравнения переменную x через , так как x и y – натуральные числа, то,

51y ≤ 553, 1 ≤ 1043/51. Полный перебор вариантов показывает, что натуральными решениями уравнения являются x = 5, y = 7.

Ответ: (5;7).

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

x(x − 1)(x − 2) · ... · 2 · 1 = y² − 12.

Решение. При x > 5 левая часть исходного уравнения содержит множитель 5 · 2, то есть, оканчивается на ноль. Правая часть уравнения не может оканчиваться на ноль, что вытекает из таблицы 1:

13

Таблица 1.

y заканчивается на	y2 заканчивается на	y2 − 12 заканчивается на
0	0	8
1	1	9
2	4	2
3	9	7
4	6	4
5	5	3
6	6	4
7	9	7
8	4	2
9	1	9

Значит, при x ≥ 5 исходное уравнение решений не имеет.

Оставшиеся случаи проверяются перебором:

При x = 4: 24 = y² − 12, y = 6.

При x = 3: 6 = y² − 12, решений нет.

При x = 2: 2 = y² − 12, решений нет.

           При x = 1: 1 = y² − 12, решений нет.                                                                                        14

Ответ: (4;6).

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

Решение.

1)     Заметим, что правая часть уравнения делится на 3 при любом целом y.

2)     Исследуем какие остатки может иметь при делении на три левая часть этого уравнения.

По теореме о делении с остатком целое число либо делится на 3, либо при делении на три в остатке дает 1 или 2.

Если x = 3k, то правая часть уравнения на 3 не делится.

Если x = 3k + 1, то x² + 1 = (3k + 1)² + 1 = 3m + 2, следовательно, опять левая часть на 3 не делится.

Если x = 3k + 2, то x² + 1 = (3k + 2)² + 1 = 3m + 2, следовательно, и в этом случае левая часть уравнения на три не делится.

Таким образом, мы получили, что ни при каких целых левая часть уравнения на 3 не делится, притом, что левая часть уравнения делится на три при любых значениях переменной y. Следовательно, уравнение в целых числах решений не имеет.

Ответ: решений нет.

               Пример 4. Решить в целых числах x³ − 3y³ − 9z³ = 0.                                                    15

Решение.

1)    Очевидно, что решением уравнения будет тройка чисел (0;0;0).

2)    Выясним, имеет ли уравнение другие решения. Для этого преоб-

разуем уравнение к виду

x³ = 3y³ + 9z³.

Так как правая часть полученного уравнения делится на 3, то и левая обязана делится на 3, следовательно, так как 3 – число простое, делится на 3, то есть x = 3k, подставим это выражение в уравнение x³ = 3y³+9z³: 27k³ = 3y³ + 9z³, откуда

9k³ = y³ + 3z³,

следовательно, y³ делится на 3 и y = 3m. Подставим полученное выражение в уравнение 9k³ = y³ + 3z³: 9k³ = 27m³ + 3z³, откуда

3k³ = 9m³ + z³.

В свою очередь, из этого уравнения следует, что z³ делится на 3, и z = 3n. Подставив это выражение в 3k³ = 9m³ + z³, получим, что k³ должно делиться на 3.

Итак, оказалось, что числа, удовлетворяющие первоначальному уравнению, кратны трём, и сколько раз мы не делили бы их на 3, опять должны получаться числа, кратные трём. Единственное целое число, 16 удовлетворяющее этому условию, будет нуль, то есть решение данного уравнения (0; 0; 0) является единственным.

Ответ. (0,0,0).

2.2 Метод разложения на множители

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

y³ − x³ = 91.

Решение. Используя формулы сокращенного умножения, разложим правую часть уравнения на множители

(y − x)(y² + xy + x²) = 91.

1.   Выпишем все делители числа 91: ±1; ±7; ±13; ±91.

2.   Проведем исследование. Заметим, что для любых целых x и y число y² + xy + x² ≥ y² − 2|y| · |x| + x² = (|y| − |x|)² ≥ 0,

следовательно, оба сомножителя в левой части уравнения должны быть положительными. Тогда уравнение (y−x)(y²+xy+x²) = 91 равносильно совокупности систем уравнений:

                                                                                                                          y − x = 91,                                                         ¹⁷

= 91;= 1;

                                         = 13;        .

Решив системы, получим: первая система имеет решения (5;6), (−6;−5); третья (−3;4), (−4;3); вторая и четвертая решений в целых числах не имеют.

Ответ: (5;6); (−6;−5); (−3;4); (−4;3).

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

x² − 3xy + 2y² = 3.

Решение. Разложим левую часть уравнения x² − 3xy + 2y² = 3 на множители: x² − 3xy + 2y² = (x − y)(x − 2y).

Имеем: (x − y)(x − 2y) = 3. Поскольку число 3 можно представить в виде произведения целых чисел с учетом порядка четырьмя способами: 3 = 1 · 3 = 3 · 1 = (−1) · (−3) = (−3) · (−1), то получаем совокупность четырех систем для нахождения значений переменных:

,

= 3;

,

= 1;

                                                                                                                       ,                                                                               18

3;

,

целочисленными решениями которых являются соответственно пары (−1;−2), (5;2), (1;2), (−5;−2).

Ответ: (−1;−2), (5;2), (1;2), (−5;−2).

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

x + y = xy.

Решение. Проведем цепочку равносильных преобразований:

x + y = xy ⇔ x + y − xy = 0 ⇔ x(1 − y) + y = 0 ⇔

⇔ x(1 − y) + (y − 1) + 1 = 0 ⇔ (x − 1)(y − 1) = −1.

Поскольку −1 можно представить в виде произведения двух целых чисел с учетом порядка двумя способами (−1 = 1 · (−1) = (−1) · 1), получаем две системы:

,

Решением первой системы является пара (2;2), а второй (0;0).

Ответ: (2;2), (0;0). ¹⁹ Пример 8. Доказать, что уравнение

(x − y)³ + (y − z)³ + (z − x)³ = 30

не имеет решений в целых числах.

Решение.

1)     Разложим левую часть уравнения на множители и обе части уравнения разделим на 3, в результате получим уравнение:

(x − y)(y − z)(z − x) = 10.

2)     Делителями 10 являются числа ±1,±2,±5,±10. Заметим также, что сумма сомножителей левой части уравнения (x−y)(y−z)(z−x) = 10 равна 0. Нетрудно проверить, что сумма любых трех чисел из множества делителей числа 10, дающих в произведении 10, не будет равняться 0.

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

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

x² − 4x − y² + 6 = 0.

Решение. Выделим в левой части уравнения x² − 4x − y² + 6 = 0

квадраты относительно x и относительно y:                                                                               ²⁰

(x² − 4x + 4) − 4 − (y² − 2y + 1) + 1 + 6 = 0 ⇔ (x − 2)² − (y − 1)² = −3; (x − y − 1)(x − 2 + y − 1) = −3 ⇔ (x − y − 1)(x + y − 3) = −3.

Поскольку −3 можно представить в виде произведения двух чисел с учетом порядка четырьмя способами

(−3 = 3 · (−1) = (−3) · 1 = (−1) · 3 = 1 · (−3)),

то уравнение x²−4x−y²+6 = 0 на множестве целых чисел равносильно совокупности четырех систем:

1;

3,

3 = 1;

1,

3 = 3;

,

решениями которых являются соответственно пары (3;−1), (1;3), (3;3), (1;−1).

Ответ: (3;−1), (1;3), (3;3), (1;−1).

21

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

                                                                              1      1        1

+ + = 1. x y xy

Решение. Исходное уравнение равносильно системе:

,

,

Поскольку −2 можно представить в виде произведения двух целых чисел с учетом порядка четырьмя способами, получаем совокупность четырех систем для нахождения x и y:

1,

1 = 2;

2,

1 = 1;

22

2;

,

решениями которых являются соответственно пары (0;−1); (−1;0); (2;3), (3;2). Учитывая ограничение xy 6= 0, получим ответ.

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

Пример 11. Найти все пары простых чисел x и y, удовлетворяющих уравнению: x² − 2y² = 1.

Решение. Переписав исходное уравнение в виде x² = 1 + 2y², заключаем, что x – нечетное число. Теперь, приводя исходное уравнение к виду

(x − 1)(x + 1) = 2y²,

заметим, что числа x − 1 и x + 1 четные, а из (x − 1)(x + 1) = 2y² следует, что y четное. Значит, y = 2 (это единственное простое четное число). Тогда находим x = 3.

Ответ: (3;2).

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

x² − y² = 7.

Решение.

                                                                         (x − y)(x + y) = 7 · 1.                                                                          23

Так как x + y > x − y, то

Ответ: (4;3).

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

x⁴(x² − x⁴ + 2y) = y² + 1999.

Решение. x⁶ − (x⁴ − y)² = 1999,

(x³ − (x⁴ + y))(x³ + (x⁴ − y)) = 1999,

.

Ответ: (10,9001), (10,10999), (−10,10999), (−10,9001). Пример 14. Решить в натуральных числах уравнение:

1 + x + x² + x³ = 2^y.

Решение. Преобразуем (1 + x)(1 + x²) = 2^y,

,

24

1-й случай. Пусть m = 0. Тогда 2^y + 2 − 1 = 2, 2^y = 1, y = 0, x = 0, нет натуральных решений.

2-й случай. Пусть m > 0, 2^y−m−1 + 2^m − 2^2m−1 = 1.

 ,

Ответ: (1;2).

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

x³ − 8y³ = 19.

Решение. Разложим на множители: (x − 2y)(x² + 2xy + 4y²) = 19 · 1,

,

25

2y² + y − 3 = 0,

 – посторонний корень, y₂ = 1.

Ответ: (3;1).

Пример 16. (Заключительный тур Минской городской математической олимпиады школьников, 9 класс) Найдите все пары целых чисел x и y, для которых x3 + y3 = 830.

Решение. Числа x и y должны иметь одну и ту же четность. Покажем, что уравнение x³ + y³ = 8ⁿ не может иметь нечетных решений на при каком натуральном n. Предположим противное, то есть, что числа x и y – нечетные. Рассматриваемое уравнение представим в виде

(x + y)(x² − xy + y²) = 8ⁿ.

Так как x²−xy+y² – нечетное число (при нечетных и ) и 8ⁿ не имеет других нечетных делителей, кроме ±1, то x² − xy + y² = ±1. Выделяя полные квадраты, получим, что .

Отсюда, . Поэтому, либо y = ±1 и тогда x = 0, либо y = 0 и тогда x = ±1. Однако, в обоих случаях равенство x³ + y³ = 8ⁿ не является верным ни при каких натуральных n.

Итак, оба x и y – четные. Пусть, x = 2x₁, y = 2y₁. Тогда, x³ +y³ = 8³⁰

равносильно. Согласно доказанному выше числа x₁ и y₁ –

26 также четные. Поэтому, полагая пусть, x₁ = 2x₂, y₁ = 2y₂, аналогично получим , и т.д. В результате получим, что x = 2³⁰x₃₀, y = 2³⁰y₃₀, где. Последнее уравнение имеет два решения:

(1,0) и (0,1). В итоге, имеем (2³⁰,0) и (0,2³⁰).

Пример 17. (Проект Shevkin.ru) Решите уравнение относительно x, y и z в натуральных числах:

(x − y + z)(x² + y² + z²) = 2005.

Решение. Представим правую часть уравнения 2005 через произведение простых делителей 2005 = 5 · 401. 401 можно записать как сумму трёх натуральных квадратов 256,144 и единицы, что подходит по первому множителю. Для полноты решения необходимо рассмотреть и другие варианты представления правой части как 2005 = 1 · 2005, которые не дают новых решений.

Ответ: (16;12;1).

Пример 18. (Петербургские математические олимпиады) Решите уравнение с двумя неизвестными x и y в целых числах:

10x² + 11xy + 3y² = 7.

Решение. Левую часть уравнения можно представить в виде произведения двух сомножителей (5x+3y) и (2x+y), которые могут принимать только целые значения −7, −1, 1, 7, которые приводят к следующим па-

рам целых корней (−4;9), (14;−21), (4;−9), (−14;21).                                                           27

Ответ: (−4;9), (14;−21), (4;−9), (−14;21).

Пример 19. (LXII Белорусская математическая олимпиада школьников, заключительный этап, 8 класс, г. Гомель, 2012) Найти все пары (n,m) целых чисел n и m, для которых выполняется равенство

n² + n = m² + 2m − 9.

Решение. Умножив обе части данного равенства на 4, получим равносильное равенство

4n² + 4n = 4m² + 8m − 36 ⇔ 4n² + 4n + 1 = 4m² + 8m + 2 − 39 ⇔

⇔ (2n + 1)² = (2m + 2)² − 39 ⇔ (2m + 2)² − (2n + 1)² = 39 ⇔ ⇔ (2m + 2 − 2n − 1)(2m + 2 + 2n + 1) = 39 ⇔ ⇔ (2m − 2n + 1)(2m − 2n + 3) = 39.

Так как 39 = 1 · 39 = 39 · 1 = 3 · 13 = 13 · 3 = (−1) · (−39) =

= (−39)·(−1) = (−3)·(−13) = (−13)·(−3) – единственное разложение числа 39 на целые множители, то достаточно рассмотреть случаи.

1.  откуда, складывая и вычитая уравнения систе-

,,

мы, получими в результате

28

2.

,

3.

.

4.

.

5.

6.

7.

,

8.

29

Ответ: (−10,−11); (−10,9); (−3,−5); (−3,3); (2,−5); (2,3); (9,9); (9,−11).

Пример 20. (LXII Белорусская математическая олимпиада школьников, заключительный этап, 9 класс, г. Гомель, 2012) Найти все пары

(n,m) целых чисел n и m, для которых выполняется равенство

n² + n + 1 = (m² + m − 3)(m² − m + 5).

Решение. Из условия получаем

n² + n + 1 = (m² + m − 3)(m² − m + 5) = m⁴ + m² + 8m − 15.

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

n² + n − (m⁴ + m² + 8m − 16) = 0

как квадратное относительно n. Для того чтобы существовали натуральные решения этого уравнения необходимо, чтобы его дискриминант

D = 4m⁴ + 4m² + 32m − 63

является квадратом некоторого целого числа. Однако, при все натуральных m

D = 4m⁴ + 4m² + 32m − 63 = (2m² + 2)² − 4(m − 1)² − 59 < (2m² + 2)²                                         30

и при всех натуральных m > 2

D = 4m⁴ + 4m² + 32m − 63 = (2m² + 1)² + 32(m − 2) > (2m² + 1)².

Следовательно, натуральные решения уравнения

n² + n − (m⁴ + m² + 8m − 16) = 0

могут существовать лишь при натуральных m = 1 или m = 2.

Если m = 1, то n² + n + 6 = 0, откуда n = −2 или n = −3.

Если m = 2, то n² + n − 20 = 0, откуда n = −5 или n = 4.

Таким образом, единственной парой натуральных чисел, удовлетворяющей условию, является пара (4,2).

Ответ: (4,2).

Пример 21. (LXII Белорусская математическая олимпиада школьников, заключительный этап, 10 класс, г. Гомель, 2012) Найти все тройки (x,n,p) натуральных x и n и простых p, для которых

2x³ + x² + 10x + 5 = 2 · pⁿ.

Решение.

2x³ + x² + 10x + 5 = (x² + 5)(2x + 1),

поэтому исходное равенство перепишется в виде

                                                                     (x² + 5)(2x + 1) = 2 · pⁿ.                                                                      31

Поскольку (2x + 1) – нечетное число при любых натуральных x, то p 6= 2 и 2x + 1 = p^k, x² + 5 = 2 · p^n−k. При этом, так как очевидно, что x² + 5 > x + 2 при всех x ∈ N и p ≥ 3, то n − k ≥ k. Следовательно, число (x² + 5)^...(2x + 1). Поэтому число  целое, но тогда и число  целое. Так как 2(x² + 5) = x(2x + 1) + (10 − x), то число

так же должно быть целым, а вместе с ним должно быть целым число

. Однако, 2(10−x) = −(2x+1)+21, следовательно, должно быть целым число . Последнее возможно лишь при 2x + 1 = 1, 3, 7, 21, т.е. при натуральных x = 1, x = 3, x = 10.

При x = 1 имеем (x² + 5)(2x + 1) = 6 · 3 = 18 = 2 · 3², откуда p = 3, n = 2.

При x = 3 имеем (x² +5)(2x+1) = 14·7 = 2·7², откуда p = 7, n = 2.

При x = 10 имеем (x² +5)(2x+1) = 105·21 = 5·7² ·3², т.е. не имеет вид 2·ⁿ ни при каких натуральных n и простых p.

Ответ: (1;2;3), (3;2;7).

Пример 22. (LXII Белорусская математическая олимпиада школьников, заключительный этап, 11 класс, г. Гомель, 2012) Найти все тройки (x,n,p) натуральных x и n и простых p, для которых

x³ + 3x + 14 = 2 · pⁿ.

Решение.

                                                       x³ + 3x + 14 = (x + 2)(x² − 2x + 7),                                                            32

поэтому исходное равенство перепишется в виде

(x + 2)(x² − 2x + 7) = 2 · pⁿ.

Очевидно, что x² − 2x + 7 > x + 2 при всех x ∈ N. Поэтому и в случае x + 2 = 2 · p^k, x² − 2x + 7 = p^n−k, и в случае x + 2 = 2 · p^k, x² − 2x + 7 = p^n−k, имеем n − k ≥ k ≥ 0. Это означает, что в общих случаях число 2(x² − 2x + 7)^...(x + 2). Следовательно, число целое, но так как 2(x² − 2x + 7) = 2x(x + 2) − 8(x + 2) + 30, то должно быть целым число . Последнее возможно лишь если (x+2) является делителем 30. Однако из (x + 2)(x² − 2x + 7) = 2 · pⁿ следует, что число x + 2 имеет не более двух простых делителей, причем один из них в этом случае равен 2. Поэтому при натуральном x число x + 2 может принимать лишь значения 3, 5, 6, 10, т.е. x может принимать значения 1, 3, 4, 8.

При x = 1 имеем (x + 2)(x² − 2x + 7) = 3 · 6 = 18 = 2 · 3², откуда p = 3, n = 2.

При x = 3 имеем (x + 2)(x² − 2x + 7) = 5 · 10 = 2 · 5², откуда p = 5, n = 2.

При x = 4 имеем (x + 2)(x² − 2x + 7) = 6 · 15 = 18 = 2 · 3² · 5, т.е. не имеет вид 2 · pⁿ ни при каких натуральных n и простых p.

При x = 8 имеем (x + 2)(x² − 2x + 7) = 10v55 = 18 = 2 · 5² · 11, т.е.

не имеет вид 2 · pⁿ ни при каких натуральных n и простых p.

         Ответ: (1;2;3), (3;2;5).                                                                                                                ³³

2.3 Метод, основанный на выражении одной переменной через другую и выделении целой части дроби

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

x² + xy − y − 2 = 0.

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

y(x − 1) = 2 − x²,

Так как x, y – целые числа, то дробь должна быть целым числом. Это возможно, если x − 1 = ±1.

1)

1;2;

x = 2,

2)

                                                                                                           .                                                                                        34

Ответ: (0;−2); (2;−2).

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

2x² − 2xy + 9x + y = 2.

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

Выразим y через . Так как уравнение 2x − 1 = 0 не имеет решений в целых числах, то это преобразование не привело к потере корней. Преобразуем полученную дробь

.

Поскольку y и x – целые числа, то дробь  должна быть целым числом. Следовательно, имеем:

+ 5 + 3;

,

3;

35

+ 5 + 1;

,

Решая полученные системы, получаем окончательный ответ.

Ответ: (1;9); (0;2); (2;8); (−1;3).

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

3x + 2y = 7.

Решение. Переписав уравнение в виде 2(x + y) = 7 − x, заключаем, что 7 − x кратно 2, т. е. 7 − x = 2k, k ∈ Z. Значит, x = 7 − 2k, и из исходного уравнения находим y = 3k−7. Следовательно, все пары вида (7 − 2k;3k − 7), k ∈ Z являются решениями исходного уравнения.

Ответ: (7 − 2k;3k − 7), k ∈ Z.

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

y² = 5x² + 6.

Решение. Пусть x = 3k, k ∈ Z. Тогда исходное уравнение принимает вид y² = 45k² + 6.

Рассмотрим случай y = 3n, n ∈ Z. Уравнение y² = 45k² + 6 решений

36 не имеет, так как левая часть уравнения будет делиться на 9, а правая – нет. Если y = 3n ± 1, n ∈ Z, то уравнение y² = 45k² + 6 также решений не имеет по той же причине, так как уравнение примет вид 9n² = 45k² + 5 ± 6n.

Пусть теперь x = 3k ± 1, k ∈ Z, тогда исходное уравнение преобразуется к виду y² = 45k² ± 30k + 11.

Правая часть уравнения y² = 45k² ± 30k + 11 есть число, которое при делении на 3 дает в остатке 2. При y = 3n, n ∈ Z, уравнение y² = 45k²±30k+11 решений не имеет; так как слева выражение делится на 3, а справа – нет.

При y = 3n±1, n ∈ Z, уравнение y² = 45k² ±30k+11 также решений не имеет, так как при делении на 3 выражения слева получаем остаток 1, а выражения справа – остаток 2.

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

Пример 27. Найти натуральные и , такие, что 117x−79y = 17, для которых x + y имеет наименьшее значение.

Решение. Имеем 117 = 79 · 1 + 38. Перепишем данное уравнение в виде 79(x−y)+38x = 17. Обозначим x−y = u, тогда уравнение примет вид

79u + 38x = 17.

37 Проведем цепочку преобразований.

Так как 79 = 2·38+3, то 38(2u+x)+3u = 17. Обозначим 2u+x = v, тогда получим 38v + 3u = 17. Так как 38 = 3 · 12 + 2, то 3(12v + u) + + 2v = 17, 12v + u = w, тогда 3w + 2v = 17, так как 3 = 2 · 1 + 1, то 2(w + v) + w = 17, w + v = t, 2t + w = 17. Последнее уравнение имеет очевидное решение w = 17−2t, t ∈ Z. Теперь пойдем в обратном направлении:

v = t − w = t − 17 + 2t = 3t − 17,

u = w − 12v = 17 − 22t − 12(3t¯17) = 17 − 2t − 36t + 204 = 221 − 38t, x = v − 2u = 3t − 17 − 2(221 − 38t) = 3t − 17 − 442 + 76t = 79t − 459,

y = x − u = 79t − 459 − 221 + 38t = 117t − 680.

Из условия x,y ∈ N найдем t ≥ 6. Очевидно, что x + y имеет наименьшее значение при t = 6.

Ответ: (15;22).

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

Решение. Выразим x через y, получим: , n ∈ Z. Тогда . Следовательно, все пары вида

(3n − 4;2n), n ∈ Z являются решениями исходного уравнения.

Ответ: (3n − 4;2n), n ∈ Z.

Пример 29. Решить в целых числах уравнение 4x − 6y = 18.

Решение. Разделив обе части уравнения на наибольший общий делитель чисел 4, 6, 18, то есть на число 2, имеем 2x − 3y = 9. Из этого уравнения выразим неизвестное с меньшим (по модулю) коэффициен- 38 том:. Далее из полученной дроби выделим целую часть:

.

Считая x и y целыми, заключаем, что последнее равенство выполняется тогда, когда дробь  является целым числом. Пусть , где n – целое. Тогда, выразив неизвестное y, получим y = 2n−1. Подставим теперь найденное выражение y в равенство  и получим x = 8 + 2(2n − 1) + n = 5n + 6. Итак, найдены все решения данного уравнения: x = 5n + 6, y = 2n − 1,где n ∈ Z.

Рассмотрим уравнение в целых числах с тремя неизвестными ax+by+ +cz = d, где a, b и c – целые числа, отличные от нуля, a d – произвольное целое.

При решении таких уравнений следует различать два случая:

1)                       среди пар чисел (a;b), (b;c), (a;c) имеется пара взаимно простых чисел;

2)                       среди указанных пар нет взаимно простых чисел.

Пример 30. Решить уравнение 2x + 4y + 5z = 1.

Решение. Здесь из трех пар (2;4), (2;5), (4;5) имеются две пары взаимно простых чисел. Выберем вторую пару, перепишем уравнение в виде 2x + 5z = 1 − 4y и будем решать его как уравнение с целыми неизвестными и z, считая y целым параметром. Выразим неизвестное , а затем выделим целую часть:

39

.

Так как x, y и z – целые числа, то последнее равенство будет выполнено только, когда дробь является целым числом. Отсюда находим z = 1 − 2n. Подставляя это выражение в равенство, получим

.

Тогда все решения данного уравнения можно записать в виде

x = 5n − 2k − 2,y = k,z = 1 − 2n,n,k ∈ Z.

Ответ: (5n − 2k − 2,k,1 − 2n),n,k ∈ Z.

Пример 31. Решить уравнение в целых числах 6x − 10y + 15z = 1.

Решение. В данном случае среди пар (6;10), (6;15) и (10;15) нет взаимно простых чисел. Поступим следующим образом. Будем рассматривать неизвестное z как целое фиксированное число и перепишем уравнение в виде

.

Так как x, y и z – целые числа, то дробь  является целым числом и, значит, ее можно представить в виде , где n – целое. Тогда получим z = 1−2n, n ∈ Z. Подставив z = 1−2n в равенство 3x−5y =

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

3x − 5y = −7(1 − 2n) + n = 15n − 7

с двумя неизвестными значениями x, y с целочисленным параметром n.

Решим это уравнение так, как описано в примере 30. В результате найдем все решения исходного уравнения: x = 5n + 5k − 4, y = 3k − 1, z = 1 − 2n, где n,k ∈ Z.

Ответ: (5n + 5k − 4,3k − 1,1 − 2n),n,k ∈ Z.

Пример 32. (Турнир им. М. В. Ломоносова, 8 класс) Найдите натуральные корни уравнения:

19x + 98y = 1999.

Решение. Из данного уравнения нетрудно выразить x через y:

.

Чтобы x и y принимали целые значения, необходимо выполнение условия 4 − 3y19k, или 19k + 3y = 4, где k – целое число. Очевидная пара корней: k = 1 и y = −5 не подходит по условию задачи. Однако ее можно использовать для определения остальных целых корней, для этого из уравнения 19k+3y = 4 вычтем равенство 19·1−3·5 = 0 и получим соотношение 19(1−k) = 3(y+5). Так как 19 и 3 взаимно просты, то последнее равенство выполняется, если 1−k и y+5 имеют делители 3 и 19, соответственно, и общий делитель m. Таким образом, выполняются соотношения 1−k = 3m и y+5 = 19m, которые дают общее решение для 41 k, y и x: k = 1−3m, y = −5+19m, x = 105−5y+k = 131−98m, откуда получаем единственную пару положительных корней x = 33, y = 14.

Ответ: (33;14).

Пример 33. (Заочная физико-математическая олимпиада (6-11 классы, г. Москва)) Решить в целых числах систему уравнений

.

Решение. Запишем систему в виде

,

тогда получим (x² + y)² = y² + x + 6 или x(x³ + 2xy − 1) = 6. Следовательно, x делитель 6, т.е. x = ±1; ±2; ±3; ±6. Нам подходят лишь значения x = ±1; 2; 3; −6.

Если x = −1, y = 2, z = 3; x = 1, y = 3, z = 4; x = 2, y = −1, z = 3; x = 3, y = −4, z = 5; x = −6, y = −18, z = 18.

Ответ: (1;3;4), (−1;2;3), (3;−4;5), (−6;−18;18).

42

2.4 Метод, основанный на выделении полного квадрата

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

x² − 6xy + 13y² = 29.

Решение. Преобразуем левую часть уравнения, выделив полные квадраты, x² − 6xy + 13y² = (x² − 6xy + 9y²) + 4y² = (x − 3y)² + (2)² = 29, значит (2y)² ≤ 29.

Получаем, что y может быть равен 0; ±1; ±2.

1. y = 0.

(x − 0)² = 29. Не имеет решений в целых числах.

2. y = −1.

(x + 3)² + 4 = 29,

(x + 3)² = 25,

x + 3 = 5 или x + 3 = −5 x = 2 или x = −8.

3. y = 1.

(x + 3)² + 4 = 29,

(x − 3)² = 25,

x − 3 = 5 или x − 3 = −5        ⁴³ x = 8 или x = −2.

4. y = −2.

(x + 6)² + 16 = 29, (x + 6)² = 13. Нет решений в целых числах.

5. y = 2.

(x − 6)² + 16 = 29, (x − 6)² = 13. Нет решений в целых числах.

Ответ: (2;−1); (−8;−1); (8;1); (−2;1).

Пример 35. Найти все пары целых чисел p и q, удовлетворяющие системе неравенств:

,

Решение. Выделим полные квадраты в каждом из неравенств:

,

Геометрически, на координатной плоскости pOq, неравенства в по-√

следней системе задают точки внутри кругов радиусами 3 и        10 с центрами в точках (1;−2) и (−2;2) соответственно (рис. 1).

44             Решением системы будут точки с целочисленными координатами, лежащие в дважды заштрихованной области. Из рисунка видно, что там наверняка находятся только начало координат и точка (−1;0), но это, конечно, надо строго доказать, не ссылаясь на рисунок.

Рис. 1

Из последней системы неравенств, учитывая, что p,q ∈ Z, получим следующие ограничения:

,

45             Итак, рассмотрим все возможные значения, которые может принимать q.

Пусть q = 0, тогда система  примет вид

,

откуда p = 0 или p = −1.

Пусть q = −1, тогда система  примет вид

,

У второго неравенства этой системы нет решений в целых

числах.

Ответ: (0;0), (−1;0).

46

2.5 Метод решения уравнения с двумя переменными как квадратного относительно одной из переменных

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

5x² + 5y² + 8xy + 2y − 2x + 2 = 0.

Решение. Рассмотрим уравнение как квадратное относительно x:

5x² + (8y − 2)x + 5y² + 2y + 2,

D = (8y−2)² −4?5(5y² +2y+2) = 64y² −32y+4 = −100y² −40y−40 =

= −36(y² + 2y + 1) = −36(y + 1)².

Для того, чтобы уравнение имело решения, необходимо, чтобы D = 0.

−36(y + 1)² = 0.

Это возможно при y = −1, тогда x = 1.

Ответ: (1;−1).

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

47

                         2 2                      2               2               2              2

15x y + 28xy − 8x y + x + 5y − 38xy + 8x − 24y + 16 = 0.

Решение. Пытаться выделить полные квадраты в левой части исходного уравнения очень сложная и долгая задача.

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

y²(15x² + 28x + 5) − y(8x² + 38x + 24) + (x² + 8x + 16) = 0;

= x⁴ + 4x³ − 12x² − 32x + 64.

Упростим, найдя корни многочлена P(x) = x⁴+4x³−12x²−32x+64.

Решим уравнение P(x) = 0. Разделим обе части на x² 6= 0, тогда имеем:

.

48

Пусть , тогда

,

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

= 0 примет вид

t² + 16 + 4t − 12 = 0 ⇔ (t + 2)² = 0.

Значит, .

Отметим, что это же выражение для дискриминанта можно получить значительно проще, если перед всеми вычислениями разложить квадратные трехчлены 4x² + 19x + 12 и x² + 8x + 16 на множители.

Итак, решениями квадратного (так как коэффициент при старшей степени 15x² + 28x + 5, если x ∈ Z) уравнения являются

;

                49

Так как y₁ ∈ Z, то, по крайней мере, 5x + 1 должно быть делителем числа 19, следовательно, существуют лишь четыре возможности: 5x +

+ 1 = ±1, 5x + 1 = ±19, откуда ;0;  целыми числами

является x = −4, тогда, тогда.

Итак, нашли две пары (−4;0) и (0;4), являющиеся решением.

Аналогичными рассуждениями приходим к выводу, что 3x + 5 = ±1 или 3x + 5 = ±7, тогда целочисленным решением будет x = −2 и, следовательно, .

Ответ: (−2;−2), (−4;0), (0;4).

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

x² − xy + y² = x + y.

Решение. Преобразуем уравнение

x² − x(y + 1) + y² − y = 0.

Рассмотрим его как квадратное относительно x:

D = (y + 1)² − 4(y² − y) = −3y² + 6y + 1 ≥ 0,

3(y − 1)² ≤ 4, (y − 1)² ≤ 2.

          Проверка для y = 0;1;2 дает искомые решения.                                                                50

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

2.6 Метод, основанный на оценке выражений, входящих в уравнение

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

(x² + 4)(y² + 1) = 8xy.

Решение.

Заметим, что если (x₀;y₀) – решение уравнения, то (−x₀;−y₀) – тоже решение. И так как x = 0 и y = 0 не являются решением уравнения, то, разделив обе части уравнения на xy, получим:

.

Пусть x > 0, y > 0, тогда, согласно неравенству Коши

.

Получаем

51

,

тогда их произведение

,

значит,

.

Отсюда находим x = 2 и y = 1 – решение, тогда x = −2 и y = −1 – тоже решение.

Ответ: (2;1); (−2;−1).

Пример 40. (LXI Белорусская математическая олимпиада школьников, заключительный этап, 10 класс, г. Гомель, 2011) Найдите все тройки натуральных чисел (x,y,z), удовлетворяющих равенству

3^x + 7^y = 4^x.

Решение: При z = 0, уравнение, очевидно, в целых числах решений не имеет. При z = 1, легко видеть, y может равняться 0, и тогда x = 1. При z = 2 находим, что уравнению удовлетворяют только y = 1 и x = 2.

Пусть z ≥ 3. Тогда (3^x + 7^y)^...8. Покажем, что x – четное. Действительно, в противном случае 3^x имеет остаток 3 при делении на 8. А ⁵² поскольку 7^y может иметь только остатки 1 или 7 при делении на 8, то сумма 3^x+7^y не может делиться на 8. Итак, x = 2a для некоторого целого неотрицательного a. Тогда 7^y = 4^x −3^x = 2^2z −3^2a = (2^z −3^a)(2^z +3^a).

Следовательно, 2^z −3^a и 2^z +3^a являются степенями числа 7. При этом, так как 2^z + 3^a > 1, то (2^z + 3^a)^...7. А значит, ((2^z + 3^a) + (2^z − 3^a)).^..7, т.е. (2 · 2^z)^...7, что невозможно. Поэтому достаточно рассмотреть случай, когда 2^z − 3^a = 1, т.е. 2^z − 1 = 3^a. Так как при a ≥ 1 (поскольку z ≥ 3), то 2^z − 1^...3, что возможно только при четном z. Положим z = 2c для некоторого целого неотрицательного c. Тогда 4^c − 3^a = 1. При a = 1, находим c = 1 и, в результате, получаем уже ранее найденное решение x = 1, z = 2, y = 1. Если a > 1, то 4^c = 3^a + 1 имеет остаток 1 при делении на 9. Степень числа 4 имеет такой остаток только при c, кратном 3. Но тогда, так как 4³ имеет остаток 1 при делении на 7, 4^c будет иметь остаток 1 и при делении на 7. В результате, при таком c выражение 3^a = 4^c −1 должно делиться на 7 без остатка – противоречие. Таким образом, других решений, кроме двух ранее найденных, нет. Ответ: (1;0;1) и (2;1;2).

Пример 41. (Минская XLIX олимпиада, 9 класс). Найдите все пары (a,b) натуральных чисел a и b, удовлетворяющих равенству

45^a − b^b = 1998.

Решение. Числа 1998 и 45^a кратны 3, поэтому и число b^b должно быть кратно 3, т.е. b = 3k для некоторого натурального k. Тогда 45^a = ⁵³

= 1998+3³k·k^3k. Оба слагаемых в правой части полученного равенства кратны 3³ = 27, поэтому число 45^a также должно быть кратно 27, т.е. a ≥ 2. Значит, 45^a = 5^a·9^a делится на 9² = 81. Если k ≥ 2, то тогда число 3³k·k^3k делилось бы на 81, поэтому и число 1998 должно делиться на 81, что неверно. Следовательно, k = 1, т.е. b = 3, и поэтому 5^a = 1998+3³ = = 2025 = 45², или a = 2.

Ответ: (2;3).

Пример 42. (Минская L олимпиада, 11 класс). Найдите все натуральные числа m и n, удовлетворяющие равенству

(m + n)m2+n2 = (m2 + n2 + 2)mn.

Решение. Поскольку для любых различных натуральных m и n выполнены неравенства

m² + n² > 2mn

и

(m + n)² = m² + n² + 2mn > m² + n² + 2,

то

.

Поэтому, если числа m и n удовлетворяют равенству из условия, то они не могут быть различными, так что необходимо m = n. С учетом

этого уравнение из условия принимает вид (2m)^2m2 = (2m² + 2)^m2, или,

54 равносильно, m² = 1. Значит, m = n = 1.

Ответ: m = 1, n = 1.

Пример 43. (Минская LII олимпиада, 10 класс). Найдите все натуральные числа m и n, удовлетворяющие равенству

(n!)^m! − (m!)ⁿ! = 28.

(Запись k! обозначает произведение всех натуральных чисел от 1 до k включительно.)

Решение. Ясно, что m = n, иначе выражение в левой части уравнения равно 0, а не 28.

Если m > n, то m! = 1 · ... · n · ... · m, значит, m! делится на n. Так как n! = 1 · ... · n, то и m! делится на n. Поэтому можно обозначить n! = an и m! = bn для некоторых натуральных a и b. Тогда заданное уравнение запишется как (an)^bn −(bn)^an = 28, откуда следует, что nⁿ делит 28. Единственные значения n, для которых это возможно, 1 или 2. Значение n = 1 не подходит (левая часть исходного уравнения в этом случае отрицательна). Если n = 2, то уравнение принимает вид 2^k − k² = 28, где через k обозначен m!. Из этого равенства вытекает, что k четно, т.е. k = 2q для некоторого натурального q. Поэтому равенство перепишется в виде 2^2q − (2q)² = 28, или по формуле разности квадратов (2^q + 2q)(2^q − 2q) = 28, откуда, сократив на 4, получим ^q−1 +q)(2^q−1 −q) = 7. Так как единственными положительными дели- 55

(2

телями 7 являются 1 и 7, то последнее равенство равносильно системе

,

Вычитая почленно из первого уравнения этой системы

второе ее уравнение, получим 2q = 6, откуда q = 3.

Непосредственно проверкой убеждаемся, что q = 3 является решение системы. Значит, k = 6, а поскольку 6 = 3!, то m = 3.

Если n > m, то аналогично, m = 1 или m = 2. В первом случае (m = 1) получим n! = 29 – нет решений. Во втором случае (m = 2) имеем: (n!)² − 2^n! = 28, что неозможно, так как a² − 2^a ≤ 0.

Ответ: n = 2, m = 3.

Пример 44. (Минская LII олимпиада, 11 класс). Решите уравнение

n² − 5p^m = 1,

если n, m и p – натуральные числа и число p – простое.

Решение.

Первое решение. Если n либо делится на 5, либо имеет остаток 2 или 3 при делении на 5, то равенство из условия задачи невозможно (девая часть его при делении на 5 имеет остаток либо 0, либо 4 соответственно, а правая остаток 1). Поэтому n = 5k ± 1 для некоторого натурального k. Подставляя это выражение в исходное уравнение, после упрощений получим

                                                                                k(5k ± 2) = p^m,                                                                               56

откуда, поскольку p – простое число, k = p^a для некоторого целого a, и тогда 5k ± 2 = p^m−a вследствие k(5k ± 2) = p^m. Так как k < 5k ± 2 при натуральном .

Разделив равенство k(5k ±2) = p^m на k², получим, что 5± _k² = p^m−2a – натуральное число. Поэтому k равно 1 или 2.

В первом случае (k = 1) из k(5k ± 2) = p^m находим p^m = 3 или 7,

т. е. m = 1, p = 3 или 7, а n = 4 или 6 соответственно.

Во втором случае (k = 2), очевидно, p = 2, а m = 4 и n = 9. Второе решение. Перепишем заданное равенство в виде:

(n − 1)(n + 1) = 5p^m.

Пусть p – простое нечетное число. Тогда правая часть равенства

(n−1)(n+1) = 5p^m нечётна, поэтому должна быть нечётна и его левая часть. Следовательно, так как числа n − 1 и n + 1 имеют одинаковую чётность, то оба они нечётны, а так как они отличаются на 2, то они взаимно просты. Поэтому одно из чисел n − 1 или n + 1 должно быть равно либо 1, либо 5.

Равенство (n−1)(n+1) = 5p^m, если n−1 = 1 или n+1 = 1, очевидно, невозможно. Если n − 1 = 5, то 5p^m = (n − 1)(n + 1), т. е. p = 7, m = 1. Если же n + 1 = 5, то 5p^m = 3 · 5, т. е. p = 3, m = 1.

Пусть p = 2. Тогда n − 1 и n + 1 чётны; значит, n = 2k + 1 для некоторого натурального k, и поэтому равенство (n − 1)(n + 1) = 5p^m перепишется как k(k+1) = 5·2^m−2. Следовательно, поскольку числа k и ⁵⁷ k+1 взаимно просты, одно из них должно быть равно 1 или 5. В случаях k = 1 или k = 5 правая часть полученного равенства, соответственно, не делится на 5 или делится на 3, чего быть не может. Случай k +1 = 1 невозможен при натуральном k, а в случае k+1 = 5 получаем 5·2^m−2 = = 4 · 5, т. е. m = 4, а так как k = 4, то n = 2k + 1 = 9.

Ответ: (4;1;3), (6;1;7), (9;4;2).

58

2.7 Метод бесконечного (непрерывного) спуска

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

Часто метод бесконечного спуска применяется в более простой форме. Предположив, что мы уже добрались до естественного конца, видим, что «остановиться» не можем.

Пример 45. Докажем неразрешимость в натуральных числах уравнения:

8x⁴ + 4y⁴ + 2z² = t⁴.

Решение. Допустим, что решение есть, и x = m, y = n, z = p, t = q – решение с наименьшим возможным x.

Из вида уравнения следует, что q = 2q₁.

Подставим решение в уравнение и сократим на 2:

.

Получаем, что p = 2p₁, следовательно,

59

.

Аналогично, n = 2n₁,

и, m = 2m₁,

.

Значит, x = m₁, y = n₁, z = p₁, t = q₁ – также решения нашего уравнения.

Но m₁ < m, что противоречит выбору исходного решения. Значит, решений нет.

Ответ: Решений нет.

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

Пример 46. Найти все решения в натуральных числах уравнения

x² − 2y² = 1.

Решение. Заметим, что x₁ = 3, y₁ = 2 – решение исходного уравнения.

Из тождества (3x + 4y)² − 2(2x + 3y)² = x² − 2y² следует, что пара ⁶⁰ x,y – решение, то пара 3x + 4y, 2x + 3y – тоже решение.

Найдена бесконечная последовательность решений (x₁,y₁); (x₂,y₂); и т.д.

Покажем, что других пар чисел, удовлетворяющих исходному уравнению, нет.

Пусть x, y – некоторое решение.

Из тождества (3x + 4y)² − 2(2x + 3y)² = x² − 2y² следует, что (3x + 4y,2x + 3y) – также решение.

Из условия задачи 9 = 9x² − 18y² > −2y² следует, что 3x > 4y.

При y > 2 из условия задачи 4 = 4x² −8y² < y² следует, что 3y > 2x.

То есть при y > 2 мы из решения x, y получаем решение x⁽¹⁾, y⁽¹⁾ в натуральных числах, причем x⁽¹⁾ < x, y⁽¹⁾ < y. Этот процесс не может продолжаться бесконечно, и когда-нибудь будет получено решение x⁽ⁿ⁾, y(n), где y(n) ≤ 2.

Из условия задачи следует, что y⁽ⁿ⁾ 6= 1. Значит y⁽ⁿ⁾ = 2. Следовательно, x⁽ⁿ⁾ = 3, то есть, числа x и y принадлежат построенной ранее последовательности.

Ответ. (3;2), (3x + 4y,2x + 3y), где x, y – решение уравнения.

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

Решение.

1.                       Выберем неизвестное, имеющее наименьший коэффициент (в на- 61 шем случае это x), и выразим его через другое неизвестное:

.

2.                       Выделим целую часть:

.

Очевидно, что x будет целым, если выражение  окажется целым, что, в свою очередь, будет иметь место тогда, когда число 4 − 3y без остатка делится на 5.

3.Введем дополнительную целочисленную переменную z следующим образом:

4 − 3y = 5z.

В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами.

4.     Решаем его уже относительно переменной . Выделяя целую часть, получим:

.

5.     Рассуждая аналогично предыдущему, вводим новую переменнуюu:

3u = 1 − 2z.

62 6. Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z:

Требуя, чтобы  было целым, получим:

1 − u = 2v,

откуда

u = 1 − 2v.

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

7.     Теперь необходимо «подняться вверх». Выразим через переменнуюv сначала z, потом y и затем x:

1;

;

8.     Формулы x = 3+8v и y = 3−5v, где v – произвольное целое число, представляют общее решение исходного уравнения в целых числах.

Замечание. Таким образом, метод спуска предполагает сначала последовательное выражение одной переменой через другую, пока в пред- 63 ставлении переменной не останется дробей, а затем, последовательное «восхождение» по цепочке равенств, для получения общего решения уравнения.

2.8 Решение диофантовых уравнений с помощью алгоритма Евклида

Определение 1. Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида

ax + by = c,

где a,b,c ∈ Z и (a,b,c) = 1.

Определение 2. Решением уравнения ax + by = c, где a,b,c ∈ Z и (a,b,c) = 1, называется пара целых чисел, при подстановке которых в уравнение ax + by = c получается верное числовое равенство.

Теорема. Диофантово уравнение ax + by = c разрешено в целых числах тогда и только тогда, когда (a,b) = 1.

Доказательство.

Необходимость. Предположим, что (a,b) = d > 1 и докажем, что диофантово уравнение ax + by = c неразрешимо в целых числах. Предположим, что существуют x₀, y₀ ∈ Z, что ax₀ + by₀ = , то есть (x₀,y₀) – решение ax + by = c. Очевидно, что из (a,b) = d > 1 и ax₀ + by₀ = получается, что с делиться на d, то есть d – общий делитель чисел (a,b,c).

Следовательно, _d¹ · d = 1, противоречие.                                                                                      ⁶⁴

Достаточность. Пусть (a,b) = 1, тогда по критерию НОДа: суще-

                         0           0                                                                       0                     0

ствуют x , y ∈ Z, что 1 = ax + by . Домножим обе части равенства на

0    0                      0                      0 c, получим a(cx ) + b(cy ) = c. Следовательно, cx , cy – целые решения 0 уравнения ax + by = c. Обозначим их через x₀ и y₀, то есть cx = x₀,

0

cy = y₀. Тем самым, доказано, что если (a,b) = 1, то диофантово уравнение ax+by = c имеет целое решение (x₀,y₀). Покажем, как найти все целые решения этого уравнения:

1)     если c = 0, имеем, ax+by = 0, следовательно,. Но по условию y ∈ Z и (a,b) = 1, отсюда делится на b и (a,b) = 1. Следовательно, по свойству взаимно простых чисел, делится на b, то есть существует t ∈ Z, что x = bt. Отсюда y = −at. Таким образом, целыми решениями

 x = bt,

такого однородного уравнения является:      t∈Z. y = −at;

2)     если c 6= 0, имеем ax + by = c и уравнение ax + by = c разрешимо в целых числах. Существуют x₀, y₀ ∈ Z, что ax₀ + by₀ = c. Вычтем ax + by = c уравнение ax₀ + by₀ = c, получим a(x − x₀) + b(y − y₀) = = 0, а данное уравнение совпадает с типом уравнения, рассмотренным в пункте 1).

Таким образом, пара (x−x₀,y−y₀) – решение уравнения a(x−x₀)+ + b(y − y₀) = 0. Отсюда, согласно случаю 1) имеем:

bt, t∈Z.

                                                                                y − y₀ = −at;                                                                                     65

Пример 48. Решить уравнение

12x − 17y = 2.

Решение. 12x − 17y = 2, (12,−17,2), следовательно, это диофантово уравнение, (12,−17) = 1. Данное уравнение разрешимо в целых числах. Найдем выражение числа 1 через a и b, a = 12, b = −17, но мы будем рассматривать |b|, так как y ∈ Z.

12 · (−7) + 17 · 5 = 1; 12 · (−7) − 17 · (−5) = 1; 12 · (−14) − 17 · (−10) = 2.

Следовательно,

Ответ: (−14 − 17t,−10 − 12t), k ∈ Z. Пример 49. Решите уравнение

24x − 17y = 2.

Решение. (24,17,2) = 1. Это диофантово уравнение, НОД(24,17) = 1. 66 Следовательно, данное уравнение разрешимо в целых числах. Найдем частное решение (x₀,y₀) с помощью алгоритма Евклида:

24 = 17 · 1 + 7;

17 = 7 · 2 + 3;

7 = 3 · 2 + 1; 3 = 1 · 3 + 0.

Найдем линейное представление НОДа:

1 = 7 − 3 · 2 = 7 − (17 − 7 · 2) · 2 = 7 − 17 · 2 + 7 · 4 + 5 · 7 − 2 · 17 =

= 5 · (24 − 17 · 1) − 2 · 17 = 5 · 24 − 5 · 17 − 2 · 17 = 5 · 24 − 7 · 17 = = 24 · 5 − 17 · 7.

24 · 5 − 17 · 7 = 1;

24 · 10 − 17 · 14 = 2;

Ответ:

Пример 50. Решите уравнение

5x − 3y = −1.

Решение. (5,3,−1) = 1. Это диофантово уравнение, НОД(5,3) = 1, 67 Данное уравнение разрешимо в целых числах. Найдем частное решение (x₀,y₀ с помощью алгоритма Евклида:

5 = 3 · 1 + 2;

3 = 2 · 1 + 1.

Найдем линейное представление НОДа:

1 = 3 − 2 · 1 = 3 − (5 − 3 · 1) = 3 · 2 − 5 · 1.

5 · (−1) − 3 · (−2) = 1;

5 · 1 − 3 · 2 = 1;

Ответ: (1 + 3t,2 − 5t), k ∈ Z.

Пример 50. Решите уравнение

17x + 11y = 6.

Решение. (17,11,6) = 1. Это диофантово уравнение, НОД(17,11) = 1. Данное уравнение разрешимо в целых числах. Найдем частное решение (x₀,y₀) с помощью алгоритма Евклида:

17 = 11 · 1 + 6;

68

11 = 6 · 1 + 5;

6 = 5 · 1 + 1; 5 = 1 · 5 + 0.

Найдем линейное представление НОДа:

1  = 6 − 5 · 1 = 6 − (11 − 6 · 1) · 1 = 6 · 2 − 11 = (17 − 11 · 1) · 2 − 11 =

= 17 · 2 − 11 · 2 − 11 = 17 · 2 + 11 · (−2 − 1) = 17 · 2 − 11 · 3.

17 · 2 − 11 · 3 = 1;

17 · 12 + 3 · (−18) = 6;

Ответ: (12 − 11t,−18 + 17t), k ∈ Z. Пример 51. Решите уравнение

130x + 160y = 3000.

Решение. 13x + 16y = 300. (13,16,300) = 1. Это диофантово уравнение, НОД(13,16) = 1. Данное уравнение разрешимо в целых числах. Найдем частное решение (x₀,y₀) с помощью алгоритма Евклида:

16 = 13 · 1 + 3;

69 13 = 3 · 4 + 1. Найдем линейное представление НОДа:

1 = 13 − 3 · 4 = 13 − (16 − 13 · 1) · 4 = 13 · 5 + 16 · (−4).

13 · 5 + 16 · (−4) = 1;

13 · 1500 + 16 · (−1200) = 300;

Ответ:

Пример 52. Стоимость товара 23 рубля. Покупатель имеет только двухрублевые, а кассир пятирублевые монеты. Можно ли осуществить покупку без предварительного размена денег?

Решение. Пусть x – количество двухрублевых монет, y – количество пятирублевых монет. Составим уравнение 2x − 5y = 23.

Заметим, что (2,5,23) = 1. Это диофантово уравнение, НОД(2,5) = = 1, следовательно, данное уравнение разрешимо в целых числах. Найдем частное решение (x₀,y₀) с помощью алгоритма Евклида:

1  = 5 · 1 − 2 · 2;

2  · (−2) + 5 · 1 = 1;

2  · (−2) − 5 · (−1) = 1;

                                                                 2 · (−46) − 5 · (−23) = 23;                                                                    70

Ответ:

Пример 53. Решить диофантово уравнение

8x + 3y = 2.

Решение. (8,3,2) = 1, это диофантово уравнение. (8,3) = 1 – данное уравнение разрешимо в целых числах.

.

8 · (−1) + 3 · 3 = 1;

8 · (−2) + 3 · 6 = 2;

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

Ответ: (−2 + 3t,6 − 8t), t ∈ Z.

Пример 54. Решить диофантово уравнение

8x + 5y = 49.

Решение. (8,5,49) = 1 – это диофантово уравнение; (8,5) = 1 – дан- 71 ное уравнение разрешимо в целых числах.

.

Следовательно,

1 = 3 − 2 · 1 = 3 − (5 − 3 · 1) = 3 − 5 · 1 + 3 · 1 = 3 · (1 + 1) − 5 · 1 =

= 3 · 2 − 5 · 1 = (8 − 5 · 1) · 2 − 5 · 1 = 8 · 2 − 5 · 2 − 5 · 1 =

= 8 · 2 − 5 · (2 + 1) = 8 · 2 − 5 · 3.

8 · 2 + 5 · (−3) = 1;

8 · 98 + 5 · (−141) = 49;

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

Ответ: (98 + 5t,−141 − 8t), t ∈ Z.

Пример 55. Решить диофантово уравнение

3x − 2y + 11 = 0.

Решение. 3x−2y = −11; (3,−2,−11) = 1 – это диофантово уравнение; (3,−2) = 1 – данное уравнение разрешимо в целых числах.

                                                       .                                                           72

3 · 1 − ·1 = 1;

3 · (−11) − 2 · (−11) = −11;

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

Ответ: (−11 − 2t,−11 − 3t), t ∈ Z. Пример 56. Решить уравнение

75x − 39y = 1.

Решение. (75,39,1) = 1 – это диофантово уравнение; (75,39) 6= 1 – уравнение неразрешимо в целых числах.

Ответ: Неразрешимо в целых числах.

73

2.9 Решение диофантовых уравнений с помощью цепных дробей

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

127x − 52y + 1 = 0.

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

.

Проделаем такие же преобразования с полученной в знаменателе неправильной дробью :

.

Теперь исходная дробь примет вид

.

74

Повторим те же рассуждения для дроби . Тогда

,

выделяя целую часть неправильной дроби  придем к окончательному результату:

.

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

,

Приведем полученное выражение к общему знаменателю и отбросим его, тогда получим 127·9−52·22+1 = 0. Из сопоставления полученного

равенства с уравнением 127x − 52y + 1 = 0 следует, что x = 9, y = 22                            75

– решение этого уравнения, и согласно теореме все его решения будут содержаться в прогрессиях x = 9+52t,y = 22+127t (t = 0,±1,±2,...).

Ответ: (9 + 52t;22 + 127t), t ∈ Z.

Определение 1. Конечной цепной дробью называется выражение вида:

,

где все a_i ∈ N, i = 1,n, a₀ ∈ Z, a_n 6= 1.

Обозначается .

Определение 2. Элемент a_i называется элементом цепной дроби.

Определение 3. Отрезок цепной дроби от a₀ до a_k называется подходящей дробью k–го порядка для данной цепной дроби и обозначается

A_k = [a₀;a₁,a₂,...,a_k],k ≤ n.

Замечание. Последняя подходящая дробь совпадает со всей дробью.

Определение 4. Число a₀ называется нулевой подходящей дробью (подходящей дробью нулевого порядка),.

Теорема 1. Всякое рациональное число можно однозначно представить в виде конечной цепной дроби, причем элементы цепной дроби [a_i] будут являться неполными частными из алгоритма Евклида для чисел a и b.

76

Доказательство.

, применим к a и b алгоритм Евклида:

a = ba₀ + r₁,0 ≤ r₁ < b, b = r₁a₁ + r₂,0₂ < r₁,

r1 = r2a2 + r3,03 < r2,

...

r_n−2 = r_n−1a_n−1 + r_n,0_n < r_n−1, r_n−₁ = r_na_n + 0.

Заметим, что a₀ ∈ Z, a_i ∈ N, i = 1,n. Разделим первое равенство на b, второе на r₁ и так далее.

,

                                                                                                               ,

77

Подставим в первое равенство все остальные, получим:

,

a_i ∈ N, i = 1,n, a₀ ∈ Z, a_n 6= 1.

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

Замечание. Если в определении 1 допустить, что a_n = 1, то тогда представление рационального числа  в виде конечной цепной дроби не единственно.

78

Метод построения подходящих дробей к данной цепной дроби

Пусть дана дробь ,

 – подходящая дробь нулевого порядка, следовательно,

.

k).

Таблица 2 – Таблица расчетов подходящих дробей

k	0	1	2	···	n
ak	a0	a1	a2	···	an
pk	p0 = a0	p1 = a0a1 + 1	p1a2 + p0	···	pn−1an + pn−2
qk	q0 = 1	q1 = a1	q1a2 + q0	···	qn−1an + qn−2

79

Применение цепных дробей к решению диофантовых уравнений

Рассмотрим уравнение ax + by = c, где (a,b,c) = 1 и (a,b) = 1. Следовательно существуют такие целые значения x, y, являющиеся решениями данного диофантова уравнения.

, тогда по свойству подходящих дробей

справедливо: , и aq_n−1 − bp_n−1 =

= (−1)ⁿ⁻¹.

Домножим обе части равенства на c или (−c):

a(cq_n−1) − b(cp_n−1) = c(−1)ⁿ⁻¹,

Затем домножим на (−1)ⁿ⁻¹, получим:

a((−1)n−1cqn−1) − b((−1)n−1cpn−1) = c.

80

Решить уравнение: 45x − 13y = 2.

(45;−13;2) = 1 и (45;−13) = 1, значит это диофантово

уравнение и оно разрешимо в целых числах.

;

.

Таблица 3 – Таблица расчета подходящих дробей

k	0	1	2
ak	3	2	6
pk	3	7	45
qk	1	2	13

;

45 · 2 − 13 · 7 = −1,

45 · (−4) − 13 · (−14) = 2 ⇒ x₀ = −4,y₀ = −14, поэтому

81

(−4 − 13t,−14 − 45t), k ∈ Z.

64x − 25y = 3.

(64,25,3) = 1 и (64,25) = 1 – имеем диофантово уравнение

и оно разрешимо в целых числах.

.

Таблица 4 – Таблица расчета подходящих дробей.

k	0	1	2	3	4	5
ak	1	1	1	3	1	2
pk	2	3	5	18	23	64
qk	1	1	2	7	9	25

;

64 · 9 − 25 · 23 = 1, 64 · 27 − 25 · 69 = 3 ⇒ x₀ = 27,y₀ = 69, поэтому

.

82

Ответ: (27 − 25t,69 − 64t), k ∈ Z.

571x + 359y = 7.

(571,359,7) = 1 и (571,359) = 1 – имеем диофантово урав-

нение и оно разрешимо в целых числах.

.

Таблица 5 – Таблица расчета подходящих дробей.

k	0	1	2	3	4	5	6	7	8
ak	1	1	1	2	3	1	4	1	2
pk	1	2	3	8	27	35	167	202	571
qk	1	1	2	5	17	22	105	127	359

;

571 · 127 − 35 · 202 = −1,

571 · (−127) + 359 · 202 = 1,

571 · (−889) + 359 · 1414 = 7 ⇒ x₀ = −889,y₀ = 1414, поэтому

                                                                                                                                          83

(−889 + 359t,1414 − 571t), k ∈ Z.

29x + 37y = 2.

(29,37,2) = 1 и (29,37) = 1 – имеем диофантово уравнение

и оно разрешимо в целых числах.

.

Таблица 6 – Таблица расчета подходящих дробей.

k	0	1	2	3	4	5
ak	1	3	1	1	1	2
pk	1	4	5	9	14	37
qk	1	3	4	7	11	29

;

37 · 11 − 29 · 14 = 1,

29 · (−14) + 37 · 11 = 1,

29 · (−28) + 37 · 22 = 2 ⇒ x₀ = −28,y₀ = 22, поэтому

84

.

(−28 + 37t,22 − 29t), k ∈ Z.

2121x − 1500y = 21.

(2121,1500,21) = 3, 707x − 500y = 7; (707,500,21) = 1 и (707,500) = 1 – имеем диофантово уравнение и оно разрешимо в целых числах.

.

Таблица 7 – Таблица расчета подходящих дробей.

k	0	1	2	3	4	5	5
ak	1	2	2	2	2	5	3
pk	1	3	7	17	41	222	485
qk	1	2	5	12	29	157	500

;

707 · 157 − 500 · 222 = −1,

707 · (−157) − 500 · (−222) = 1, 707 · (−1099) − 500 · (−1554) = 7;

x₀ = −1099,y₀ = −1554, поэтому

85

.

(−1099 − 500t,−1554 − 707t), k ∈ Z.

38x + 117y = 209.

(38,117,209) = 1 и (38,117) = 1 – имеем диофантово урав-

нение и оно разрешимо в целых числах.

.

Таблица 8 – Таблица расчета подходящих дробей.

k	0	1	2	3
ak	3	12	1	2
pk	3	37	40	117
qk	1	12	13	38

;

117 · 13 − 38 · 40 = 1,

38 · (−40) + 117 · 13 = 1, 38 · (−8360) + 117 · 520 = 209;

x₀ = −8360,y₀ = 520, поэтому

86

.

(−8360 + 117t,520 − 38t), k ∈ Z.

119x − 68y = 34.

7x−4y = 2, (7,−4,2) = 1 и (7,−4) = 1 – имеем диофантово

уравнение и оно разрешимо в целых числах.

.

Таблица 9 – Таблица расчета подходящих дробей.

k	0	1	2
ak	1	1	3
pk	1	2	7
qk	1	1	4

;

7 · 1 − 4 · 2 = −1,

7 · (−1) − 4 · (−2) = 1,

7 · (−2) − 4 · (−4) = 2 ⇒ x₀ = −2,y₀ = −4, поэтому

87

.

(−2 − 4t,−4 − 7t), k ∈ Z.

258x − 175y = 113.

(258,−175,113) = 1 и (258,−175) = 1 – имеем диофантово

уравнение и оно разрешимо в целых числах.

.

Таблица 10 – Таблица расчета подходящих дробей.

k	0	1	2	3	4
ak	1	2	9	4	2
pk	1	3	28	115	258
qk	1	2	19	78	17

;

258 · 78 − 175 · 115 = −1,

258 · (−78) − 175 · (−115) = 1,

258·(−8814)−175·(−12995) = 113 ⇒ x₀ = −8814,y₀ = −12995, поэтому

88

.

(−8814 − 175t,−12995 − 258t), k ∈ Z.

587x + 113y = 1.

(587,113,1) = 1 и (587,113) = 1 – имеем диофантово урав-

нение и оно разрешимо в целых числах.

.

Таблица 11 – Таблица расчета подходящих дробей.

k	0	1	2	3
ak	5	5	7	3
pk	5	26	187	587
qk	1	5	36	113

,

587 · 36 + 113 · (−187) = 1,⇒ x₀ = 36,y₀ = −187, поэтому

.

89

Ответ: (36 + 113t,−187 − 587t), k ∈ Z.

3587x − 2743y = 1.

Решение. (3587,2743,1) = 1 и (3587,2743) = 2111 – имеем диофантово уравнение, но оно неразрешимо в целых числах. Ответ: неразрешимо в целых числах.

90

2.10 Решение диофантовых уравнений с помощью сравнений

Определение 1. Если два числа a и b имеют одинаковые остатки при делении на m, то говорят, что a и b сравнимы по модулю m, и пишут a ≡ b(mod m) (читают: a сравнимо с b по модулю m).

Теорема 1. Сравнение a ≡ b(mod m) имеет место в том и только в том случае, если разность a − b делится на m.

Доказательство. Предположим, что a ≡ b(mod m), то есть числа a и b дают при делении на m один и тот же остаток r. Тогда a = mq₁ + r, b = mq₂ +r, где q₁, q₂ – некоторые целые числа. Вычитая почленно одно равенство из другого, получаем: a−b = mq₁ −mq₂ = m(q₁ −q₂). Отсюда следует, что разность a − b делится на m. Обратно, пусть a − b делится на m, то есть a − b = km. Разделим с остатком b на m: b = qm + r, где 0 ≤ r ≤ m. Сложив равенства a − b = km и b = qm + r, получим: a = km + qm + r = m(k + q) + r. А это означает, что число имеет тот же остаток при делении на m, что и число b. Значит, a ≡ b(mod m).

Теорема 2. Сравнения с общим модулем можно почленно складывать и вычитать, то есть если a ≡ b(mod m) и c ≡ d(mod m), то a + c ≡

≡ b + d(mod m) и a − c ≡ b − d(mod m).

91 Доказательство. Так как a ≡ b(mod m) и c ≡ d(mod m), то по теореме 1: a − c и b − d делятся на m, то есть a − b = km, c − d = hm. Складывая эти два равенства, получаем a − b + c − d = km + hm или

(a + c) − (b + d) = (k + h)m. Следовательно, разность (a + c) − (b + d)

делится на m, а это значит, что a+ ≡ b+d(mod m). Сравнение a−c ≡ ≡ b − d(mod m) доказывается аналогично.

Теорема 3. Сравнения с общим модулем можно почленно умножать, то есть если a ≡ b(mod m) и c ≡ d(mod m), то a · c ≡ b · d(mod m).

Доказательство. Так как a ≡ b(mod m) и ≡ d(mod m), то по теореме 1: (a−c) и (b−d) делятся на m, то есть a−b = km, c−d = hm. Поэтому ac−bd = (ac−ad)+(ad−bd) = a(c−d)+d(a−b) = ahm−dkm = m(ah−

−kd), то есть разность (ac−bd) делится на m. Значит, ac ≡ bd(mod m).

Замечание. Теоремы 2 и 3 верны для любого числа слагаемых или множителей.

Рассмотрим диофантово уравнение ax+by = c, (a,b,c) = 1, (a,b) = 1 следовательно, существуют x,y ∈ Z – решения ax + by = c, (a,b,c) = = 1, (a,b) = 1.

 при целом x нужно, чтобы y ∈ Z, а это будет тогда и только тогда, когда , тогда  – решение ax + by = c, (a,b,c) = 1, (a,b) = 1, где .

92

Пример 68. Решить уравнение

14x − 10y = 6.

Решение. (14,10,6) 6= 1, 7x − 5y = 3 – диофантово уравнение, так как (7,5,3) = 1, а поскольку (7,5) = 1, то ∃x,y ∈ Z – решение данного диофантова уравнения.

, так как (7,5) = 1, то

сравнение имеет единственное решение. 2x ≡ 8(mod 5), x ≡ 4(mod 5), x = 4 + 5t, t ∈ Z.

Ответ: .

Пример 69. Решить уравнение

5x − 7y = 6.

Решение. (5,7,6) = 1 – диофантово уравнение, а поскольку (5,7) = 1, то ∃x,y ∈ Z – решение данного диофантова уравнения.

), так как (5,6) = 1, то

сравнение имеет единственное решение.

                                                                              5x ≡ 20(mod 7),                                                                              ⁹³

x ≡ 4(mod 7), x = 4 + 7t,t ∈ Z.

Следовательно,

Ответ: (4 + 7t,2 + 5t), t ∈ Z.

Пример 70. Решить уравнение

13x + 29y = 19.

Решение. (13,29,19) = 1 – диофантово уравнение, а поскольку (13,29) = 1, то ∃x,y ∈ Z – решение данного диофантова уравнения.

, так как (−13,19) = 1, то сравнение имеет единственное решение.

8x ≡ −24(mod 29),

94

Следовательно, .

Ответ: (−3 + 29t,2 − t), k ∈ Z.

Пример 71. Решить уравнение

7x − 3y = 2.

Решение. (7,3,2) = 1 – диофантово уравнение, а поскольку (7,3) = 1, то ∃x,y ∈ Z – решение данного диофантова уравнения.

, так как (7,2) = 1, то

сравнение имеет единственное решение.

7x ≡ 14(mod 3),

Cледовательно,

Ответ: (2 + 3t,4 + t), k ∈ Z.

95

2.11 Уравнение Пелля

Одним из ярких представителей класса диофантовых уравнений второй степени является уравнение Пелля (его еще называют неопределённым уравнением Ферма), то есть уравнение: x² − ay² = 1, где a – целое положительное число, не являющееся полным квадратом.

Каждое уравнение Пелля имеет решение (±1;0), которое называется тривиальным. Все остальные решения называются нетривиальными.

Наименьшим нетривиальным решением уравнения Пелля называется

√

такое решение, при котором двучлен x + ay принимает наименьшее значение из всех возможных.

Решений уравнения Пелля бесконечно много. Доказывается это с по-

√

мощью бинома Ньютона следующим образом. Двучлен x₀ + ay₀, где x₀, y₀ – наименьшее нетривиальное решение, возводится в n-ую степень и раскладывается по биному Ньютона. Если привести подобные слагае-

√

мые, то получается выражение вида x_n + ay_n, где x_n, y_n – целые числа. Далее надо провести аналогичные операции для сопряжённого двучлена. В результате получается следующая система уравнений:

                                                           ,                                                                 96

Далее следует перемножить эти равенства и «свернуть» по формуле разности квадратов. Так как число n может принимать бесконечное множество значений, то решений уравнения Пелля тоже бесконечное множество. Существует несколько методов нахождения «всех» решений уравнения Пелля.

Метод 1. Первый метод основан на формулах:

,

Доказывается, что все решения получаются в результате возведения

√

в n-ую степень двучлена x₀ + ay₀. Этот способ удобен при нахождении решения «вручную», так как надо работать с целыми числами, выполняется «мало» операций и не требуется никаких данных, кроме наименьшего решения. Но при компьютерной реализации возникают проблемы. Во-первых, сложность представления. Требуется создавать множество дополнительных переменных, вводить треугольник Паскаля и n+1 слагаемых, возводить в степени «большие» числа, для чего на многих языках программирования требуется создавать отдельную функцию. Вовторых, надо работать с n + 1 «большими» числами (число a будем называть «большим», если a > 4294967295), для чего требуется создавать

новый тип чисел и разрабатывать для них все необходимые операции

97

(суммирование, умножение, разность, деление, хранение). К тому же требуется найти наименьшее решение, что является проблематичным.

Метод 2. Второй метод основан на операции «гиперболический поворот», переводящей одну целочисленную точку на графике в следующую, и основан на формулах:

,

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

Метод 3 (индийский метод). Сначала берут два целых числа, подставляют в правую часть уравнения Пелля и находят результат. Выбирают такие числа, чтобы правая часть была близка к единице. Далее получившееся уравнение умножается на уравнение Пелля. Скобки раскрывают, выделяют полные квадраты и подбирают новые числа, удовлетворяющие неравенству. Далее сокращают обе части равенства на НОД и опять умножают на уравнение Пелля и так далее, пока в правой части не получится единица. Недостатки алгоритма огромны: требуется множество проверок, действий, переменных. Но самым проблематичным является первый этап. Оказывается, для приближения можно брать далеко не любые целые числа, поэтому при компьютерной реализации надо перебирать и проверять множество чисел, что занимает большую

часть времени. При «ручном» нахождении наименьшего решения этим

98 алгоритмом можно легко ошибиться.

Метод 4 (английский метод). Алгоритм, основанный на цепных дро-

√

бях, выполняется следующим образом: a раскладывается в цепную дробь, которая будет периодична со второго полного частного. Далее находится период k и вычисляется выражение kn, где n – такое наименьшее натуральное число, что kn чётно. Далее находится подходящая дробь с таким индексом, числитель и знаменатель которой и будут наименьшим решением. Доказательство несложно, но опять требует применения множества теорем из теории цепных дробей. Поэтому рассмотрим только этапы решения. Сначала требуется доказать, что все решения уравнения Пелля являются числителями и знаменателями подходящих дробей. Вторым этапом находится индекс, при котором модуль правой части уравнения Пелля равен 1. Далее находится окончательный индекс.

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

Индийский (или циклический) метод и английский с появлением теории цепных дробей перестали применять.

99

Метод решения уравнения Пелля, основанный на теории цепных дробей

Теорема 1. Пусть (x,y) – положительное решение уравнения Пелля.

√

Тогдаявляется подходящей дробью           a.

                                                                                                                     √                                √

            Доказательство. Так как x > y > 0 и          a > 1, то x + y       a > 2y.

                                                                                           √             √                        √

             Значит, 1 = x² − ay² = (x − y         a)(x +       a) > (x − y     a) · 2y.

Разделим полученное неравенство на .

Поскольку (x,y) – положительное решение уравнения Пелля, левая часть этого неравенства положительна и дробьнесократима, она яв-

√

ляется подходящей дробью числа         a. Итак, положительные решения

уравнений Пелля следует искать только среди пар, составленных из чис-

√

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

Теорема 2. Пусть n – длина периода последовательности элементов

√

цепной дроби для числа    a. Тогда числитель и знаменатель подходящей

√

дроби числа a являются решением уравнения Пелля тогда и только тогда, когда ее номер имеет вид kn − 1 (т.е. дает при делении на n ¹⁰⁰ остаток n − 1) и нечетен.

√

Так как цепная дробь является периодической, то a = [a₀;a₁,a₂,...] и обозначим длину периода этой непрерывной дроби через S. S может быть чётным или нечётным, если S – чётно, то находят подходящую дробь:

.

В этом случаи наименьшее натуральное решение уравнения Пелля имеет вид:

x = P_S−₁,y = Q_S−₁.

А если же S – нечётное, то x = P_2S−1,y = Q_2S−1. Пример 72. Решить уравнение Пелля

x² − 8y² = 1.

        Решение.                                                                √            √

1) найдём наименьшее (x₀,y₀), так как            8 = 2  2 = [2;1,4,1,4,...]; 2) S = 2;

3) , следовательно, x₀ = 3, y₀ = 1.

Остальные решения найдём по формулам:

101

.

Среди олимпиадных задач для учащихся 11 классов в 2012 году было задание, для решения которого необходимо владеть методами решения уравнения Пелля (олимпиада МГУ).

Пример 73. Найти натуральные x и y, для которых

x² − 2012y² = 1.

Решение. Поскольку 2012 кратно четырём, то данное уравнение равносильно: x² −503z² = 1, где z = 2y. Разделим обе части на z² и выполним перенос вычитаемого вправо:  и извлечём корень:

                                                                        .

Таким образом, корни этого уравнения можно искать среди рациональных приближений корня из 503. Цепная дробь записывается в виде: [22,(2,2,1,21,1,2,2,44)].

Если обрывать цепную дробь на каком-нибудь слагаемом и сворачивать её обратно, будем получать подходящие дроби. Если для прибли-

жения взять дробь.        102 .

То получим первую пару натуральных чисел, удовлетворяющую условию: 24648² − 503 · 1099² = 1. Таким образом, x = 24648, y = 2198. Ответ: x = 24648, y = 2198.

103

Циклический метод решения уравнения Пелля

Циклический метод называют ещё индийским, о котором говорилось выше, рассмотрим этот метод на примере:

x² − 11y² = 1.

Наша цель найти натуральные x и y. В качестве первого приближения рассмотрим равенство 3² − 11 · 1² = −2. Воспользуемся формулой:

(a² − 11ab²)(c² − 11d²) = (ac + 11bd)² − 11(bc + ad)².

И, применив ее к равенствам, 3² − 11 · 1² = −2 и r² − 11 · 1² = s, где r (а тем самым и s) будет определено позже, получим

(3r + 11)² − 11(r + 3)² = −2s.

Пытаясь сделать правую часть (по модулю) как можно меньшей только за счет выбора наименьшего по модулю значения s, мы выбрали бы r = 3, при котором s = −2, и получили бы равенство 20² − 11 · 6² = 4.

Идея циклического метода – выбор такого r, чтобы r+3 делилось на

104

2 и s при этом, было как можно меньше по модулю. (Когда это сделано, обе части уравнения разделяться нацело на 2².)

Обе части разделим на 2² и получим 10² −11·3² = 1. Отсюда следует, что x = 10, y = 3 есть решения нашего уравнения y² − 11x² = 1.

В нашем случаи решение получилось на первом шаге циклического метода. Следовательно, этот метод делается до тех пор пока не получим равенство, в правой части которого будет 1.

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

105

Общее решение уравнения Пелля

Если уравнение Пелля имеет хотя бы одно нетривиальное решение, то, умножая его многократно на себя, можно найти бесконечно много решений. Двигаясь по графику уравнения (рис.2) из точки (1,0) в направлении положительных значений y, находим первое нетривиальное решение. Это решение назовём основным.

                                                Рис.2 – График уравнения x² − 3y² = 1.                                                      106

Теорема 3. Все нетривиальные положительные решения получаются многократным умножением основного решения на себя.

Доказательство. Рассмотрим последовательность

(x₁,y₁),(x₂,y₂),...,(x_n,y_n),...

решений, получаемых из основного решения (x₁,y₁) последовательным умножением на него. Предположим, что на графике уравнения между двумя её членами (x_n,y_n) и (x_n+1,y_n+1) имеется некоторое решение. Умножив его на (x_, −y₁), получим новое решение, лежащее между

(x_n−1,y_n−1) и (x_n,y_n). Действительно, умножение на (x₁,−y₁), является обратной операцией к умножению на (x₁,y₁). Проделав такую операцию n раз, получим решение, лежащее между (1,0) и (x₁,y₁). Это противоречит тому, что (x₁,y₁) – основное решение.

107

2.12 Уравнение Каталана

В 1842 году бельгийский математик Эжен Шарль Каталан сформулировал утверждение: уравнение x^a − y^b = 1, где x,y,a,b > 1 имеет единственное решение в натуральных числах: x = 3, y = 2, a = 2, b = 3 (гипотеза Каталана). Гипотеза Каталана говорит о том, что разность между двумя числами, возведенными в степень, не может быть равной 1, за исключением 3² − 2³. Это утверждение было доказано в 2002 году румынским математиком Преда Михайлеску. Доказательство использует методы из теории круговых полей.

Для решения уравнения x^a −y^b = 1, где x,y,a,b > 1 можно рассмотреть случаи:

1) x – четное число, y – нечетное число; 2) x – нечетное число, y – четное число.

Каждый из вариантов распадается еще на два случая:

1) x > y, a < b; 2) x < y, a > b.

Кроме этого, требуется перебрать комбинации a, b – четные (нечётные) числа. Всего 16 вариантов перебора.

108

2.13 Уравнение Маркова

Уравнение вида x² + y² + z² = 3xyz называют уравнением Маркова.

В 1879 году в Петербургском университете молодой человек 23-х лет защитил магистерскую диссертацию под названием «О бинарных квадратичных формах положительного определителя». В ней решались труднейшие вопросы теории чисел, и она определила новое направление в этой теории. Её автором был будущий знаменитый академик Андрей Андреевич Марков (1856-1922).

В основу диссертации были положены две его статьи, опубликованные в Германии в 1879 и 1880 годах в одном из наиболее известных в мире математических журналов – «Mathematische Annalen». В 1913 году крупный немецкий математик Георг Фробениус (1849-1917) опубликовал мемуар под названием «О числах Маркова». В предисловии к нему он написал, что вопреки тому, что исследования А.А. Маркова являются «чрезвычайно замечательными и важными», они, по-видимому, остались мало известными.

В своих построениях А.А. Марков неожиданно пришёл к вспомогательному диофантову уравнению (называемому теперь его именем),

имеющему вид:                                                                                                                                      109

x² + y² + z² = 3xyz.

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

Упорядоченная тройка целых чисел (a,b,c) называется решением диофантова уравнения с переменными x, y, z, если это уравнение при x = a, y = b, z = c превращается в верное числовое равенство. Числа a,b,c решения (a,b,c) будем называть координатами решения. Для уравнения Маркова мы условимся рассматривать только те решения, у которых нет нулевых координат, иными словами, тройку (0,0,0) мы будем исключать из решений (легко видеть, что если равна нулю одна из координат решения уравнения x² + y² + z² = 3xyz, то и остальные координаты решения равны нулю).

Левая часть уравнения Маркова положительна для любого решения (a,b,c), поэтому либо все a,b,c положительны, либо два из них отрицательны. В последнем случае переход от (a,b,c) к (|a|,|b|,|c|) приводит к решению уравнения Маркова с положительными координатами. Обратно, если все координаты решения (a,b,c) положительны, то, изменив знак у каких-либо двух координат, мы снова получим решение. Поэтому в дальнейшем без ограничения общности мы будем рассматривать только решения (a,b,c) с положительными координатами.

Из симметричности уравнения Маркова следует, что если (a,b,c) – решение уравнения Маркова, то решениями будут:

110

(a,b,c),(c,a,b),(b,c,a),

(b,a,c),(a,c,b),(c,b,a),

то есть вместе с (a,b,c) решениями будут все тройки, получаемые различными перестановками координат данного решения.

Ввиду этого мы можем условиться все шесть решений уравнения Маркова, получающихся друг из друга перестановками, считать одним решением, то есть считать, что для решения существенны лишь значения координат, а не их порядок. Уравнение Маркова имеет очевидное решение (1,1,1). Сейчас мы выясним, как, зная какое-либо решение, можно находить другие решения. Если (a,b,c) – решение уравнения Маркова, то можно утверждать, что a есть корень квадратного уравнения

Ψ_a(x) = x² + b² + c² − 3bcx = 0.

Но по теореме Виета это уравнение будет иметь еще одни корень , такой, что

0

a + a = 3bc, aa⁰ = b² + c².

Очевидно, также является решением уравнения Маркова. Оно называется соседним решением по координате a. Очевидно,

                    ⁰                                                                                                                                                                                                                                                                                                               111

если (a ,b,c) – соседнее решение для (a,b,c), то (a,b,c) является сосед-

0 ним по координате a решением для.

Аналогично вводятся решения, соседние по координате b и по координате c.

Найдем решение, соседнее по координате 1 решению (1,1,1). Для этого нужно решить квадратное уравнение

x² + 1² + 1² − 3 · 1 · 1 · x = 0.

Кроме корня x = 1, это уравнение имеет корень x = 2. Таким образом, получено еще одно решение (2,1,1). В дальнейшем решения (1,1,1) и (2,1,1) будут играть существенную роль. Их называют, следуя Маркову, сингулярными.

Сингулярные решения выделяются из множества всех решений следующим свойством.

Свойство 1. Если решения (a,b,c) уравнения Маркова две из координат равны, то в этом и только этом случае решение является сингулярным.

Первое сингулярное решение (1,1,1) имеет только одно соседнее решение. Второе сингулярное решение имеет два соседних: одно из них – (1,1,1), другое (соседнее по координате 1), получается из уравнения 2² + y² + 1² = 3 · 2 · y · 1 и имеет вид (2,5,1). В свою очередь, решение (2,5,1) имеет три соседних: одно, естественно (2,1,1) и два новых – (13,5,1) и (2,5,29). Вообще, каждое несингулярное решение (a,b,c)

порождает три соседних                                                                                                                     ¹¹²

,

              0                                                   0                                                    0

где a = 3bc − a, b = 3ac − b, c = 3ab − c.

Свойство 2. Если решение (a,b,c) несингулярно, то одно из его соседних решений имеет меньшую максимальную координату, а два других — большую.

Теорема Маркова. Любое решение уравнения Маркова соединяется цепочкой соседних решений с сингулярным решением (1,1,1).

Доказательство. Пусть (a,b,c) – решение уравнения Маркова, отличное от сингулярного. Тогда у него есть соседнее решение (a₁,b₁,c₁) с меньшей максимальной координатой (свойство 2). Если это решение также несингулярно, то оно порождает решение (a₂,b₂,c₂) с еще меньшей максимальной координатой, и так далее. Так как из натуральных чисел нельзя образовать бесконечную убывающую последовательность, то этот процесс должен закончиться, и закончится он тогда, когда мы придем к некоторому решению (a_n,b_n,c_n), у которого есть равные координаты, то есть (свойство 1) к сингулярному. Если оно (1,1,1), то теорема доказана, если же это решение (2,1,1), то остается вспомнить, что соседним решением для (2,1,1) по координате 2 будет (1,1,1).

Теорема доказана.

Из теоремы Маркова следует, что, отправляясь от сингулярного решения (1,1,1), и последовательно переходя к соседним решениям с большим максимумом координат, мы получим все решения уравнения Мар- 113 кова. При этом получается такая таблица – родословное дерево уравнения Маркова (рис. 3).

Рис. 3 – Родословное дерево уравнения Маркова.

Эта таблица позволяет для данного N(≥ 1) конечным числом дей-

114 ствий найти все решения уравнения Маркова, координаты которых не превосходят N.

Свойство 3. У каждого решения уравнения Маркова координаты попарно взаимно просты.

Поставим следующий вопрос: «Если сумма квадратов трех натуральных чисел делится на их произведение, то каким может быть частное»?

Этот вопрос равносилен следующему: при каких натуральных k диофантово уравнение

X² + Y ² + Z² = kXY Z

имеет ненулевое решение? При k = 3 это уравнение совпадает с уравнением Маркова. Легко видеть, что при k = 1 уравнение X² + Y ² + Z² = = kXY Z имеет решения, например (3,3,3). Проанализировав уравнение

X²+Y ²+Z² = kXY Z, приходим к результату: уравнение X²+Y ²+Z² = = kXY Z имеет решения только при k = 3 и k = 1. Этот результат также может быть получен элементарными средствами.

Свойство 4. Пусть A, B, C – натуральные числа. Тогда остаток от деления числа A² + B² + C² на 3 равен количеству неделящихся на 3 чисел среди A, B, C, если их меньше трех, и равен нулю в противном случае.

Свойство 5. Все решения (A,B,C) уравнения X² + Y ² + Z² = XY Z получаются по формулам A = 3a, B = 3b, C = 3c, где (a,b,c) – произвольное решение уравнения Маркова.

Свойство 6. Уравнение X² +Y ² +Z² = kXY Z не имеет решений при 115 k = 2.

Теорема 1. Уравнение X²+Y ²+Z² = kXY Z имеет ненулевое решение только при k = 1 и k = 3.

Доказательство.

При k = 1 решения находятся в соответствии с свойством 5. При k = 2 уравнение X² + Y ² + Z² = kXY Z не имеет решений в силу свойства 6. Рассмотрим k > 3.

Допустим, что при некотором k > 3 уравнение X²+Y ²+Z² = kXY Z имеет решение (a,b,c). Покажем, что координаты a,b,c этого решения попарно различны. Пусть, например, b = c; тогда a² = kab² − 2b² = = (ka − 2)b², так что a = bd, где d – целое. Отсюда b²d² = (kbd − 2)b², d² = kbd − 2, 2 = d(kb − d). Таким образом, 2 делится на d или d − 1, или 2. В обоих случаях kb − 3, что противоречит условию k > 3.

У любого решения уравнения X² +Y ² +Z² = kXY Z при k > 3 координаты попарно различны. Без ограничения общности можно считать, что a > b > c. Для решения (a,b,c) с помощью квадратного трехчлена

Ψ_a(x) = x² + b² + c² − kxbc

образуем соседнее по координате a решение . Так как

Ψ_a(b) = 2b² + c² − kb²c < 3b² − kb²c ≤ 3b² − kb² < 0,

0 мы видим, что b лежит между корнями a и a многочлена Ψ_a(x), то

0        0 есть a > b > a . Поэтому у решения (a ,b,c) максимальная координата

116 меньше максимальной координаты решения (a,b,c). Итак, по каждому решению (a,b,c) можно построить решение (a₁,b₁,c₁) с меньшей максимальной координатой. Это построение можно повторить, получив решение (a₂,b₂,c₂) с еще меньшей максимальной координатой. Так как у

каждого решения координаты попарно различны, этот процесс можно продолжать неограниченно и получить бесконечную последовательность решений уравнения X²+Y ²+Z² = kXY Z со все меньшими и меньшими максимальными координатами. Но это невозможно, так как координаты – натуральные числа.

Теорема доказана.

Следствие. Для любого решения (a,b,c) уравнения Маркова числа a, b, c попарно взаимно просты.

Доказательство. Если a и b имеют общий делитель d (> 1), то в силу уравнения Маркова, число d будет делителем и числа c. Следовательно, найдутся натуральные X, Y , Z такие, что a = dX, b = dY , c = dZ, и в силу уравнения Маркова будем иметь

X² + Y ² + Z² = 3dXY Z,

а это противоречит только что доказанной теореме.

Обобщённым уравнением Маркова называют уравнения вида:

,

где x_i – целые, n ≥ 3, k – натуральное число.                                                                             ¹¹⁷

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

Действительно, если хотя бы одно из чисел x_i равно 0, то легко видеть,

что и остальные также равны нулю. Если же среди них имеются отрицательные, то переход к числам |x_i| даёт решение в натуральных числах.

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

Для каждого решения (x₁,x₂,...,x_m,...,x_n) в натуральных числах уравнения, по каждой его координате x_m (1 ≤ m ≤ n) можно построить соседнее решение : подставив в равенство, набор

(x₁,x₂,...,x_m,...,x_n), решить возникающее при этом квадратное уравнение

,

у которого кроме корня x = x_m должен быть второй корень . При этом согласно формулам Виета:

,

                                                                              118

При этом если x₁ ≥ x₂ ≥ ··· ≥ x_n, m ≥ 2, то

.

Таким образом, из каждого решения можно получить новые, с большей максимальной координатой, и лишь по одной координате – максимальной – переходить к соседнему, «меньшему» по максимальной координате решению. Такое движение вверх по дереву решений к меньшим по максимальной координатам решениям не может продолжаться бесконечно (мы рассматриваем решения в натуральных числах), в конце концов будет достигнуто коренное решение x₁ ≥ x₂ ≥ ··· ≥ x_n, для которого , и в дальнейшем подъём невозможен.

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

Пример 74. Докажите, что уравнение Маркова имеет бесконечно много решений.

Решение. Предположим сначала, среди m, n и p есть равные, например, n = p. Тогда m² + 2n² = 3mn², т.е. . Следовательно, m = dn, где d – целое число. При этом d² + 2 = 3nd, т.е. d(3n − d) = 2. Поэтому d = 1 или 2. В обоих случаях n = 1. В результате получаем решения (1,1,1) и (2,1,1). Их назовем особыми.

119 Возьмем теперь не особое решение (m,n,p), для которого числа m, n, p попарно различны, и рассмотрим квадратный трехчлен

f(x) = x² − 3xnp + n² + p².

Ясно, что f(m) = 0, т.е. один корень квадратного трехчлена f равен

                                                                   0                                                                                                                                                  0

m. Второй его корень m можно найти по теореме Виета: m = 3np−m. Ясно, что при этом  – решение уравнения m² +n² +p² = 3mnp.

Покажем, что наибольшее из числе n и p заключено между .

Пусть для определенности n > p. Тогда

.

Это как раз и значит, что n заключено между m и m

Аналогичным образом по решению (m,n,p) можно построить решения .

Предположим, что m – наибольшее из чисел m, n, p. Тогда m >

0          0 max(n,p) > m ,n < m = max(m,p) < n .

Таким образом, при переходе от решения (m,n,p) к решению наибольшее из трех чисел уменьшается, а при переходе к решениям

              0                                                      0

(m,n ,p) и (m,n,p ) увеличивется.

Если начать с решения (1,1,1), то получим следующее дерево решений (рис. 4).

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

0 решения (m,n,p), где m > max?(n,p), к решению (m ,n,p).

Рис. 4 – Дерево Маркова.

Пример 75. Докажите, что если m, n, p – решение уравнения Мар-

кова, то числа m, n и p взаимно просты.                                                                                      ¹²¹

Решение. Предположим, чтоm = dm₁, n = dn₁ и p = dp₁, где

d > 1. Тогда . Но согласно теореме 1 уравнение x² + y² + z² = kxyz не имеет решений в натуральных числах при k > 3.

Пример 76. Докажите, что все решения уравнения m² + n² + p² = mnp в натуральных числах имеют вид 3m₁, 3n₁, 3p₁, где m₁, n₁, p₁ – решение уравнения Маркова.

Решение. Достаточно доказать, что если m² + n² + p² = mnp, то числа m, n и p делятся на 3. Если целое число не делится на 3, то его квадрат при делении на 3 даёт остаток 1. Поэтому если m² + n² + p² не делится на 3, то среди чисел m, n и p есть как делящиеся на 3, так и не делящиеся на 3. Но тогда m² + n² + p² = mnp делится на 3, чего не может быть. Значит, m² + n² + p² делится на 3, причём числа m, n и p одновременно либо все делятся на 3, либо все не делятся на 3. Второй вариант невозможен, потому что mnp = m² + n² + p² делится на 3.

122

2.14.Методы решения диофантовых уравнений второй степени и выше

Рассмотрим уравнение второй степени с тремя неизвестными:

x2 + y2 = z2

Геометрически решение этого уравнения в целых числах можно истолковать как нахождение всех пифагоровых треугольников, то есть прямоугольных треугольников, у которых и катеты x, y и гипотенуза z выражаются целыми числами.

Обозначим через d наибольший общий делитель чисел x и y: d = (x,y). Тогда x = x₁d, y = y₁d, и уравнение x² + y² = z² примет вид:

.

Отсюда следует, что z² делится на d² и, значит, z кратно d: z = z₁d. Теперь уравнение x² + y² = z² можно записать в виде:

;

сокращая на d², получим                                                                                                                    123

.

Мы пришли к уравнению того же вида, что и исходное, причем теперь величины x₁ и y₁ не имеют общих делителей, кроме 1. Таким образом, при решении уравнения x²+y² = z² можно ограничиться случаем, когда x и y взаимно просты. Итак, пусть (x,y) = 1. Тогда хотя бы одна из величин x и y (например, x) будет нечетной. Перенося y² в правую часть уравнения x² + y² = z², получим

x² = z² − y²; x² = (z + y)(z − y).

Обозначим через d₁ общий наибольший делитель выражений z + y и z − y.

Тогда z + y = ad₁,z − y = bd₁,

где a и b взаимно просты. Подставляя в x² = (z + y)(z − y) значения z + y и z − y, получим.

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

a = u²,b = v².

         Но тогда                                                                                                                                               124

и x = uvd₁.

Найдем теперь y и z из равенств x² = (z + y)(z − y). Сложение этих равенств дает:

;

Вычитая второе из равенств z + y = ad₁,z − y = bd₁ из первого, получим

;

В силу нечетности x из x = uvd₁ получаем, что u, v и d₁ также нечетны. Более того, d₁ = 1, так как иначе из равенств x = uvd₁ и  следовало бы, что величины x и y имеют общий делитель

d₁ 6= 1, что противоречит предположению об их взаимной простоте. Числа u и v связаны с взаимно простыми числами a и b равенствами

a = u²,b = v²

и в силу этого сами взаимно просты; u < v, так b < a, что ясно из равенств z + y = ad₁,z − y = bd₁.

Подставляя в равенства значение         125 d₁ = 1, получим формулы:

дающие при нечетных взаимно простых u и v (v < u) все свободные от общих делителей тройки целых положительных чисел x, y, z, удовлетворяющие уравнению x² + y² = z². Простой подстановкой x, y и z в уравнение x² + y² = z² легко проверить, что при любых u и v числа  удовлетворяют этому уравнению.

Для начальных значений u и v формулы,

 приводят к следующим часто встречающимся равенствам:

3² + 4² = 5²(v = 1,u = 3),

5² + 12² = 13²(v = 1,u = 5), 15² + 8² = 17²(v = 3,u = 5).

Как уже было сказано, формулы дают только те решения уравнения

x² + y² = z²,

в которых числа x, y и z не имеют общих делителей. Все остальные целые положительные решения – этого уравнения получаются умноже-

нием решений, содержащихся в формулах,

126 , на произвольный общий множитель d.

Тем же путем, каким мы получили все решения уравнения x² +y² = = z², могут быть получены и все решения других уравнений того же типа.

Пример 77. Докажите, что если a, b, c – пифагорова тройка, то одно из этих чисел делится на 3, другое (или то же самое) делится на 4, третье – на 5.

Решение. Остаток от деления квадрата целого числа на 3 и на 4 равен 0 или 1, а остаток от деления на 5 равен 0, 1 или 4. Используя только остатки 1 и 4, нельзя добиться выполнения равенства a² + b² = c². В случае делимости на 3 и на 5 – это завершает доказательство. В случае делимости на 4 мы получаем, что либо все три числа a, b, c чётны, либо одно из чисел a и b чётно, а другое нечётно. Первый случай можно не разбирать, поскольку доказательство достаточно провести для примитивных пифагоровых троек. Таким образом, остаётся доказать, что если для целых чисел a₁, b₁, c₁ выполняется равенство

(2a₁)² + (2b₁ + 1)² = (2c₁ + 1)²,

то число a₁ чётно. Последнее равенство можно переписать в виде

.

Числа c₁(c₁ + 1) и b₁(b₁ + 1) чётны, поэтому число a₁ тоже чётно.

127

Пример 78. Пусть a, b, c – примитивная пифагорова тройка. Докажите, что одно из чисел a или b чётно, а другое нечётно.

Решение. Числа a и b не могут быть оба чётными, потому что иначе число c тоже было бы чётным. Числа a и b не могут быть оба нечётными, потому что иначе число a² + b² делилось бы на 2, но не делилось бы на

4.

Пример 79. Пусть a, b, c – примитивная пифагорова тройка, причём число a чётно. Докажите, что существуют взаимно простые числа m и n, для которых

a = 2mn,b = m² − n²,c = m² + n².

Решение. Числа  взаимно простые, поэтому из равенства  следует, что , где m и n – взаимно

простые числа. При этом c² = m² + n² и b² = m² − n².

Пример 80. Пусть a, b, c – примитивная пифагорова тройка. Докажите, что ab делится на 12.

Решение. Нужно доказать, что для любых взаимно простых натуральных чисел m и n число mn(m + n)(m − n) делится на 6. Если m и n нечетны, то m + n четно. Если m и n не делятся на 3, то либо числа 128 m и n дают одинаковые остатки при делении на 3 (тогда m−n делится на 3), либо одно из них при делении на 3 дает остаток 1, а другое дает остаток 2 (тогда m + n) делится на 3).

Пример 81. Пусть a, b, c – примитивная пифагорова тройка. Докажите, что число  (площадь прямоугольного треугольника с катетами a и b) не может быть полным квадратом.

Решение. Предположим, что существуют взаимно простые натуральные числа m и n, для которых mn(m + n)(m − n) = s², где s – натуральные число. Будем считать, что s – наименьшее из всех чисел, для которых имеет место равенство такого вида. Числа m, n, m + n, m − n попарно взаимно просты, поэтому m = x²,

n = y²,m + n = z²,m − n = t²,

где x, y, x и t – натуральные числа. Числа m и n разной четности, поэтому числа z и t нечетные. Положим . Тогда

. Таким образом, для

числа тоже имеет место равенство указанного вида. Поэтому y² ≥ 4s², т.е. y² ≥ 4x²y²(x² − y²)(x² + y²). Получено противоречие.

Пример 82. Найти все решения уравнения x² + 2y² = z² в целых положительных попарно взаимно простых числах x, y, z.

Решение. Заметим, что если x, y, z есть решение данного уравнения и x, y, z не имеют общего делителя, отличного от 1, то они и попарно взаимно просты. Действительно, если x и y кратны простому числу 129 p > 2, то из равенства

следует, так как его левая часть – целое число, что z кратно p. То же самое будет, если x и z или y и z делятся на p.

Заметим, что x должно быть числом нечетным для того, чтобы общий наибольший делитель x, y, z был равен 1. Действительно, если x четно, то левая часть исходного уравнения будет четным числом и, значит, z также будет четным. Но x² и z² будут тогда кратны 4. Отсюда следует, что 2y² должно делиться на 4, другими словами, что y тоже должно быть четным числом. Значит, если x четно, то все числа x, y, z должны быть четными. Итак, в решении без общего отличного от 1 делителя x должно быть нечетным. Отсюда уже следует, что и z должно быть тоже нечетным. Перенося x² в правую часть, мы получаем:

2y² = z² − x² = (z + x)(z − x).

Но z + y и z − y имеют общим наибольшим делителем 2. Действительно, пусть их общий наибольший делитель будет d. Тогда

z + y = kd,z − y = ld,

где k и l - целые числа. Складывая и вычитая эти равенства, мы будем

иметь:                                                                                                                                                          130

2z = d(k + l),2x = d(k − l).

Но z и x нечетны и взаимно просты. Поэтому общий наибольший делитель 2x и 2z будет 2. Отсюда следует, что d = 2.

Итак, или, или нечетно. Поэтому или числавзаимно просты, или взаимно просты числа .

В первом случае из равенства  следует, что z+x = n², z − x = m², а во втором случае из равенства  следует z + x = 2m², z + x = n², где n и m целые, m – нечетное число и n > 0, m > 0. Решая эти две системы уравнений относительно x и z и находя y, мы получаем или

,

или

,

где m нечетно.      131 Объединяя эти две формы представления решения x, y, z мы получаем общую формулу:

,

где m нечетно. Но для того чтобы z и x были целыми числами, необходимо, чтобы n было четным. Полагая n = 2b и m = a, мы получим окончательно общие формулы, дающие все решения данного в условии уравнения в целых положительных без общего делителя, большего 1, числах x, y, z:

x = ±(a² − 2b²), y = 2ab, z = a² + 2b²,

где a и b положительны, взаимно просты и a нечетно. При этих условиях величины a и b выбираются произвольно, но так, чтобы x было положительно. Формулы x = ±(a² −2b²), y = 2ab, z = a² +2b² действительно дают все решения в целых положительных и взаимно простых числах x, y, z так как, с одной стороны, мы доказали, что x, y, z в этом случае должны представляться по формулам x = ±(a² − 2b²), y = 2ab, 132 z = a² + 2b², а с другой стороны, если мы зададим числа a и b, удовлетворяющие нашим условиям, то x, y, z будут действительно взаимно просты и будут решением исходного уравнения.

Пример 83. (Московские математические олимпиады). Решить в целых числах уравнение

6x² + 5y² = 74.

Решение. Перепишем данное уравнение так: 6x² − 24 = 50 − 5y², т.е. 6(x² − 4) = 5(10 − y²), откуда имеем x² − 4 = 5u, 10 − y² = 6v и, следовательно, v = u.

Итак, x² = 4+5u, т.е. 4+5u ≥ 0, откуда; аналогично 10−y² = = 6u, т.е. 10 − y² ≥ 0, откуда , значит u = 0 или u = 1.

При u = v = 0 получим 10 = y², где y – целое, что неверно.

Пусть u = v = 1, тогда x² = 9, y² = 4.

Ответ: (3;2), (3;−2), (−3;2), (−3;−2).

Пример 84. (Петербургские математические олимпиады). Решить в целых числах уравнение

19x² + 28y² = 729.

Решение. Так как (18x² + 27y²) + (x² + y²) = 729, то x² + y² делится на 3, поэтому x = 3u, y = 3v и 19u² + 28v² = 81.

Повторяя рассуждения, получим u = 3t, v = 3s и 19t² + 28s² = 9.

Последнее уравнение, очевидно, не имеет решений в целых числах, а 133 значит, и исходное уравнение решений не имеет.

Ответ: решений нет.

Как известно, уравнение второй степени с двумя неизвестными

ax + bxy + cy² + fx + hy + d,

где a, b, c, f, h, d ∈ Z, может не иметь решений в целых числах, может иметь их только конечное число и, наконец, может иметь бесконечное множество таких решений, причём в последнем случае пары чисел, которые могут быть решениями уравнения, встречаются значительно реже, чем пары целых чисел, которые могут быть решениями уравнения первой степени. Это обстоятельство не случайно. Оказывается, что уравнения с двумя неизвестными степени выше второй, вообще говоря, могут иметь только конечное число решений в целых числах. Исключения из этого правила крайне редки. А. Туэ доказал, что уравнение

a₀xⁿ + a₁x⁽n − 1)y + a₂x⁽n − 2)y² + · + a_nyⁿ = c,

где n ∈ Z, n > 2, a₀, a₁,...,a_n ∈ Z имеет только конечное число решений в целых числах, за исключением, может быть, случаев, когда левая однородная часть этого уравнения есть степень однородного дву-

члена первой степени или трёхчлена второй степени. Метод А. Туэ даёт

134 возможность найти границу для числа решений уравнения, правда, достаточно грубую. Для отдельных классов уравнений эта граница может быть значительно уточнена. Например, Б. Н. Делоне показал, что уравнение ax³ +y³ = 1 при a целом может иметь, кроме тривиального x = 0,

y = 1, не более одного решения в целых числах. Кроме того, он показал, что уравнение ax³ + bx²y + cxy² + dy³ = 1, a,b,c,d ∈ Z, может иметь не более пяти решений в целых числах. К. Зигель доказал, что уравнение P(x,y) = 0, где P(x,y) – неприводимый многочлен выше чем второй степени относительно x и y, может иметь бесконечное множество решений в целых числах только тогда, когда существуют числа

a_n,a_n−₁,...,a₀,a₋₁,...,a_−n

и

b_n,b_n−₁,...,b₀,b₋₁,...,b_−n

такие, что при подстановке вместо и в данное уравнение

,

получится тождество P(x,y) = 0 относительно t. Здесь n – некоторое целое число.

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

135 с двумя неизвестными на примерах.

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

3x² + 4xy − 7y² = 13.

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

3x² + 4xy − 7y² = (3x + 7y)(x − y).

Имеем (3x+7y)(x−y) = 13. Представим число 13 в виде произведения целых чисел с учетом порядка 13 = 1 · 13 = 13 · 1 = (−1) · (−13) =

(−13) · (−1), тогда получим:

= 13,

= 1;

1,

13;

= 1,

= 13;

,

136

Системы вторая и третья не имеют целочисленных решений.

Ответ: (2;1), (−2;−1).

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

x² − 4x − y² + 2y + 6 = 0.

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

(x² − 4x + 4) − 4 − (y² − 2y + 1) + 1 + 6 = 0 ⇔ (x − 2)² − (y − 1)² = −3

(x − y − 1)(x + y − 3) = −3.

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

3;

1,

3 = 3;

1;

,

137

Решая данные системы, получаем ответ.

Ответ: (1;−1), (3;3), (3;−1), (1;3).

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

x² + xy − 2y² − x + y = 3.

Решение. Проведем равносильные преобразования

x² + xy − 2y² − x + y = 3 ⇔ (x − y)² + 2xy − y² + xy − 2y² − x + y = 3,

(x − y)² + 3xy − 2y² − (x − y) = 3 ⇔ (x − y)² + 3y(x − y) − (x − y) = 3, (x − y)(2y + x − 1) = 3.

Данное уравнение равносильно совокупности четырех систем:

1 = 3;

1 = 1;

3;

138

.

Системы вторая и третья не имеют целочисленных решений.

Ответ: (2;1),(−2;1).

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

y − x − xy = 2.

Решение. Проведем над данным уравнением цепочку равносильных преобразований:

y − x − xy = 2 ⇒ (y + 1) − x(1 + y) − 1 = 2 ⇔ (y + 1)(1 − x) = 3.

Поскольку число 3 можно представить в виде произведения двух целых чисел с учетом порядка четырьмя способами 3 = (−1) · (−3) = = (−3) · (−1) = 1 · 3 = 3 · 1, то получим четыре системы:

2,

= 0;

.

Ответ: (0;2), (−2;0), (2;−4), (4;−2).

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

2

2x + xy = x + 7.

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

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

Выразим y через. Поскольку x и y целые числа, то дробь  должна быть целым числом. Следовательно, имеем:

1,

4;

,

Ответ: (−1;−4, (−7;14), (7;−12), (1;6).

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

x² − 3y = 17.

Решение. Очевидно, что не делится на 3, так как в противном случае (x² − 3y) делится на 3, что невозможно, так как 17 не делится на 3. Поэтому, пусть x = 3k±1, k ∈ Z. Тогда данное уравнение преобразуется к виду

9k2 ± 6k + 1 − 3y = 17 ⇔ 3(3k2 ± 2k − y) = 16,

140 что невозможно, так как 16 не делится на 3.

Ответ: решений нет.

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

x² + xy − y² = x²y².

Решение. Проведем рациональное преобразование

(y² − 1)x² − yx + y² = 0.

Если y² − 1 6= 0, то есть y 6= ±1, то решим квадратное уравнение относительно :

.

Если y 6= 0, то должно иметь место неравенство 5 − 4y² = a², где – некоторое целое число, то есть 4y² + a² = 5. Это возможно в случае, когда y = ±1, чего не может быть по предположению. Если y = 0, то x = 0. Если y² −1 = 0, то есть y = ±1, то при y = 1 имеем x−1 = 0, то есть x = 1; при y = −1 имеем −x − 1 = 0, то есть x = −1.

Ответ: (0;0), (1;1), (−1;−1).

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

                                                                                  3x² − 4y = 13.                                                                               141

Решение. Перепишем данное уравнение в виде

3x² − 23 − 4y² = 10 ⇔ 3(x² − 1) − 4y² = 10 ⇔

⇔ 3(x + 1)(x − 1) − 4y² = 10.

Так как 3x² − 4y = 13 – нечётное число – то ясно, что х может быть только нечётным числом. Следовательно, (x + 1)(x − 1) – произведение двух последовательных чётных чисел, а поэтому это произведение кратно 4.

Таким образом, левая часть уравнения 3(x + 1)(x − 1) − 4y² = 10 кратна 4. Но так как число 10 не кратно четырем, то равенство 3(x+1)(x−1)−4y² = 10 не выполняется ни при каких целых значениях x и y, то есть данное уравнение не имеет решений в целых числах. Ответ: решений нет.

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

x + y + z = xyz (0 ≤ x ≤ y ≤ z).

Решение. Так как y ≥ x, то можем представить y в виде y = x + a, где a ≥ 0, a ∈ Z, аналогично z ≥ y, тогда z = y + b, где b ≥ 0, b ∈ Z ⇒ z = x + (a + b). Тогда исходное уравнение примет вид x + (x + a) + (x + (a + b)) = x(x + a)(x + (a + b)) ⇔

⇔ 3x + (2a + b)x3 · (2a + b)x2 · (a2 + ab)x = 0. 142 Если x = 0, тогда получим 2a + b = 0 ⇔ a = 0, b = 0 ⇒ y = z = 0.

Если.

При x > 1 получим, что x³ > 3x, x²(2a + b) ≥ 2a + b, то есть x³ +(2a+b)x² +(a² +ab)x > 3x+(2a+b). Значит, при x > 1 уравнение решений не имеет.

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

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

3(u − 3)² + 6v² + 2w² + 3v²w² = 33.

Решение. Пусть (u₀,v₀,w₀) – тройка чисел, удовлетворяющих условию задачи, тогда

.

Откуда следует, в частности, что 3(u₀−3)² ≤ 33, то есть (u₀−3)² ≤ 11. Поскольку (u₀−3)² является квадратом целого числа (u₀−3), то (u₀−3)² равно либо 0, либо 1, либо 4, либо 9. Перепишем

в виде

.

              Если (u−3)² = 0, то . Так как                     ¹⁴³

целые числа, большие 1, а 37 – простое число, то последнее равенство выполняться не может, значит (u₀ − 3)² 6= 0.

Если (u₀ − 3)² = 1, то .

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

,

+ 2 = 5;

либо

.

Вторая система не имеет решений, а решением первой являются пары w₀ = 0, v₀ = ±1.

Ответ: (6;−1;0), (6;1;0), (0;−1;0), (0;1;0). Пример 95. Доказать, что уравнение

x³ = 2 + 3y²

не имеет решений в целых числах.

Решение. Рассмотрим это уравнение по модулю 9, то есть с точностью до слагаемых, кратных девяти. Напомним, два целых числа a и b

называются сравнимыми по модулю k, если разность a−b делится на k.

144 Поскольку каждое целое число x имеет вид 3n, 3n−1 или 3n+1, где n – целое, то (3n)³ = 27n³ делится на 9, а (3n±1)³ = 27n³±27n²+9n±1 дает при делении на 9 в остатке 1 или 8.

Аналогично, 3y² дает при делении на 9 остаток 0 или 3.

Значит, правая часть исходного уравнения по модулю 9 может равняться 2 или 5, а левая 0, 1 или 8, поэтому исходное уравнение не имеет решений ни при каких целых x и y, ч. т. д.

Самым трудным местом в таком решении является выбор модуля, то есть того числа, остатки от деления на которое рассматриваются. То, что a и b сравнимы по модулю k, записывают следующим образом: a(mod k). Это означает, что a − b делится на k , где a,b,k ∈ Z, k 6= 0. Правила операций над сравнениями можно записать так:

,

то a+c ≡ b+d(mod k), ac ≡ bd(mod k). Заметим, что если ac ≡ b(mod k) и c взаимно просто с k, то a ≡ b(modk). Суть метода перехода к уравнениям по простому модулю в следующем. Рассматриваем какое-нибудь диофантово уравнение. Предположим, что оно имеет решения, и рассмотрим вместо входящих в решение чисел их классы вычетов по mod p, где p – простое число. Полученный набор будет являться решением приведенного уравнения – уравнения, получающегося из данного заменой

каждого коэффициента на его класс вычетов по mod p. Поэтому необхо-

145 димым условием существования решения у диофантова уравнения является существование решения приведенного уравнения по mod p при всех p. Классом вычетов r по модулю p называется все числа, сравнимые с числом r по модулю p, r = (r + kp|k ∈ Z). Все множество Z целых

чисел распадается на p классов вычетов по модулю p. Множество всех

этих классов обозначают через F_p: F_p = (0,1,...,p − 1). Множество F_p конечно, и установить, имеет ли приведенное уравнение решение, можно простым перебором.

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

35x⁴ + 24y³ = 100000.

Решение. Приведем это уравнение по mod 3:

35 ≡ 2(mod 3),

24 ≡ 0(mod 3),

100000 ≡ 1(mod 3).

Исходное уравнение примет вид по mod 3: 2x⁴ = 1.

Выражение 2x⁴ при x ∈ F₃ принимает значения 0 и 2. Поэтому у уравнения 2x⁴ = 1 нет решений, значит, нет решений у исходного уравнения.

Характерной особенностью рассуждений при решении уравнений в

целых числах является следующий подход: возможные значения реше-

146 ния, за исключением конечного числа, отбрасываются при помощи когото заключения, а оставшиеся проверяются перебором.

2.15 Некоторые приложения теории диофантовых уравнений

Утверждение. Пусть в уравнении kx + my = n k,m,n ∈ Z. Если числа k,m,n взаимно простые, то есть НОД(k,m) = 1, то уравнение kx + my = n имеет целочисленные решения.

Пусть (x₀,y₀) – одно какое – либо решение уравнения kx + my = n, его находят подбором. Поэтому справедливо тождество kx₀ + my₀ = n. Покажем, как найти все решения уравнения kx + my = n. Вычитая из уравнения kx + my = n тождество kx₀ + my₀ = n, получаем:

,

Поскольку x₀ – целое число, то для целочисленности x необходимо и достаточно, чтобы целочисленно было . Но НОД(k,m) = 1, то есть m не делится на k. Значит,  должно быть целым числом, то есть , откуда y = y₀ + kt.

Тогда x = x₀ − mt.

В итоге имеем общее решение уравнения kx + my = n:

147

.

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

3n − 4m = 2.

Решение. Поскольку НОД(3,4) = 1, НОД(3,4,2) = 1, то данное уравнение, согласно приведенному выше утверждению, имеет решение. Очевидно, что n = 2, m = 1 – решение данного уравнения, то есть имеем тождество 3·2−4·1 = 2. Вычитая их исходного уравнения последнее тождество, получаем 3(n−2)−4(m−1) = 0, откуда следует .

Для целочисленности m необходимо и достаточно, чтобы , то есть n − 2 = 4t, n = 2 + 4t, t ∈ Z, и тогда m = 1 + 3t, t ∈ Z. В итоге имеем: m = 1 + 3t, n = 2 + 4t, t ∈ Z. Ответ: (2 + 4t;1 + 3t), t ∈ Z. Пример 98. Решить уравнение

cos3x + cos4x = 2.

Решение. Поскольку cos3x ≤ 1 и cos4x ≤ 1, то данное уравнение справедливо при выполнении системы уравнений

     148 Находим пересечение серий решений последней системы:

Уравнение 4k = 3n имеет очевидное решение: k = 3t, n = 4t, t ∈ Z, и общее решение системы, а вместе с ним и исходного уравнения.

Есть.

Ответ: 2πt, t ∈ Z.

Пример 98. Решить уравнение

√ sinx + sin           2x = 2.

                                                                                                     √                                                            √

Решение. Так как |sinx| ≤ 1, |sin 2x| ≤ 1, выражение sinx+sin 2x принимает значение, равное 2, тогда и только тогда, когда√       sinx = 1 и

sin      2x = 1, то есть имеем:

откуда

Ни при каких целых k и n последнее равенство не выполняется, поскольку в его левой части число иррациональное, а в правой – целое. 149 Поэтому полученная система, а вместе с ней и данное уравнение, не имеет решений.

Ответ: нет решений.

Пример 98. Решить уравнение

.

Решение. Уравнение эквивалентно системе тригонометрических уравнений

.

Находим пересечение решений последней системы:

Решим последнее уравнение в целых числах. Очевидно, что k = 2 и n = 1 являются решением этого уравнения. То есть имеет место тождество

3 · 2 − 5 · 1 = 1.

Вычитая из уравнения 3k−5n = 1 тождество 3·2−5·1 = 1, получаем:

.

Чтобы k − 2 было целым, нужно, чтобы  было целым. Тогда 150 имеем решение уравнения в целых числах:

.

В силу этого тригонометрическая система уравнений

,

эквивалентная исходному уравнению, имеет решение

.

Ответ: .

Пример 99. Решить уравнение

sinax + sinbx = 2

и выяснить, при каких a и b решение существует.

Решение. Очевидно, что уравнение эквивалентно системе уравнений

.

Находим пересечение решений последней системы:

.

151

Чтобы равенство b(1+4k) = a(1+4n) было справедливым при целых k и n, необходимо и достаточно, чтобы a и b были связаны зависимостью

, откуда  при p,q ∈ Z.

Таким образом, для разрешимости исходного уравнения его нужно взять в виде

при p,q ∈ Z, откуда получаем:

( x = _a1 π₂ + 2πk, x = 1+41p π2 + 2πn.

1+4qa

Находим пересечение этой системы:

.

При k = q и n = p из уравнения (1+4p)k−(1+4q)n = q−p получаем тождество

(1 + 4p)q − (1 + 4q)p = q − p.

Вычитая из уравнения (1 + 4p)k − (1 + 4q)n = q − p тождество (1 + 4p)q − (1 + 4q)p = q − p, имеем:

(1 + 4p)(k − q) − (1 + 4q)(n − p) = 0.

          Для получения целочисленного решения этого уравнения положим                   152

, тогда будем иметь общее решение уравнения (1+4p)k− − (1 + 4q)n = q − p:

k = q + (1 + 4q)t, n = p + (1 + 4p)t, t,p,q ∈ Z.

В итоге решением исходного уравнения будет

Ответ: .

Пример 100. Решить уравнение

cos²x + cos²2x + cos²3x + cos²4x = 2.

Решение. Применяя формулу понижения степени получаем:

cos2x + cos4x + cos6x + cos8x = 02cos3xcosx + 2cos7xcosx = 0

m

                                                                                                                                             ,mZ.

Рассмотрим возможность совпадения серий. Для этого составим совокупность равенств:

153

,

.

Первое и третье равенства ни при каких целых числах соответственно n, k и m, n невозможны, поскольку в левых частях стоят нечетные числа, а в правых – четные. А вот второе равенство m = 2+5k свидетельствует о том, что при m = 2 + 5k из третьей серии получается первая серия решений. В самом деле,

π π(2 + 5k) π 2π 5πk π x = + = + + = + +πk.

                                           10               5               10        5          5          2

В итоге получаем решение исходного уравнения:

                                                              π        πn π         πm

                                                                     +        ;        +           ,n,m ∈ Z

                                                              4        2    10        5

Ответ. .

154

3 Практикум по решению уравнений в целых числах

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

x² + 5y² = 20z + 2.

Решение. Перепишем исходное уравнение в виде:

x² = 20z − 5y² + 2.

Правая часть данного уравнения есть число, которое при делении на 5 дает в остатке 2. Следовательно, x² не делится на 5. Но квадрат числа, не делящегося на 5, дает в остатке 1 или 4 (докажите самостоятельно). Таким образом, равенство

x² = 20z − 5y² + 2

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

Ответ: решений нет.

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

                                                                          19x² + 91y² = 1991.                                                                         155

Решение. Перепишем уравнение в виде

19(x² − 100) = 91(1 − y²).

Поскольку числа 19 и 91 взаимно просты, то x² − 100 кратно 91, а 1 − y² кратно 19, т. е. x² − 100 = 91n, 1 − y² = 19k, где n,k ∈ Z. Подстановкой в равенство 19(x² − 100) = 91(1 − y²) убеждаемся, что k = n. Тогда имеем

.

Из условия x² = 91n + 100 ≥ 0 получаем; а из y² = 1 − 19n имеем. Таким образом, n = 0 или n = −1. При n = 0 получим x² = 100, y² = 1, т. е. четыре пары решений (10;1), (10;−1),(−10;1), (−10;−1). При n = −1 решений в целых числах нет.

Ответ: (10;1), (10;−1), (−10;1), (−10;−1).

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

x! + y! = 4z + 3,

где x! = 1 · 2 · ... · x; y! = 1 · 2 · ... · y.

Решение. Правая часть уравнения есть нечетное число. Следовательно, и левая часть также должна быть нечетным числом. Значит, либо x, либо y меньше 2. Пусть y = 1, тогда x! = 4z + 3. Правая часть последнего равенства не делится на 4, значит, x < 4. Проверкой убеждаемся, 156 что x = 3, z = 1. Аналогично, при x = 1 получим y = 3, z = 1.

Ответ: (1;3;1), (3;1;1).

Решить в натуральных числах уравнение:

x⁴ + x³ + x² + x + 1 = y².

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

. Тогда, умножив обе части исходного уравнения на 64, получим равенство

(8x² + 4x + 3)³ + 4x + 55 = (8y)².

Так как,x,y ∈ N, то из последнего равенства заключаем, что

8y > 8x² + 4x + 3 ⇔ 2y ≥ 2x² + x + 1,

откуда

4y² ≥ (2x² + x + 1)² = 4x⁴ + 4x³ + 5x² + 2x + 1.

Умножив теперь обе части исходного уравнения на 4 и воспользовавшись последним неравенством, имеем

4x⁴ + 4x³ + 4x² + 4x + 4 ≥ 4x⁴ + 4x³ + 5x² + 2x + 1 ⇔ x² − 2x − 3 ≤ 0,

откуда −1 < x < 3. Задача свелась к проверке значений x = 1, x = 2, 157 x = 3. Имеем x = 3, y = 11.

Ответ: (3;11).

Найти натуральные x и y, удовлетворяющие уравнению:

117x − 79y = 17,

для которых x + y имеет наименьшее значение.

Решение. Пусть 2x−y = u, тогда 79u−41x = 17. Как видим, у нового уравнения один из коэффициентов уменьшился. Преследуя указанную цель, проведем цепочку преобразований:

Последнее уравнение имеет очевидное решение w = 17 − 2t, t ∈ Z. Теперь пойдем по нашей цепочке в обратном направлении:

v = t − w = 3t − 17,u = 13v − w = 41t − 238, x = 2u − v = 79t − 459

, y = 2x − u = 117t − 680.                                                                                                                      158

Из условия x,y ∈ N найдем t ≥ 6. Очевидно, что x + y имеет наименьшее значение при наименьшем t, т. е. при t = 6.

Ответ: x = 15; y = 22.

Какие целые положительные числа могут удовлетворять

уравнению

xyz = x + y + z ?

Решение. Для определенности будем считать, что x < y < z. Тогда

xyz = x + y + z ≤ z + z + z = 3,

откуда следует (так как z 6= 0), что

xy ≤ 3 ⇒ x ≤ 3, y ≤ 3.

Проведем полный подбор всех вариантов. Если y = 3, то так как xy < 3, значит, может быть только x = 1. Тогда из исходного уравнения получаем

1 · 3 · z = 1 + 3 + z ⇔ z = 2,

но x < y < z.

Если y = 2, то так как xy < 3, значит, опять x может принимать только значение x = 1. Тогда из исходного уравнения получаем 1·2·z = = 1 + 2 + z ⇔ z = 3 и тройка (1;2;3) – решение. Если y = 1, то так как x < y, значит, x = 1 и исходное уравнение не имеет решений.

159 Итак, нашли только одну тройку: (1;2;3). Остальные решения получаются различными перестановками этих чисел.

Ответ: (1;2;3),(1;3;2),(2;1;3),(2;3;1),(3;1;2),(3;2;1).

Решить в натуральных числах уравнение:

x + y = (x − y)².

Решение. Если x = y, то уравнение примет вид 2x = 0, и решений исходного уравнения в натуральных числах нет.

Так как x,y ∈ N,то x+y ∈ N. Если x > y, то x−y ∈ N,а если x < y, то x − y ∈ N. Значит, исходное уравнение равносильно совокупности линейных систем:

,

;

,

где p ∈ N, p 6= 1. Решая первую систему, получаем, а из второго – .

Ответ: – любое натуральное число, кроме единицы.

160

Доказать, что уравнение 3x²−4y² = 14 не имеет решений

в целых числах.

Решение. Одно из слагаемых в левой части уравнения (3x²) делится нацело на 3. Второе слагаемое (4y² = (2y)²) является полным квадратом. Известно, что квадрат натурального числа при делении на 3 дает в остатке или 1 или 0. То есть 3x² − 4y² либо делится нацело на 3, либо дает в остатке 1. Справа стоит число 14, которое при делении на 3 дает в остатке 2. Следовательно, левая часть не может быть равна правой, так как они при делении на 3 никогда не имеют одинаковых остатков.

Пример 9. Решить уравнение  в попарно взаимно простых числах x,y,z.

Решение. Домножим уравнение на xyz:

x²z + y²x + z²y = 2000xyz,

Значит, z делит на y²x, но z взаимно просто с y и z взаимно просто с

x. Следовательно, z = ±1.

Аналогично, x = ±1, y = ±1.

161

Тогда,.

Ответ: решений нет.

Пример 10. Доказать, что уравнение xⁿ +yⁿ = zⁿ не имеет решений

в целых положительных числах, если

√

Решение. Так как n ∈ N, то ⁿ 2 > 1. Так как по условию и кроме того z − 1 – положительное число, то, значит,

.

По условию xⁿ + yⁿ = zⁿ, поэтому

.

Сложив неравенства в последней системе, получим xⁿ + yⁿ = = 2(z − 1)²,тогда из zⁿ > 2(z − 1)ⁿ следует, что xⁿ + yⁿ < zⁿ,то есть уравнение не имеет решений.

Ответ: решений нет.

Пример 11. Решить в простых числах уравнение: x^y + 1 = z.

Решение. Имеем x ≥ 2, y ≥ 2, значит, x² ≥ 4 и z = x^y + 1 ≥ 5.

Если x^y + 1 – простое, значит, x^y – четное, следовательно, x – четное и простое, то есть x = 2.

Если бы y = 2k + 1, то x = 2^2k+1 + 1 = (2 + 1)(2^2k − 2^2k−1 + ··· + 1), 162 то есть z делилось бы на 3. Так как z ≥ 5, то z – не простое. Итак, y – четное и простое, то есть y = 2 и z = 5.

Ответ: (2;2;5).

Пример 12. Решить уравнение (x + 4)⁴ − x⁴ = y³ в целых числах.

Решение. Запишем y³ = 8(x³+3x²+4x+2), то есть y = 2z, где z ∈ Z.

Тогда z³ = x³ + 3x² + 4x + 2.

Пусть x ≥ 0,

(x + 1)³ < x³ + 3x² + 4x + 2 < (x + 2)³,

(x + 1)³ < z³ < (x + 2)³,

что невозможно.

Пусть x ≤ −2 и u = −x − 2.

Тогда u ≥ 0 и

(x + 4)⁴ − x⁴ = (−u)⁴ + (−u − 2)⁴ = u⁴ + (u + 2)⁴ = y³,

Значит, u³ + 3u² + 4u + 2 = t³, где u ≥ 0, что, как показано выше, невозможно.

Ответ: (−1;0).

Пример 13. Решить уравнение

                                                                                                                                             163

в натуральных числах.

Решение. Заметим, что x,y,z,t > 1. Пусть x ≥ y ≥ z ≥ t.

,

Значит, t = 2.

,

Значит,.

Значит, y = 2. Тогда x = 2.

Ответ: (2;2;2;2).

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

,

Решение. Подставим z = x² + y во второе уравнение:

                                                                          (x² + y)² = y² + x + 2,                                                                         ¹⁶⁴

x(x³ + 2xy − 1) = 2.

Значит, x делит 2, то есть x = ±1; ±2.

Если x = 1, то y = 1, z = 2.

Если x = −1, то y = 0, z = 1.

Если x = −2, то y = −2, z = 2.

Если, что невозможно.

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

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

.

Решение. Имеем

(x + y + z)³ − (x³ + y³ + z³) = 3(x + y)(y + z)(z + x),

тогда согласно условию, имеем

(x + y)(y + z)(z + x) = 8,

причем (x + y) + (y + z) + (z + x) = 2(x + y + z) = 6.

Значит, числа x + y,y + z,z + x либо все четны, либо одно из них четное.

Тогда

                                                                         ^x + y = 2;8;−1⁰ − 1                                                                          165



y + z = 2;−1;8;−1 .

z + x = 2 − 1;−1;8

Ответ: (1;1;1),(4;4;5),(4;−5;4),(−5;4;4).

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

x⁴ + x³ + x² + x + 1 = y².

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

исходного уравнения на 64 получим равенство

(8x² + 4x + 3)² + 40x + 55 = (8y)².

Так как x,y ∈ N, то

откуда

4y² ≥ (2x² + x + 1)² = 4x⁴ + 4x³ + 5x² + 2x + 1.

Умножив теперь обе части исходного уравнения на 4 и воспользовавшись последним неравенством, имеем

4x⁴ + 4³ + 4x² + 4x + 4 = 4y² ⇒

⇒ 4x⁴ + 4³ + 4x² + 4x + 4 ≥ 4x⁴ + 4³ + 5x² + 2x + 1 ⇔ 166 ⇔ x² − 2x − 3 ≤ 0 ⇔ −1 ≤ x ≤ 3.

Задача свелась к проверке для чисел 1,2,3.

Ответ: (3;11).

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

x² + 9y² = 3z + 2.

Решение. Перепишем уравнение в виде x² = 3z − 9y² + 2.

Правая часть данного уравнения есть число, которое при делении на 3 дает в остатке 2. Следовательно, x² не делится на 3. Но квадрат числа, не делящегося на 3, дает в остатке 1. Таким образом, равенство x² = 3z − 9y² + 2 невозможно, так как левая и правая часть дают при делении на 3 разные остатки.

Ответ: решений нет.

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

1! + 2! + ... + x! = y².

Решение. Подставив вместо последовательно числа 1, 2, 3, 4, 5, ... убеждаемся, что при x = 1, y = ±1 и при x = 3, y = ±3, числа 2, 4, 5, 6, ... не удовлетворяют условию задачи. Докажем, что при x ≥ 4 данное уравнение решений не имеет. В самом деле, сумма 1!+2!+3!+4!+5!+ +...+x! при x ≥ 4 оканчивается цифрой 3, но квадрат целого числа не может оканчиваться цифрой 3, поэтому других решений уравнение не

имеет.                                                                                                                                                          167

Ответ: (1;1),(1;−1),(3;3),(3;−3).

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

x³ − y³ = xy + 61.

Решение. Сделаем замену x = d+y, где d ≥ 1, d ∈ N. Тогда получим (d + y)³ − y3 − y(d + y) = 61 ⇔ d³ + 3d²y + 3dy² − dy − y² = 61,

(3d − 1)y² + (3d2 − d)y + d³ − 61 = 0.

Дискриминант этого уравнения будет неотрицательным при

1 ≤ d ≤ 5. Перебирая все d от 1 до 5 и, подставляя в

(3d − 1)y² + (3d2 − d)y + d³ − 61 = 0,

можно убедиться, что лишь при d = 1 уравнение будет иметь целые корни y = 5 и y = −6. Отсюда получаем, что x = 6 и x = −5 соответственно.

Ответ: (−5;−6),(6;5).

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

,

Решение. Данную систему уравнений можно представить в виде совокупности двух систем, причем x и y будут иметь разные знаки:

                                                                                        x > 0,                                                                                       168

 y < 0, x − y = 5,

^ xy = −6.

^ x < 0,

 y > 0, x − y = 5,

^ xy = −6.

Решая первую систему, получим следующее:

При y = −2,x = 3,y = −3,x = 2. Решая вторую систему, придем к выводу, что при x = −2y = 3, а при x = −3,y = 2.

Ответ: (−3;2),(−2;3),(2;−3),(3;−2).

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

^x² = y − 1,



y² = z − 1, z² = x − 1.

Решение. Если x – четно, то из первого уравнения следует, что y – нечётно, а тогда из второго уравнения получаем, что z – четно, а из третьего уравнения следует, что x – нечётно. Тем самым получаем противоречие. Если же x – нечётно, то y – четно, z – нечётно, x – четно 169

– противоречие. Полученные противоречия свидетельствуют о том, что данная система не имеет решений в целых числах.

Ответ: нет решений.

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

,

Решение. Из второго уравнения системы следует, что xyz 6= 0. Если обе части второго уравнения умножить на xyz, то получим уравнение

xy + xz + zy = 0.

Из первого уравнения следует, что x+y = −z. Подставим выражение x + y в уравнение xy + xz + zy = 0, тогда xy = z². Аналогично легко получить, что xz = y² и yz = x²4. В таком случае уравнение xy + xz + + zy = 0 можно переписать в виде

x² + y² + z² = 0,

откуда следует, что x = y = z = 0. Полученные значения переменных противоречат области допустимых значений переменных. Следовательно, исходная система не имеет решений.

Ответ: нет решений.

             Пример 23. Решить систему уравнений в натуральных числах                                170

^ x² + y² + z² = 14,



xy + xz + yz = 11,

 xyz = 6.

Решение. Умножим второе уравнение на два и сложим с первым уравнением. Тогда получаем уравнение x + y + z = ±6. Рассмотрим два случая.

1) Пусть x + y + z = 6. Тогда y + z = 6 − x. Из третьего уравнения получаем

.

Перепишем второе уравнение системы в виде x(y + z) + yz = 11. Отсюда нетрудно получить уравнение относительно переменной вида

,

которое эквивалентно уравнению третьей степени

x³ − 6x² + 11x − 6 = 0.

Первый корень данного уравнения легко находится подбором, то есть x₁ = 1.

Для нахождения других корней уравнения x³ − 6x² + 11x − 6 = 0 необходимо решить квадратное уравнение x² − 5x + 6 = 0. Очевидно, что корнями являются x₂ = 2 и x₃ = 3.

171 Для нахождения значений переменных y и z необходимо рассмотреть три системы уравнений

,

,

Отсюда получаем следующие тройки решений (1;2;3),(1;3;2),(2;1;3), (2;3;1),(3;1;2),(3;2;1).

2) Пусть x + y + z = −6. Очевидно, что в таком случае исходная система будет иметь хотя бы один отрицательный корень [2,3,6,9]. Ответ: (1;2;3),(1;3;2),(2;1;3),(2;3;1),(3;1;2),(3;2;1).

172

4 Задачи для самостоятельного решения

1.    Решите диофантовы уравнения всеми возможными методами:

1.1 3x + 4y = 13; 1.2 8x − 13y = 63; 1.3 7x − 19y = 23; 1.4 39x − 22y = 10; 1.5 17x − 25y = 117; 1.6 43x + 37y = 21; 1.7 53x + 47y = 11; 1.8 45x − 37y = 25;

1.9 81x − 48y = 33; 1.10 26x + 34y = 13; 1.11 122x + 129y = 2; 1.12 258x + 172y = 56; 1.13 38x + 117y = 209; 1.14 119x − 68y = 34; 1.15 258x − 175y = 113; 1.16 41x + 114y = 5.

2.    Найдите все пары целых чисел x и y, для которых x³ + y³ = 8³⁰.

3.    Найти все натуральные числа, которые не могут быть представлены в виде суммы нескольких (не менее двух) последовательных натуральных чисел.

173 4. Существуют ли такие 1996 последовательных целых чисел, сумма которых равна 1996²?

5.        Существуют ли такие целые числа x и y, чтобы 3x² + 2y² = 1998?

6.        Найдите все пары (x,y) неотрицательных целых чисел x и y, удовлетворяющих равенству x − y = x² + xy + y².

7.        Решить в целых числах x, y, z систему уравнений:

.

8.        Найдите все натуральные простые числа p и q, такие, что уравнение x² − qx − 20 = pq имеет по крайней мере один целый корень.

9.        Найдите все пары натуральных простых чисел (p,q), при которых уравнение x⁵−8x³+qx²−16 = p имеет по крайней мере один целый корень.

10.    Найдите все пары натуральных простых чисел (p,q), при которых уравнение x⁴ + (q − 2)x + 4 = p имеет по крайней мере один целый корень.

11.    Найдите все такие тройки (a,b,c) натуральных чисел, что a² +b² − − 33c² = 8bc, и – простое число.

12.    Решить диофантово уравнение: 13y = x² − 21x + 110.

13.    Решить в целых числах, больших чем 1, уравнения:

174

                3^x − 2^y = −1,                                                        z^x − 2^y = 1,

               3^x − 2^y = 1,                                                            z^x − 2^y = −1.

5. Вопросы для самоконтроля

1.        Какое уравнение называют диофантовым уравнением?

2.        Какое уравнение называют линейным диофантовым уравнением?

3.        Сформулируйте критерий разрешимости линейного диофантова уравнения.

4.        Назовите методы решения линейных диофантовых уравнений.

5.        В чем состоит суть метода полного перебора всех возможных значений переменных, входящих в уравнение?

6.        В чем состоит суть метода разложения на множители?

7.        В чем состоит суть метода, основанного на выражении одной переменной через другую и выделении целой части дроби?

8.        В чем состоит суть метода, основанного на выделении полного квадрата?

9.        В чем состоит суть метода решения уравнения с двумя переменны- 175 ми как квадратного относительно одной из переменных?

10.    В чем состоит суть метода, основанного на оценке выражений, входящих в уравнение?

11.    В чем состоит суть метода бесконечного (непрерывного) спуска?

12.    В чем заключается метод решения диофантовых уравнений с помощью алгоритма Евклида?

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

14.    В чем заключается метод решения диофантовых уравнений с помощью сравнений?

15.    Какое уравнение называют уравнением Пелля?

16.    Назовите методы решения уравнения Пелля?

17.    Охарактеризуйте циклический метод решения уравнения Пелля?

18.    Какое уравнение называется уравнением Каталана?

19.    Опишите метод решения уравнения Каталана.

20.    Какое уравнение называется уравнением Маркова?

21.    Назовите методы решения уравнения Маркова.

176 22. Какое уравнение называют диофантовым уравнением второй степени? Приведите примеры диофантовых уравнений второй степени.

23.    Назовите методы решения диофантовых уравнений второй степени.

24.    Сформулируйте великую теорему Ферма.

25.    Назовите методы решения диофантовых уравнений степени выше второй.

177

Литература

1.    Башмакова, И.Г. Диофант и диофантовы уравнения / И.Г. Башмакова. – М.: Наука, 1972. – 68 с.

2.    Гильфорд, А.О. Решение уравнений в целых числах / А.О. Гильфорд. – М.: Наука, 1983. – 64 с.

3.    Виленкин, Н.Я. За страницами учебника математики: Пособие для учащихся 5-6 классов средней школы / Н.Я. Виленкин, И.Я. Депман. – М.: Просвещение, 1989. – 287 с.

4.    Буштаб, А.А. Теория чисел. / А.А. Буштаб. – М.: Просвещение, 1966. – 385 с.

5.    Хинчин, А.Я. Цепные дроби. / А.Я. Хинчин. – М.: Наука, 1978. – 111 с.

6.    Гринько, Е.П. Система работы с интеллектуально одаренными детьми : монография / Е.П. Гринько; Брест. гос. ун-т имени А.С. Пушкина. – Брест: Изд-во БрГУ, 2009. – 229 с.

178 7. Гринько, Е.П. Методы решения алгебраических олимпиадных задач : учебно-методич. пособие / Е.П. Гринько ; Брест. гос. ун-т имени А.С. Пушкина. – Брест : БрГУ, 2012. – 108 с.

8.        Грибанов, В.У. Сборник упражнений по теории чисел / В.У. Грибанов, П.И. Титов. – М.: Просвещение, 1964. – 144 с.

9.        Задачи Минской городской математической олимпиады младших школьников / Е.А. Барабанов [и др.] – Мн.: Бел. ассоц. «Конкурс», 2005. – 352 с.

10.    Задачи районного тура Минской городской математической олимпиады школьников (1991—2001 гг.) / Е.А. Барабанов [и др.]. – Мн.: Фаритэкс. 2002. – 181 с.

11.    Кот, В.И. Как одолеть олимпиадные задачи по математике: Пособие для учителей общеобразовательной школы / В.И. Кот. – Мн.: Бестпринт, 2002. – 400 с.

12.    Барабанов, Е.А. Задачи заключительного тура минской городской математической олимпиады школьников / Е.А. Барабанов, И.И. Воронович, В.И. Каскевич, С.А. Мазаник. – Минск, 2006 г.- 352 с.

13.    Московские математические олимпиады 1993 – 2005 г. / Р.М. Федо-

                ров и др. Под ред. В.М. Тихомирова. – М.: МЦНМО,                                                179

2006. – 456 с.

14.    Берлов, С.Л. Петербургские математические олимпиады / С.Л. Берлов, С.В. Иванов, К.П. Кохась. – СПб.: Лань, 2003. – 532 с.

15.    Васильев, Н.Б. Заочные математические олимпиады / Н.Б. Васильев, В.Л. Гутенмахер, Ж.М. Раббот, А.Л. Том. – М.: Наука, 1986. – 230 с.

16.    Довбыш, Р. И. Математические олимпиады: 906 самых интересных задач и примеров с решениями [Текст] / Р. И. Довбыш, Н. А. Кулеско, В.В. Лиманский, Л.Л. Оридрога, Л.Л. Потемкина, Н. Л. Трегуб. – Ростов н/Д: Феникс; Донецк: издательский центр «Кредо», 2006. – 335 с. – (Большая перемена).

17.    Маркова, И.С. Новые олимпиады по математике / И. С. Маркова. – Ростов н/Д: Феникс, 2005. – 315 с.: ил. – (Здравствуй, школа!).

18.    Фарков, А.В. Математические олимпиады в школе / А. В. Фарков. – 5-е изд. – М.: Айрис-Пресс, 2006. – 176 с.: ил. – (Школьные олимпиады).

19.    Прасолов, В.В. Задачи по алгебре, арифметике и анализу: учебное пособие / В.В. Прасолов. – М.: МЦНМО, 2007. – 608 с.: ил.

20.    Мазаник, А.А. Реши сам / А.А. Мазаник, С.А. Мазаник. – Мн., Народная асвета, 1992. – 256 с.

180 21. Петраков, И.С. Содержание и методика подготовки и проведения олимпиад (на примере международных олимпиад) / И.С. Петраков.

– М., 1973, – 152 с.