Диофантовы уравнения

Диофантовы  уравнения.

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

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

   Линейное диофантово уравнение с двумя неизвестными    ах + вх = с  (где  а, в, с, – целые,  а, в – взаимно простые числа), очевидно имеет бесконечное число решений:   х = хо – вk,   у = уо +аk,  где (хо,уо) – любое   решение,    k.

Ι. Линейные уравнения.

1. Решить в целых числах уравнение  38х + 14у = 22.

Решение: Убедимся, что НОД коэффициентов при неизвестных является делителем свободного члена: НОД(38; 14) = 2.  22 делится на 2 следовательно уравнение имеет решения. Поделим уравнение на НОД. Получим уравнение с теми же решениями, что и исходное:

                      19х + 7у = 11           (1)

   НОД коэффициентов теперь равен 1. Решим вспомогательное    уравнение

                     19х +7у =1                (2)

    Применим алгоритм Евклида:

   19 = 7 · 2 + 5

    7 = 5 · 1 + 2

    5 = 2 · 2 + 1 – последний ненулевой остаток всегда равен 1.

   «Соберём» алгоритм Евклида «в обратную сторону»:

   1 = 5 + 2 · (-2); выразим число 2 из предпоследнего уравнения:

   1 = 5 – ( 7 – 5 · 1) · 2 = 7 · (-2) + 5 ·3.  Теперь выразим число 5 из первого:      1 = 7 · (-2) + (19 – 7 ·2) · 3 = 19 · 3 + 7 · (-8).

    Таким образом, некоторое решение уравнения (2)  таково:  х2 = 3; у2 = - 8. Чтобы получить частное решение уравнения  (1) умножим  х2  и  у2   на 11, получим  х1 = 33;  у1 = -88.

    Для получения общего решения воспользуемся формулами: х = х1 – вk,   у = у1 +аk.  Тогда  х = х1 – 7k;  у = у1 +19k.

   Ответ:  х = 33 - 7k;   у = -88 + 19k, где  k – целое число.

2. Решите уравнение в целых числах  6х – 9у = 7.

Решение: НОД (6; 9) = 3, следовательно, левая часть делится на 3 при любых целых значениях  х  и  у.  Правая  часть  (число 7)  не делится на  3.

   Ответ: уравнение не имеет решений.

3. Пятиклассник расставляет игрушечных солдатиков по 10 в шеренгу. В    последней не хватило трёх солдатиков. Он стал ставить в шеренгу по 12 солдатиков – 7 осталось. Затем он уложил их в коробки по 100 штук – третья коробка оказалась неполной. Сколько всего солдатиков у школьника?

   Решение: Пусть с – число солдатиков, х – количество полных шеренг по 10, у – по 12.  Тогда   с = 10х + 7 = 12у + 7, откуда  5х = 6у. Левая часть равенства кратна 6, т.е. х = 6k, следовательно, у = 5k,  с = 60k + 7, k 

  Условию  200 < с < 300  удовлетворяет только k = 4, откуда х = 23, у = 20, с = 247.

4.  Можно ли между 30 детьми разделить поровну 29 конфет, не разрезая их более чем на 6 частей?

   Решение: Разобьём все конфеты на х групп по 5 и у групп по 6 (имея в виду делить каждую конфету первой группы на 6 частей, а второй – на 5), т. е.  5х + 6у = 29. Отсюда х =1, у = 4. Значит  5·1=5 конфет делим на 6 частей получим 30 частей  и 6·4=24 конфеты делим на 5 частей получим 120 частей. Всего 150 частей поделим между 30 детьми.

5. Сколькими способами можно набрать сумму в 10 рублей монетами по 3 и 5 копеек?

  Решение: Пусть х монет по 3 коп. и у монет по 5 коп. в сумме дают 10 р. Тогда  3х + 5у = 1000. Имеем:  Последнее слагаемое    k =      должно  быть  целым.    Отсюда   у =3k – 1,         х = 333 – 2(3k – 1) + k = 335 - 5k.  Последнее равенство имеет смысл для k = 1, 2, …, 67. Ответ: 67 способов.

6.  Три рыбака вечером наловили рыбы и легли спать. Первый, проснувшись утором, решил не будить остальных. Он разделил рыбу из садка поровну, но одна рыба оказалась лишней; он выбросил её в воду, забрал третью часть улова и уехал домой. Через час встал второй. Думая, что он проснулся первым, и не желая будить остальных, проделал то же самое, что и первый: выкинул в воду лишнюю рыбу, взял третью часть от оставшегося улова и уехал. Ещё через час все это повторил третий рыбак, тоже считая, что он встал первым. Каков был улов?

    Решение : Пусть поймано  х рыб.

      доля первого рыбака,

     остаток после первого дележа,

     доля второго рыбака,

     остаток после второго дележа,

     доля третьего рыбака.

     Выразим из последнего уравнения х:  

    Последний одночлен обозначим  новой переменной: k =  Тогда  выражение х через k будет иметь целые коэффициенты: х = 7у – k + 5.

   А из предыдущего равенства имеем: у = 4 k – 1. Подставим это значение в выражение для х: х = 27 k – 2. Мы получим формулу для всех решений задачи, если придадим параметру  k значения 1, 2, 3, … При этом х=25, 52, 77, …

