Решение диофантовых уравнений первой и второй степени

54=37

1+17, остаток от деления     17 = 54-37 1 

Далее, следуя алгоритму, получаем:

37 = 17

2+3 ,    3 = 37-17 2

17 = 3

5+2 ,    2 = 17- 3 5

3 = 2

1+1 ,    1 = 3 - 2 1 

После нахождения единицы выражаем через неё значения а и b: 

                                                     1 = 3 – (17-3 5);

                                                     1 = 17- 3 4;

 1 = 17 - (37- 17

2) 4;

                                                     1 = 17 - 37 4+17 8;

                                                     1 = 17 9 – 37 4;

   1 = (54- 37

1) 9 - 37 4;

                                                     1 = 54 9 - 37 9 - 37 4;

                                                     1 = 54 9 - 37 13

                                                     1 = 54х + 37у

Следовательно,  х₀ = 9, у₀ = -13. Значит, данное уравнение имеет следующее решение  . 

    Пример  2. Требуется найти целое решение уравнения 15x + 37y = 1.

    1-й  метод. Воспользуемся разложением  единицы:

    1 = 15*5 + 37*(-2).Ответ:  x = 5, y = -2.

    2-й  метод. Применяя алгоритм Евклида,  имеем: 37 = 15*2 + 7, 15 = 2*7 + 1. Отсюда    1 = 15 – 2*7 = 15 – 2(37 – 15*2) = 15*5 + (-2)*37. Тогда x_о = 5, y_о = - 2. Общее решение уравнения есть система . 

    Пример  3. В уравнении 16x + 34y = 7, НОД (16, 34) = 2  и 7 не делится на 2,то нет целых решений.  [5] 
 
 
 
 
 
 
 
 

    2.2  Цепная дробь

    Одним из применений алгоритма Евклида  является представление дроби  в виде

       

    Где q₁ – целое число, а q₂, … ,q_n – натуральные числа. Такое выражение называется цепной (конечной непрерывной) дробью.

Уравнение:

с взаимно простыми коэффициентами a и b имеет решение

,  ,

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

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

Если для заданной цепной дроби с последовательными  частными q₁, q₂,…,q_n несократимые дроби

, , …,

являются результатами свертывания подходящих дробей ,    , и т.д. , порядка 1, 2, …, n соответственно,то

, , …, n.

При k=n получаем :

,

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

.

Умножая обе  части последнего равенства на (-1)ⁿ, имеем

,

То есть пара чисел  , , где n-порядок цепной дроби, является решением уравнения .  

    Пример.  Для перевозки большого количества контейнеров по 170 кг и по 190 кг выделены трехтонные машины. Можно ли ими загружать машины полностью?

    Решение:

      Пусть х и у количество контейнеров по 170 и 190 кг соответственно, тогда имеем уравнение

    170х+190у=3000

    После сокращения на 10 уравнение выглядит так,

    17х+19у=300.

    Для нахождения частного решения воспользуемся  разложением дроби  в цепную дробь

    

    Свернув предпоследнюю подходящую к ней  дробь в обыкновенную

    

    Частное решение данного уравнения имеет вид

    х₀= (-1)⁴300*9=2700,  у₀=(-1)⁵300*8=-2400,

    а общее задается формулой

    х=2700-19k,       y= -2400+17k.

    откуда получаем условие на параметр k

    

    Т.е. k=142, x=2,  y=14. .[6] 
 
 

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

  Данный  метод и все последующие применяются к решению диофантовых уравнений второй степени.

  Задача 1. Решить в целых числах уравнение

x + y = xy.

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

(x - 1)(y - 1) = 1.

Произведение  двух целых чисел может равняться 1 только в том случае, когда оба они равны 1. Т. е. исходное уравнение равносильно совокупности

с решениями (0,0) и (2,2).  

  2.4 Использование четности 

  Задача 2. Решить в простых числах уравнение

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

  a) Пусть x - нечетное число. Подстановка x = 2t + 1 приводит исходное уравнение к виду

(2t + 1)² - 2y² = 1,

или

2y² = 4t(t + 1).

