stringtranslate.com

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

Нахождение всех прямоугольных треугольников с целыми длинами сторон эквивалентно решению диофантова уравнения.

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

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

Слово « диофант» относится к эллинистическому математику III века Диофанту Александрийскому , который исследовал подобные уравнения и был одним из первых математиков, введших символизм в алгебру . Математическое исследование диофантовых задач, начатое Диофантом, теперь называется диофантовым анализом .

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

Примеры

В следующих диофантовых уравнениях w, x, y и z являются неизвестными, а остальным буквам даны константы:

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

Одно уравнение

Простейшее линейное диофантово уравнение имеет вид

abc
Это диофантово уравнение имеет решение (где x и y — целые числа) тогда и только тогда, когда c кратно наибольшему общему делителю a и b . Более того, если ( x, y ) — решение, то остальные решения имеют вид ( x + kv, yku ) , где k — произвольное целое число, а u и v — частные a и b (соответственно) по наибольшему общему делителю a и b .

Доказательство: если d является наибольшим общим делителем, тождество Безу утверждает существование целых чисел e и f таких, что ae + bf = d . Если c кратно d , то c = dh для некоторого целого числа h и ( eh, fh ) является решением. С другой стороны, для каждой пары целых чисел x и y наибольший общий делитель d чисел a и b делит ax + на . Таким образом, если уравнение имеет решение, то c должно быть кратно d . Если a = ud и b = vd , то для каждого решения ( x, y ) мы имеем

( x + kv, yku )
uvпростылемма Евклидаvx 2x 1k

Китайская теорема об остатках

Китайская теорема об остатках описывает важный класс линейных диофантовых систем уравнений: пусть k попарно взаимно простых целых чисел больше единицы, k произвольных целых чисел и N - произведение. Китайская теорема об остатках утверждает, что следующая линейная диофантова система имеет ровно одно решение такой, что 0 ≤ x < N и что другие решения получаются добавлением к x кратного N :

Система линейных диофантовых уравнений

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

Am × n , Xматрица-столбецn × 1 , а Cm × 1 .

Вычисление нормальной формы Смита A дает две унимодулярные матрицы (то есть матрицы, которые обратимы в целых числах и имеют определитель ±1) U и V соответствующих размеров m × m и n × n , такие, что матрица

b i,iik
y iV −1 Xd iD = UC

Эта система эквивалентна данной в следующем смысле: матрица-столбец целых чисел x является решением данной системы тогда и только тогда, когда x = Vy для некоторой матрицы-столбца целых чисел y такой, что By = D .

Отсюда следует, что система имеет решение тогда и только тогда, когда b i,i делит d i для ik и d i = 0 для i > k . Если это условие выполнено, решения данной системы будут

h k +1 , …, h n

Нормальную форму Эрмита можно также использовать для решения систем линейных диофантовых уравнений. Однако нормальная форма Эрмита не дает решений напрямую; Чтобы получить решения нормальной формы Эрмита, необходимо последовательно решить несколько линейных уравнений. Тем не менее, Ричард Зиппель писал, что нормальная форма Смита «несколько больше, чем это на самом деле необходимо для решения линейных диофантовых уравнений. Вместо того, чтобы приводить уравнение к диагональной форме, нам нужно только сделать его треугольным, что называется нормальной формой Эрмита. Нормальную форму Эрмита значительно легче вычислить, чем нормальную форму Смита». [6]

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

Однородные уравнения

Однородное диофантово уравнение — это диофантово уравнение, определяемое однородным полиномом . Типичным таким уравнением является уравнение Великой теоремы Ферма.

Поскольку однородный полином от n неопределенных определяет гиперповерхность в проективном пространстве размерности n - 1 , решение однородного диофантова уравнения аналогично нахождению рациональных точек проективной гиперповерхности.

Решение однородного диофантова уравнения, как правило, является очень сложной задачей, даже в простейшем нетривиальном случае трех неопределенных (в случае двух неопределенных проблема эквивалентна проверке, является ли рациональное число d - й степенью другого рационального числа) . Свидетельством сложности проблемы является Великая теорема Ферма (при d > 2 не существует целочисленного решения приведенного выше уравнения), решение которой потребовало более трех столетий усилий математиков.

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

Для третьей степени существуют общие методы решения, которые работают почти со всеми уравнениями, встречающимися на практике, но не известен алгоритм, работающий для каждого кубического уравнения. [8]

Вторая степень

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

Чтобы доказать отсутствие решения, можно сократить уравнение по модулю p . Например, диофантово уравнение

