Олимпиадные задания. Решение уравнений в целых числах
методическая разработка по алгебре (9, 10, 11 класс) на тему

МБОУ «Высокогорская средняя общеобразовательная школа №2

Высокогорского муниципального района Республики Татарстан»        

Олимпиадные задания.

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

                                                                  Разработала:

                                                                 Аксанова Ильсияр Исмагиловна

                                                                 Учитель математики высшей категории

                                                                 МБОУ ВСОШ № 2

С. Высокая Гора – 2015 г.

Введение

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

          Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные  наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Аксандрийского, который исследовал некоторые типы таких уравнений ещё до нашей эры.

Наиболее известное уравнение в целых числах – великая теорема Ферма: уравнение

xn + yn = zn

не имеет ненулевых рациональных решений для всех натуральных n > 2.

При решении уравнений в целых и натуральных числах можно условно выделить следующие способы решения:

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

      В работе представлены два приложения: приложение 1. Таблица остатков при делении степеней (an:m); приложение 2. Задачи для самостоятельного решения

1. Способ перебора вариантов.

        Пример 1.1. Найти множество всех пар натуральных чисел, которые являются решениями уравнения 49х + 51у = 602.

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

х =   602 - 51у ≥ 49,  51у≤553,  1≤у≤10.

        Полный перебор вариантов показывает, что натуральными решениями уравнения являются х=5, у=7.

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

2. Применение алгоритма Евклида. Теорема.

      Дано уравнение ax+by=c, где a, b, c-целые числа, a и b не равны 0.

        Теорема: Если c не делится нацело на НОД(a,b), то уравнение не разрешимо в целых числах. Если НОД(a,b)=1или c делится на НОД(a,b), то уравнение разрешимо в целых числах. Если (x0, y0 )- какое-нибудь решение уравнения, то все решения уравнения задаются формулами:

x=x0-bt

y=y0+at , где t- принадлежит множеству целых чисел.

        Пример 2.1. Решить уравнение в целых числах 5х + 7у = 19

Подберём сначала некоторое конкретное решение. В данном случае, это просто, например,

x0 = 1, y0 = 2.

Тогда   5x0 + 7y0 = 19, откуда

5(х – x0) + 7(у – y0) = 0,

5(х – x0) = –7(у – y0).

Поскольку числа 5 и 7 взаимно простые, то

х – x0 = 7k, у – y0 = –5k.

Значит, общее решение:

х = 1 + 7k, у = 2 – 5k,

где k – произвольное целое число.

Ответ: (1+7k; 2–5k), где k – целое число.

         Пример 2.2.  Решить уравнение 201х – 1999у = 12.

         Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 1999 и 201:

НОД(1999, 201) = НОД(201, 190) = НОД(190, 11) = НОД(11, 3) = НОД(3 , 2) = НОД(2, 1) = 1.

       Запишем этот процесс в обратном порядке:

1 = 2 – 1 = 2 – (3 – 2) = 2·2 – 3 = 2· (11 – 3·3) – 3 = 2·11 – 7·3 = 2·11 – 7(190 – 11·17) =

= 121·11 – 7·190 = 121(201 – 190) – 7·190 = 121·201 – 128·190 =

= 121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

       Значит, пара (1273, 128) является решением уравнения 201х – 1999у = 1. Тогда пара чисел

x0 = 1273·12 = 15276, y0 = 128·12 = 1536

является решением уравнения 201х – 1999у = 12.

Общее решение этого уравнения запишется в виде

х = 15276 + 1999k, у = 1536 + 201k, где k – целое число,

или, используя, что 15276 = 1283 + 7·1999, 1536 = 129 + 7·201, имеем

х = 1283 + 1999n, у = 129 + 201n, где n – целое число.

Ответ: (1283+1999n, 129+201n), где n – целое число.

3. Метод остатков. 

        Этот метод основан на исследовании возможных остатков левой и правой частей уравнения от деления  на некоторое фиксированное натуральное число.

Замечание. Говоря строго математическим языком, для решения уравнения в данном случае применяется теория сравнений.

Рассмотрим примеры, которые раскрывают сущность данного метода.

        Пример 3.1. Решить уравнение в целых числах x3 + y3 = 3333333;

Так как x3 и y3 при делении на 9 могут давать только остатки 0, 1 и 8 (смотрите таблицу в приложении 1), то x3 + y3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.

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

        Пример 3.2. Решить уравнение в целых числах  x3 + y3 = 4(x2y + xy2 + 1).

 Перепишем исходное уравнение в виде (x + y)3 = 7(x2y + xy2) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.

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

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

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

         Исследуем какие остатки может иметь при делении на три левая часть этого уравнения.По теореме о делении с остатком целое число х либо делится на 3, либо при делении на три в остатке дает 1 или 2.

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

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

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

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

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

        Пример 3.4. Решить в целых числах  x³ - 3y³ - 9z³ = 0  (1)

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

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

x³ = 3y³ + 9z³   (2)

        Так как правая часть полученного уравнения делится на 3, то и левая должна делиться на три, следовательно, так как 3 - число простое, х делится на 3,  т.е. х = 3k, подставим это выражение в   уравнение (2), получим:

27k3 = 3y³ + 9z³, откуда

                                                     9k3 = y³ + 3z³  (3)

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

                                                  3k3 = 9m³ + z³    (4)

         В свою очередь, из этого уравнения следует, что z3 делится на 3, и z = 3n. Подставив это выражение в (4), получим, что k3 должно делиться на 3.

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

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

4. Решение уравнений в целых числах сведением их к квадратным.

          Пример 4.1. Решить в простых числах уравнение

х2 – 7х – 144 = у2 – 25у.

Решим данное уравнение как квадратное относительно переменной у. Получим: у = х + 9 или у = 16 – х.

        Поскольку при нечётном х  число х + 9 является чётным, то единственной парой простых чисел, которая удовлетворяет первому равенству, является (2; 11).

Так как х, у – простые,  то из равенства у = 16 – х,  имеем

2 < х < 16, 2 < у < 16.

С помощью перебора вариантов находим остальные решения: (3; 13), (5; 11), (11; 5), (13; 3).

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

        Пример 4.2. Решить в целых числах уравнение x + y = x2 – xy + y2. 

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

x2 – (y + 1)x + y2 – y = 0.

Дискриминант этого уравнения равен –3y2 + 6y + 1. Он положителен лишь для следующих значений у: 0, 1, 2. Для каждого из этих значений из исходного уравнения получаем квадратное уравнение относительно х, которое легко решается.

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

       Пример 4.3. Решить уравнение в целых числах: 5х2+5у2+8ху+2у-2х+2=0.

Решение:

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

5х2 + (8у - 2)х + 5у2 + 2у + 2 = 0

D = (8у - 2)2 - 4·5(5у2 + 2у + 2) = 64у2 - 32у + 4 = -100у2 - 40у – 40 =                      = -36(у2 + 2у + 1) = -36(у + 1)2

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

-36(у + 1)2 = 0. Это возможно при у = -1, тогда х = 1.

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

5. Разложение на множители.

        Пример 5.1. Решить в целых числах уравнение x2 – xy – 2y2 = 7.

Разложим левую часть на множители  (x – 2y)(x + y) = 7.

Так как х, у – целые числа, то находим решения исходного уравнения, как решения следующих четырёх систем:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Решив эти системы, получаем решения уравнения: (3; –2), (5; 2), (–3; 2) и (–5; –2).

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

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

Решение. Перепишем уравнение в виде:

у2 - х2 = 23,  (у - х)(у + х) = 23

Так как х и у – целые числа и 23 – простое число, то возможны случаи:

Решая полученные системы, находим:

Ответ: (-11;12);(11;12);(11;-12);(-11;-12).

        Пример 5.3. Решить уравнение в целых числах   y3 - x3 = 91.

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

                                          (y - x)(y2 + xy + x2) = 91          

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

 Проводим исследование. Заметим, что для любых  целых x и y  число  

                          y2 + yx + x2 ≥ y2 - 2|y||x| + x2 = (|y| - |x|)2 ≥ 0,

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

             ;   ; ;

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

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

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

Решение. Перенесем все члены уравнения влево и к обеим частям полученного уравнения прибавим (–1)

x + y – xy – 1 = – 1

Сгруппируем первое – четвертое и второе – третье слагаемые и вынесем общие множители, в результате получим уравнение: (x - 1)(y - 1) = 1

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

Ответ:  (0,0) и (2,2).

        Пример 5.5. Доказать, что уравнение (x - y)3 + (y - z)3 + (z - x)3 = 30 не имеет решений в целых числах.

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

                            (x - y)(y - z)(z - x) = 10      

 Делителями 10 являются числа ±1, ±2, ±5, ±10. Заметим также, что сумма сомножителей левой части уравнения  равна 0. Нетрудно проверить, что сумма любых трех чисел из множества делителей числа 10, дающих в произведении 10, не будет равняться 0. Следовательно, исходное уравнение не имеет решений в целых числах.

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

6. Метод бесконечного спуска.

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

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

Выберем неизвестное, имеющее наименьший коэффициент , и выразим его через другое неизвестное: .  Выделим целую часть:       Очевидно, что х будет целым, если выражение   окажется целым, что, в свою очередь, будет иметь место тогда, когда число 4 – 3y без остатка делится на 5.  

           Введем дополнительную целочисленную переменную z следующим образом: 4 –3y = 5z. В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами. Решать его будем уже относительно переменной y, рассуждая аналогично: . Выделяя целую часть, получим:

.

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

 u: 3u = 1 – 2z.

Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z:  = . Требуя, чтобы  было целым, получим: 1 – u = 2v, откуда u =  1 – 2v. Дробей больше нет, спуск закончен.

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

z = = = 3v – 1;        = 3 – 5v.

 =  = 3+8v.

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

Ответ: x =  3+8v  и y = 3 – 5v.

7. Оценка выражений, входящих в уравнение.

        Пример 7.1. Решить в целых числах уравнение   (х2 + 4)(у2 + 1) = 8ху

