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

      , .

     Покажем несколько алгоритмов для нахождения решения.

Способ 1.

     Пусть

     Рассмотрим  два случая:

           а). не делится на . В этом случае решений нет по теореме 2.

           б). делится на , поделим на .

      ;

      .

     Таким образом получили новое ЛДУ, с тем же множеством решений, но уже со взаимно-простыми коэффициентами. Поэтому далее мы будем рассматривать именно такие уравнения.

     Рассмотрим  , .

      , перейдем к сравнению,

      .

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

      ; подставим в уравнение.

      ;

      ;

      , причем  .

     Обозначим .

     Тогда общее решение можно найти  по формулам: , где .

     Пример.  , .

     Найдем  решение сравнения 

;

     

;

     

, т.е. 

     

  .

     

;

     

     Получили  общее решение: , где .

Способ 2.

     Рассмотрим  еще один способ нахождения решения ЛДУ с двумя неизвестными, а для этого рассмотрим уравнение вида . Уравнения такого вида называются линейными однородными диофантовыми уравнениями (ЛОДУ). Выражая неизвестную , через неизвестную приходим к . Так как x должен быть целым числом, то , где - произвольное целое число. Значит . Решениями ЛОДУ являются n-ки вида , где . Множество всех таких n-ок называется общим решением ЛОДУ, любая же конкретная пара из этого множества называется частным решением.

     Рассмотрим  теперь уравнение  , . Пусть n-ка его частное решение, а множество n-ок общее решение соответствующего ЛОДУ. Докажем предложение.

     Общее решение ЛДУ  , задается уравнениями , где .

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

      - однородное уравнение. Пишем  сразу общее решение:  , откуда получаем:

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

     Встает  вопрос о нахождении частного решения  ЛДУ.

     

     По  теореме о линейном разложении НОД, это означает, что найдутся такие  и из множества целых чисел, что , причем эти  и мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство на и получим: , т.е. , .

     Таким образом, для нахождения общего решения  находим общее решение ЛОДУ, частное  решение ЛДУ и их складываем.

     Замечание: особенно этот способ удобен, когда  или . Если, например, , , тогда n-ка , очевидно, будет частным решением ЛДУ. Можно сразу выписывать общее решение. 

     Пример. , .

     Найдем  частное решение. Используем алгоритм Евклида.

      ;

     

     Получаем  линейное разложение НОД:

      , т.е  .

      ,

     Получили  общее решение: , где .

     Как видим, получили решение, не совпадающее с решением, найденным первым способом.

     Обозначим и получим , т.е эти решения равносильны.

Способ 3.

     Еще один способ опирается на теорему:

     Пусть - произвольное решение диофантова уравнения

     

, , тогда

множество решений  уравнения в целых числах совпадает  с множеством пар  , где , , где t – любое целое число.

  Перейдем  теперь к решению ЛДУ с  неизвестных, т. е. уравнений вида

  

  где все коэффициенты и неизвестные  – целые числа и хотя бы одно . Для существования решения по теореме 2, необходимо, чтобы

  Положив

перейдем к  равносильному уравнению 

(*),

где . Пусть ,   - два ненулевых числа, таких, что Для определенности предположим, что , Разделив с остатком на , получим представление . Заменив на в уравнении (*), приведем его к виду

  Перепишем это уравнение в виде

  

  (**)

  где

  

,  .

  Очевидно, что решения уравнения (*) и (**) связаны  между собой взаимно однозначным  соответствием и, таким образом, решив уравнение (**), несложно найти все решения уравнения (*). С другой стороны отметим, что

  

 

  Отметим также, что 

  

  Следовательно, за конечное число шагов уравнение (*) приведется к виду

  

(***)

  где числа    (i = 1,...,n), которые не равны нулю, равны между собой по абсолютной величине. Из соотношения следует, что числа могут принимать только значения 0,±1, причем не все из них равны нулю. Предположим, для определенности, . Тогда уравнение (***) имеет следующее решение:

  

где t₂, t₃, ..., t_n - произвольные целые числа. Отсюда, учитывая проведенные замены, получается и решение уравнения (*). Отметим, что при получении решения уравнения (***) использовался лишь факт, что , поэтому, при выполнении алгоритма можно остановиться на том шаге, когда хотя бы один из коэффициентов станет равным  ±1.

 Примеры решений задач.

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

4x - 6y + 11z = 7,  (4,6,11)=1.

  Разделив  с остатком -6 на 4, получим -6 = 4(-2) + 2. Представим исходное уравнение в виде

4(x - 2y) + 2y + 11z = 7.

После замены x¢ = x - 2y это уравнение запишется следующим образом

4x¢ + 2y + 11z = 7.

Учитывая, что 11 = 2·5 + 1, преобразуем последнее уравнение:

4x¢ + 2(y + 5z) + z = 7.

Положив y¢ = y + 5z, получим

4x¢ + 2y¢ + z = 7.

Это уравнение  имеет следующее решение: x¢, y¢ - произвольные целые числа, z = 7 - 4x¢ - 2y¢.

Следовательно y = y¢ - 5z = 20x¢ + 11y¢ - 35,  x = x¢ + 2y = 41x¢ + 22y¢ - 70.

  Таким образом, решение исходного уравнения  имеет вид 

   , где , - произвольные целые числа.

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

  

  Разделим 5 на -4 с «остатком», , преобразуем исходное уравнение к виду

  

.

  Заменив получим , следовательно

      , является решением данного

     уравнения.

Рассмотрим такие  диофантовы уравнения:

x²-Dy²=1.

Мы будем искать минимальные (по x) решения этого  уравнения в натуральных x и y. Например, для D=13 минимальное решение такое:

649²-13*180²=1.

Легко показать, что для D - полного квадрата решений не существует.

Рассмотрим минимальные  решения D <= 10:

3² - 2*2²=1;

2² - 3*1²=1;

9² - 5*4²=1;

5² - 6*2²=1;

8² - 7*3²=1;

3² - 8*1²=1;

19² - 10*6²=1.

Нас будут интересовать только те D, минимальные решения  которых больше всех ему предшествующих. Здесь это 2, 5, 10.

Среди всех D≤1000 не полных квадратов, найдите те у  которых минимальное решение (по x) больше (по x) всех минимальных решений для меньших D. В ответе укажите сумму таких D. 
 

О «многоугольных числах»  Диофанта. 

Александрийская математика от Евклида и до Аполлония носит ярко выраженный геометрический характер: «логистика», т. е. вычислительная математика.

     Треугольными  числами в арифметике называются

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

Это будут а₁ = 1, а₂ = 1 + 2 = 3, а₃ =

= 1 + 2 + 3 - 6,..., .

Каждое треугольное  число может быть изображено в  виде треугольника, число углов которого (3) одновременно дает и «(количество) углов» соответствующего числа. Вместо натурального ряда мы можем взять и более общий случай арифметической прогрессии, у которой первый член и

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

же стоит подумать, почему же ею занимались два античных математика, разделенных некоторым (даже не вполне определенным) временем. Кроме того, аналогичные вопросы  интересовали математиков индийских, средне-

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

.

Выполняя все  обозначенные действия, мы получаем  

 

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

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