не имеет другого решения, кроме тривиального решения (0, 0, 0) . Фактически, разделив x, y и z на их наибольший общий делитель , можно предположить, что они взаимно просты . Квадраты по модулю 4 конгруэнтны 0 и 1. Таким образом, левая часть уравнения конгруэнтна 0, 1 или 2, а правая часть конгруэнтна 0 или 3. Таким образом, равенство можно получить только если x, y и z все четны и, следовательно, не взаимно просты. Таким образом, единственным решением является тривиальное решение (0, 0, 0) . Это показывает, что на круге радиуса с центром в начале координат не существует рациональной точки .

В более общем смысле, принцип Хассе позволяет решить, имеет ли однородное диофантово уравнение второй степени целочисленное решение, и вычислить решение, если оно существует.

Если известно нетривиальное целочисленное решение, все остальные решения можно получить следующим образом.

Геометрическая интерпретация

Позволять

— однородное диофантово уравнение, где — квадратичная форма (т. е. однородный многочлен степени 2) с целыми коэффициентами. Тривиальное решение — это решение, в котором все значения равны нулю. Если – нетривиальное целочисленное решение этого уравнения, то – однородные координаты рациональной точки гиперповерхности, определяемой Q . Обратно, если – однородные координаты рациональной точки этой гиперповерхности, где – целые числа, то – целочисленное решение диофантова уравнения. Более того, все целочисленные решения, определяющие данную рациональную точку, представляют собой последовательности вида

где k — любое целое число, а d — наибольший общий делитель числа

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

Параметризация

Пусть теперь это целочисленное решение уравнения. Поскольку Q — многочлен второй степени, линия, проходящая через A , пересекает гиперповерхность в одной другой точке, что рационально тогда и только тогда, когда линия рациональна (то есть, если линия определяется рациональными параметрами). Это позволяет параметризовать гиперповерхность линиями, проходящими через A , а рациональными точками являются те, которые получены из рациональных прямых, то есть те, которые соответствуют рациональным значениям параметров.

Точнее, можно поступить следующим образом.

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

который имеет рациональную точку

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

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

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

В общем случае рассмотрим параметрическое уравнение прямой, проходящей через R :

Подставив это в q , получим полином второй степени по x1 , который равен нулю при x1 = r1 . Таким образом, оно делится на x 1r 1 . Частное является линейным по x 1 и может быть решено для выражения x 1 как частного двух многочленов степени не выше двух in с целыми коэффициентами:

Подставив это в выражения для , получим для i = 1, …, n − 1 ,

где – многочлены степени не выше двух с целыми коэффициентами.

Тогда можно вернуться к однородному случаю. Пусть для i = 1, …, n ,

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

Точка проективной гиперповерхности, определяемая Q , является рациональной тогда и только тогда, когда ее можно получить из рациональных значений As — однородных многочленов; точка не меняется, если все t i умножить на одно и то же рациональное число. Таким образом, можно предположить, что это взаимно простые целые числа . Отсюда следует, что целочисленными решениями диофантова уравнения являются в точности такие последовательности , где для i = 1, ..., n ,

где k — целое число, — взаимно простые целые числа, а d — наибольший общий делитель n целых чисел .

Можно было бы надеяться, что взаимнопростость t i может означать, что d = 1 . К сожалению, это не так, как показано в следующем разделе.

Пример пифагорейских троек

Уравнение

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

Чтобы точно получить формулу Евклида, мы начинаем с решения (−1, 0, 1) , соответствующего точке (−1, 0) единичной окружности. Линия, проходящая через эту точку, может быть параметризована ее наклоном:

Поместив это в уравнение окружности

каждый получает

Деление на x + 1 дает результат

что легко решить в x :

Следует

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

где k — любое целое число, s и t — взаимно простые целые числа, а d — наибольший общий делитель трех числителей. Фактически, d = 2, если s и t оба нечетны, и d = 1, если один из них нечетный, а другой четный.

Примитивные тройки — это решения, где k = 1 и s > t > 0 .

Это описание решений немного отличается от формулы Евклида, поскольку формула Евклида рассматривает только те решения, у которых все x, y и z положительны, и не делает различия между двумя тройками, которые отличаются заменой x и y .

Диофантовый анализ

Типичные вопросы

Вопросы, задаваемые при диофантовом анализе, включают:

  1. Есть ли какие-либо решения?
  2. Существуют ли какие-либо решения помимо тех, которые легко найти путем проверки ?
  3. Существует ли конечное или бесконечное число решений?
  4. Все ли решения можно найти теоретически?
  5. Можно ли на практике вычислить полный список решений?

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

Типичная проблема

Данная информация состоит в том, что возраст отца на 1 меньше, чем в два раза, чем возраст его сына, и что цифры AB , составляющие возраст отца, перевернуты в возрасте сына (т. е. BA ). Это приводит к уравнению 10 A + B = 2(10 B + A ) − 1 , таким образом 19 B − 8 A = 1 . Проверка дает результат A = 7 , B = 3 , и, таким образом, AB равен 73 годам, а BA равен 37 годам. Легко показать, что не существует другого решения с целыми положительными числами A и B меньше 10.

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