Следовательно, 2 | y². Так как y - простое число, то y = 2. Отсюда

  b) Пусть x - четное число. Так как x - простое число, то x = 2. Следовательно, т. е. уравнение неразрешимо в простых числах.

  Следовательно, уравнение имеет в классе простых  чисел единственное решение (3;2).    

  2.5 Другие методы решения диофантовых уравнений 

  Задача 3. Доказать, что уравнение

  имеет бесконечно много решений в натуральных  числах.

  Решение. Нетрудно заметить, что (3,2) - одно из решений исходного уравнения. С другой стороны из тождества

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

следует, что  если (x, y) - решение данного уравнения, то пара (x² + 2y² , 2xy) также является его решением. Используя этот факт, рекуррентно определим бесконечную последовательность (x_n , y_n) различных решений исходного уравнения:

(x₁ , y₁) = (3,2)   и   x_n+1 = x_n² + 2y_n²,     y_n+1 = 2x_ny_n,     n Î N^*.  

  Задача 4. Доказать, что уравнение

x(x + 1) = 4y(y + 1)

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

  Решение. Нетрудно заметить, что исходное уравнение равносильно уравнению

x² + x + 1 = (2y + 1)².

Следовательно, x² < (2y + 1)² < (x + 1)² или x < 2y + 1 < x + 1. Полученное противоречие доказывает требуемое утверждение.  

  Задача 5. Решить в целых числах уравнение

x + y = x² - xy + y².

  Решение. Положим t = x + y. Так как

то должно выполняться неравенство     откуда t Î [0;4]. [7] 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Заключение: 

    Современное обозначение непрерывных дробей предложил выдающийся учёный Христиан Гюйгенс (1629-1695).

    К цепным дробям Гюйгенс обратился  при построении планетария в Париже. Он хотел получить наилучшее приближение  для отношения периодов обращения  планет. Эти отношения и отношения  чисел зубцов соответствующих связанных  между собой шестерён планетария должны были совпадать. Но числа зубцов шестерен по техническим причинам не могут быть очень большими. Необходимо было так их подобрать, чтобы полученные отношения как можно меньше отличались от истинных. Гюйгенс обратился к цепным дробям и с их помощью нашел решение стоящей перед ним задачи.

    В заключении отметим преимущества и  недостатки цепных дробей по сравнению, например, с десятичными. Удобство заключается в том, что их свойства не связаны ни с какой системой счисления. По этой причине цепные дроби эффективно используются в теоретических исследованиях. Но широкого практического применения они не получили, так как для них нет удобных правил выполнения арифметических действий, которые имеются для десятичных дробей. [3]

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

    Для начала выберем пять случайных решений: 1=< a,b,c,d=<30. Вообще говоря, мы можем использовать меньшее ограничение для a,b,c,d. 
 

 

    1-е  поколение хромосом и их содержимое. 

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

    Главное свойство диофантовых уравнений  в том, что мы не перебираем все  варианты решений подряд, а приближаемся от случайно выбранных решений к лучшим. [8] 
 
 

    Список  литературы 
 

1. Журнал  «Квант» 1970г. №7
2. «Энциклопедия юного математика» 520 с.
3. Виленкин Н.Я. «За страницами учебника математики» (10-11 класс).- Москва:          «Просвещение» 1996-320 с.
4. http://festival.1september.ru/articles/417558/
5. Шыныбеков Н.А. «Алгебра 8» Алматы «Атамұра» 2004-272 с.
6. И.Н.Сергеев «Примени математику» 1989г.- 240 с.
7. math.ournet.md
8. http://ilib.mirror1.mccme.ru/djvu/serp-int_eq.htm
9. Кожегельдинов С.Ш. «Некоторые элементы теории диофантовых уравнений в упражнениях и задачах»
10. Пичугин Л.Ф. «За страницами учебника алгебры», М., 1990г., 224с.
11. Глейзер Г.И. «История математики в школе 10-11»,  351с
12. Гусев В.А., Орлов А.И. и др. «Внеклассная работа по математике в 6-8 классах»,  М., 1984г., 286 с.
13. Петраков И.А. «Математика для любознательных»,  М., 2000г. 256с.
14. http://bse.sci-lib.com/article028554.html
15. http://bars-minsk.narod.ru/teachers/diofant.html