Решение. Заметим, что если (х;у) – решение уравнения, то (-х;-у) – тоже решение.

И так как х = 0 и у = 0 не являются решением уравнения, то, разделив обе части уравнения на ху, получим:

∙ = 8, (х +)(у +) = 8.

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

х +  = 4, у + = 2,

тогда их произведение (х + )(у +) = 4·2 = 8, значит, х +  = 4 и у + = 2.

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

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

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

x2 + 13y2 – 6xy = 100

Решение. x2+13y2–6xy=100 ↔ (x-3y)2+4y2=100. Так как (x-3y)2≥0, то 4y2≤100, или │2y│≤10. Аналогично, в силу 4y2≥0 должно выполняться │x-3y│≤10.

Возможны 12 случаев:

Ответ: (±15; ±5); (±10; ±0); (±18; ±4);

(±6; ±4); (±17; ±3); (±1; ±3).

8. Применение цепных дробей.

        Пример 8.1. Решите в целых числах уравнение  25x-18y+1=0.

Найдем наибольший общий делитель пары чисел 25 и 18 с помощью цепных дробей, то есть используем один из вариантов алгоритма Евклида.

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

 = 1 +  = 1 +  = 1 +  = 1  +  = 1 +  = 1 +  = 1 + ,

где выражение 1+ называется целой дробью.

Числа 1, 2, 1, 1,  выделенные в этом выражении, являются последовательными частными алгоритма Евклида для нахождения наибольшего общего делителя пары чисел 25 и18.

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

1 +  – 1 +  –  .

Вычтем полученную дробь из исходной дроби :

 –  =  = .

Приведем ее к общему знаменателю: 25 ∙ 5 – 18 ∙ 7 + 1 = 0.

Получили частное решение исходного уравнения х = 5, у = 7.

Общее решение исходного уравнения: х = 5 + 18t; y = 7 + 25t, t  Z.

Ответ: х = 5+18t; у = 7+25t.

Приложение 1. Таблица остатков при делении степеней (an:m)

Приложение 2. Задачи для самостоятельного решения

1. Решить в простых числах уравнение x2 - 2y2 = 1.
2. Доказать, что уравнение x3 + x + 10y = 20004 неразрешимо в целых числах.
3. Доказать, что уравнение x5 + 3x4y - 5x3y2 - 15x2y3 + 4xy4 + 12y5 = 33 неразрешимо в целых числах.
4. Решить в целых числах уравнение 2x3 + xy - 7 = 0.
5. Доказать, что уравнения не имеют целочисленных решений:  

а) y2 = 5x2 + 6;         б) x3 = 2 + 3y2

6. Решить в целых числах уравнения: а) x2 + x = y4 + y3 + y2 + y;

        б) x² - y² = 91; в)  2ху = х² + 2y; г) 3x2 +4ху – 7y2 =13

7. Решите в натуральных числах уравнения:

          а)  2х² + 5ху – 12у² = 28;      б) х² - 4ху – 5у² = 1996.

8. Докажите, что система уравнений не имеет решений в целых числах.

9. Найти все пары целых чисел, удовлетворяющих уравнению

          а) x2 = y2+ 2y +13; б) xy = 20 – 3x + y; в) xy + 1 = x + y; г) x2– 3xy + 2y2 = 3

10. Существуют ли целые числа m и n, удовлетворяющие уравнению

m2 + 1994 = n2

11. Найти все простые числа, которые одновременно являются суммой двух простых чисел и разностью двух простых чисел.
12. Докажите, что уравнение x2 – y2 = 30 не имеет решений в целых числах.
13. Решите уравнение x2 – 2х + y2 – 4y + 5 = 0.
14. Если первую цифру трехзначного числа увеличить на n, то полученное число будет в n раз больше исходного. Найдите число n и исходное число.
15. Решить в целых числах уравнение x2 + y2 + z2 = 2xyz.
16. Решить в целых числах уравнение x2 - 2y2 + 8z = 3.
17. Решите в натуральных числах систему уравнений:

а)      б)

18. Найдите два натуральных числа, разность квадратов которых равна 45.
19. Найдите все пары натуральных чисел, удовлетворяющих уравнению:

а)  x2 - y2 = 105;      б) 2x2 + 5xy – 12y2 = 28

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

а)  xy + 3x – 5y = – 3;     б) x – y =

21. Докажите, что система не имеет целочисленных решений

Литература:

1. Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах. Факультативный курс. – М.: МГИЭТ(ТУ). 2003. – 224 с.

2.  В. Серпинский. О решении уравнений в целых числах. 1961.

3. Карпова И.В. Решение уравнений в целых числах.

4. http://www.fmclass.ru/pic/48503321f105d/uravneniya-v-celyh-chislah.pdf

          Образовательный портал «Физ/Мат класс» www.fmclass.ru. 

5. http://diofant.na.by/

6. www.a-elita.net/userfiles/File/.../Integer%20solutions_2012_10.pdf 

7. http://math4school.ru/uravnenija_v_celih_chislah.html