17 и 18 веков

В 1637 году Пьер де Ферма нацарапал на полях своего экземпляра «Арифметики» : «Невозможно разделить куб на два куба, или четвертую степень на две четвертые степени, или вообще любую степень, превышающую вторую, на две, как полномочия». Выражаясь более современным языком: «Уравнение a n + b n = c n не имеет решений ни при каком n больше 2». Вслед за этим он написал: «Я обнаружил поистине чудесное доказательство этого положения, для которого эти поля слишком узки». Однако такое доказательство ускользало от математиков на протяжении веков, и поэтому его утверждение стало известно как Великая теорема Ферма . Лишь в 1995 году это было доказано британским математиком Эндрю Уайлсом .

В 1657 году Ферма попытался решить диофантово уравнение 61 x 2 + 1 = y 2 (решенное Брахмагуптой более 1000 лет назад). В конечном итоге уравнение было решено Эйлером в начале 18 века, который также решил ряд других диофантовых уравнений. Наименьшее решение этого уравнения в натуральных числах — x = 226153980 , y = 1766319049 (см. метод Чакравалы ).

Десятая проблема Гильберта

В 1900 году Дэвид Гильберт предложил разрешимость всех диофантовых уравнений как десятую из своих фундаментальных проблем . В 1970 году Юрий Матиясевич решил его отрицательно, опираясь на работы Джулии Робинсон , Мартина Дэвиса и Хилари Патнэм , чтобы доказать, что общего алгоритма решения всех диофантовых уравнений не может существовать .

Диофантова геометрия

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

Современные исследования

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

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

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

Этот подход в конечном итоге привел к доказательству Эндрю Уайлсом в 1994 году Великой теоремы Ферма , сформулированной без доказательства около 1637 года. Это еще одна иллюстрация сложности решения диофантовых уравнений.

Бесконечные диофантовы уравнения

Пример бесконечного диофантового уравнения:

nn,тэта-функциямиn[9]
n

Экспоненциальные диофантовые уравнения

Если в диофантовом уравнении есть дополнительная переменная или переменные, выступающие в качестве показателей степени , то это экспоненциальное диофантово уравнение. Примеры включают уравнение Рамануджана-Нагеля , 2 n - 7 = x 2 , и уравнение гипотезы Ферма-Каталана и гипотезы Била , a m + b n = c k с ограничениями неравенства на показатели. Общая теория таких уравнений не существует; были рассмотрены конкретные случаи, такие как гипотеза Каталана . Однако большинство из них решаются с помощью специальных методов, таких как теорема Штормера , или даже методом проб и ошибок .

Смотрите также

Примечания

  1. ^ «Цитаты Харди». Gap.dcs.st-and.ac.uk. Архивировано из оригинала 16 июля 2012 года . Проверено 20 ноября 2012 г.
  2. ^ Эверест, Г.; Уорд, Томас (2006), Введение в теорию чисел, Тексты для аспирантов по математике, том. 232, Спрингер, с. 117, ISBN 9781846280443.
  3. ^ Уайлс, Эндрю (1995). «Модулярные эллиптические кривые и Великая теорема Ферма» (PDF) . Анналы математики . 141 (3): 443–551. дои : 10.2307/2118559. JSTOR  2118559. OCLC  37032255.
  4. ^ Элкис, Ноам (1988). «На А4+В4+С4=D4» (PDF) . Математика вычислений . 51 (184): 825–835. дои : 10.2307/2008781. JSTOR  2008781. МР  0930224.
  5. ^ Фрай, Роджер Э. (1988). «Нахождение 95800 4 + 217519 4 + 414560 4 = 422481 4 на соединительной машине». Proceedings of Supercomputing 88, Том II: Наука и приложения . стр. 106–116. дои : 10.1109/SUPERC.1988.74138.
  6. ^ Ричард Зиппель (1993). Эффективное полиномиальное вычисление . Springer Science & Business Media. п. 50. ISBN 978-0-7923-9375-7.
  7. ^ Александр Бокмайр, Фолькер Вайспфеннинг (2001). «Решение числовых ограничений». У Джона Алана Робинсона и Андрея Воронкова (ред.). Справочник по автоматизированному рассуждению , том I. Elsevier и MIT Press. п. 779. ИСБН 0-444-82949-0. (Эльзевир) (MIT Press).
  8. Ковачич, Джеральд (8 мая 1985 г.). «Алгоритм решения линейных однородных дифференциальных уравнений второго порядка» (PDF) . Основной . Архивировано (PDF) из оригинала 16 апреля 2019 г.
  9. ^ "A320067 - Оайс" .

Рекомендации

дальнейшее чтение

Внешние ссылки