7. Найти все целые корни уравнения   не превосходящие по модулю 100.

   Решение:  Умножим обе части уравнения на 91, получим 13а – 7с = 1,  где   т.е. а = 7 k – 1, с = 13 k – 2,  Получили бесконечное множество корней, но условию удовлетворяют лишь а  при |7 k – 1|< 100,  с  при    |13 k – 2|<100, т.е. при  | k | ≤ 7.     Ответ: а = 7 k – 1, с = 13 k – 2,  при  | k | ≤ 7.

8. Сумма всех трехзначных чисел без некоторых двух в 600 раз больше одного из этих чисел. Найдите эти два числа.

    Решение: Сумма всех трехзначных чисел равна  494 550. Если из неё вычесть     искомые     числа   х  и  у,     то      494 550 – х – у = 600х,     или у = 494 550 – 601х.  Тогда   100 ≤ 494 550 – 601х ≤ 990,   откуда   х = 822, у = 528.

ΙΙ. Линейные системы.

9. Школьник написал три различных натуральных числа. Сложил большее со средним – получилось 2004, а когда из среднего вычел меньшее, то получил 1000. Что это за числа?

Решение: Пусть написанные числа  а, в  и  с; такие, что  а < в < с. По условию получаем систему:           Из   системы   следует:

в = 1000 + а,   значит   а<1000.  Пусть   с = в + Δ,  тогда  2в = 2004 – Δ  и значит  в<1002.  Отсюда следует в = 1001,  а = 1, с = 1003.

10. Библиотекарь получил  10 000 рублей на приобретение 100 книг (без сдачи). В магазине он определил, что для библиотеки подходят книги стоимостью 30, 80 и 120 рублей. Сколькими способами библиотекарь может приобрести книги?

     Решение:  Возьмём  х книг по 120 рублей,  у – по 80 рублей, z – по 30 рублей. Тогда        Исключим  z:  9х + 5у= 700.    Отсюда  х = 5k,  у = 140 – 9k,  z = 4k – 40. Какие значения k удовлетворяют условию задачи?  140 – 9k ≥ 0,  4k – 40 ≥ 0,  10 ≤ k ≤ 15. Всего 6 значений.  Ответ: 6.

11. В классе 35 учеников. Они собрали библиотеку для младших школьников. Для этого каждый принес от  4  до  6  книг – и получилось  180 книг. Каких учеников в классе больше – тех, кто принес по  4, или тех, кто принес по 6 книг? Укажите одно из распределений учеников по количеству принесенных книг.

     Решение: Пусть  х  учеников принесли по 4 книги,  у – по 5, z – по 6 книг. Имеем:       Исключим    х:   у = 40 – 2z.    Тогда  х = 35 – у – z = z – 5 < z (ответ на первый вопрос задачи). При любом   z  ( 5 < z ≤ 20)  получаем     решение.   Например, z = 20, у = 0, х = 15.

     Ответ на первый вопрос можно получить сразу: тех, кто принес 6 книг больше, потому что среднее число книг  (на одного ученика) больше 5.

12.  Разменяйте  25 тугриков монетами по 1, 3, 5 тугриков так, чтобы их было ровно 10.

     Решение:   Пусть  а, в, с – количество монет достоинством в 1, 3, 5 тугриков соответственно.  Тогда      Вычитая уравнения,  получим  2в + 4с = 15. Левая часть четная, правая нечетная, что невозможно ни при каких целых  в и  с. Ответ: такой размен невозможен.

13. Каждым выстрелом по мишени стрелок выбивал  8,  9  или  10  очков. Он произвел более  11 выстрелов и выбил 100 очков. Сколько он сделал выстрелов и с каким результатом?

     Решение:  Пусть х,  у,  z – количество выстрелов с результатом  8,  9,  10 очков соответственно:  8х + 9у + 10z = 100. Если бы каждым выстрелом  стрелок  выбивал  по  8 очков,  то  выбил бы  не  более 100:      8х + 8у + 8z  <  100,     поэтому      Таким образом, общее количество выстрелов 12.

      Из системы      исключим  х:   y + 4z = 4,  откуда  z = 1,  у = 2, х = 9.  Ответ: 9, 2, 1.

14.  Мальчик коллекционирует значки, все время пересчитывает и раскладывает по темам: памятные даты, города, спорт. Если бы количество первых (даты) у него увеличилось вдвое, а вторых (города) – в 11 раз, то всего значков стало бы 6 000. А вот если бы вдвое увеличить «города» и вчетверо – спортивные, то получилось бы даже 10 000. Каких значков у мальчика больше – «спорта»  или  «городов»?

     Решение:  Обозначим за  а,  в,  с  количество значков по каждой теме. Тогда       Исключая  а,  получим  с = в + 2000 > в. Ответ: спортивных значков больше.

15.  Некто купил 30 птиц за 30 монет, уплатив за каждые 3 воробья по 1 монете, за каждые 2 горлицы – тоже по 1 монете, а за каждого голубя – по 2 монеты. Сколько куплено птиц каждого вида?

     Решение:  Пусть  х,  у,  z – количество воробьев, горлиц и голубей соответственно. Тогда     Исключая из системы  х, получим   у = 120 – 10z.   Подставим в первое уравнение:  х = 9z – 90. Из неравенств   1 ≤ х ≤ 29,   1 ≤ у ≤ 29  получим  z = 11,  откуда  х = 9,  у = 10.  Ответ:  9  воробьев,  10  горлиц  и  11  голубей.

ΙΙΙ. Нелинейные уравнения.

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

1). Преобразование в произведение.

17.   Решите в целых числах уравнение   (4х – 1) (2у + 1) = 15.

     Решение: Так как выражения в обеих скобках целые, то они должны   быть дополнительными делителями числа 15.

     Делители числа 15: ± 1; ± 3; ± 5; ± 15. Переберём случаи:

                 1) При  4х – 1 = 1; -3; 5 или -15 число  х  не является целым. Эти

                     варианты отпадают.

                 2) Если  4х – 1 = -1, то 2у + 3 = - 15. Получаем:  х = 0; у = -9.

                 3) Аналогично при 4х – 1 = 3:   х = 1;  у = 1;

                                          при 4х – 1 = -5:   х = -1;  у = -3;

                                          при 4х – 1 = 15:   х = 4;  у = -1.

     Ответ: ( 0; -9); ( 1; 1); ( -1; -3); ( 4; -1).

18.  Решите в целых числах уравнение   ху – 2х + 3у = 16.

      Решение: Данное уравнение равносильно следующим:

х (у – 2) + 3у – 6 = 10,

(х + 3)(у – 2) = 10.

     Из последнего уравнения следует, что числа  х + 3  и   у – 2  - делители числа 10. Число 10 имеет восемь делителей: ± 1, ± 2, ± 5, ± 10. Отсюда восемь систем уравнений:

    Следовательно,  данное   уравнение   имеет   восемь  целых  решений:  (-2,12),  (-4,-8), (-1,7),  (-5,-3), (2,4), (-8,0), (7,3), (-13,1).

19. Решить   уравнение       относительно р,  где  р – данное простое число.

     Решение:  Отметим, что   х ≠ 0,  у ≠ 0,  р ≠ 0.  Имеем:

ху = рх + ру,

(х – р)(у – р) = р2.

    Так  как  р – простое  число,  то  р2 имеет шесть делителей:  ± 1, ± р, ± р2. Следовательно, данное уравнение имеет пять целых решений: (р+1, р+р2),  (р–1, р–р2),  (2р, 2р),  (р+р2, р+1),  (р–р2, р–1).

2). Метод проб.

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

      Решение: Допустим сначала, что  х ≤ у ≤ z. Рассмотрим следующие случаи: а)  х=1; уравнение не имеет решений, так как  

                  б)  х=2;   имеем         (у – 2)(z – 2) = 4.  

                   Так   как    0 ≤ у – 2 ≤ z – 2,   то    имеется   два   решения:

                  (2, 3, 6),  (2, 4, 4).

                 в)  х=3;   после   преобразования   получим    

                 Если    у=3,   то   z=3.   Получим   решение   (3, 3, 3).

                 Если   у ≥ 4,  то z ≥ 4.    Отсюда    следует,   что

  Это невозможно.

                 г)  х ≥ 4;  при  этом   у ≥ 4  и  z ≥ 4, и  следовательно,

  Это невозможно.

        Итак,  при    х ≤ у ≤ z   уравнение  имеет  три   решения:   (2, 3, 6),  (2, 4, 4),  (3, 3, 3).  Снимая первоначальное допущение, получим еще семь решений:  (4, 2, 4),  (4, 4, 2),  (2, 6, 3),  (3, 2, 6),  (3, 6, 2),  (6, 2, 3), (6, 3, 2).

21. Найти пары натуральных чисел, для которых сумма каждого из них с числом 1 делится на другое число.

     Решение:  Сначала предположим, что х ≤ у. Из условия задачи следует, что  х +1  и  у + 1 соответственно делятся  на  у  и  х.  Следовательно,   произведение  (х+1)(у+1) = ху + х + у + 1  делится  на  ху.   Отсюда    х+у+1  делится на  ху, или  х+у+1 = рху,  где  р  

     Так  как   х ≥ 1  и  у ≥ 1,   имеем       Следовательно, целое число р может принять одно из трех значений:  1,  2,  3.

      а) р=3, получим уравнение     решение которого  (1, 1).  б) р=2;      решений нет.

     в) р=1;     Получаем решение  (2, 3).

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