Теория чисел. Диофантовы уравнения



В данной статье приведены исследования в области теории чисел, а именно в области линейных диофантовых уравнений. Здесь будут представлены обнаруженные методы решения и свойства.

Ключевые слова: уравнение, линейная сумма, решение.

Введение. Диофантовы уравнения знакомы науке уже давно. Первым, кто начал их активное изучение, был Диофант Александрийский. Он был одним из первых математиков, который ввёл символику в алгебру, позднее полностью развитую французским математиком Франсуа Виеттом, что позволило значительно ускорить развитие математики. Математическое исследование диофантовых проблем, начатое Диофантом, теперь называют диофантовым анализом. В изучении диофантовых уравнений также принимали участие такие математики, как Пьер де Ферма, Леонард Эйлер, Андрей Колмогоров и многие другие.

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

Ручной перебор. Бесконечность решений

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

Первое что я сделал это представил уравнение в буквенном виде, я получил: , что является стандартным видом линейного диофантового уравнения. Далее я выразил :

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

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

В конце концов мы получили систему:

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

, где .

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

.

Теперь попробуем решить данное уравнение перебором через . Дойдя до значения , получаем решение: . Из этого следует, что линейное диофантово уравнение может иметь бесконечное множество решений.

Свойства коэффициентов.

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

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

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

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

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

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

Теорема о делителях линейной суммы.

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

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

Рассмотрим другой пример: , согласно частному случаю проверки уравнения на существование у него целых корней, также приведенному мной ранее, это уравнение не имеет целых решений. Разложим его на множители: , заметим, что множитель повторяется в каждом члене линейной суммы, но не повторяется в ее результате. Внимательно посмотрев на множители, мы увидим, что повторяющиеся множители это ничто иное как наибольший общий делитель (НОД) всех членов линейной суммы. Из этого можно сделать вывод о том, что, если результат линейной суммы, при разложении на множители содержит наибольший общий делитель всех ее членов, то уравнение имеет целые корни. Япроверил этот вывод на 100 уравнениях, 50 из которых имели целые решения, а остальные 50 соответственно нет. Данная гипотеза подтвердилось в каждом из случаев. Вероятность правдоподобности данной гипотезы составила сто процентов, что заставило меня искать ее доказательство. И оно было найдено.

Доказательство. Возьмем уравнение общего вида: , обозначим НОД за

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

Чтобы уравнение имело целые решения нужно, чтобы результат линейной суммы был целым числом, следовательно , а значит, что при разложении на множители содержит НОД всех членов линейной суммы. Теорема доказана.

Параметрический метод решения.

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

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

Далее вычтем из первого уравнения второе:

Выносим общие множители за скобки:

Переносим второй член суммы за знак равенства:

Если левая часть уравнения делится на 4 без остатка, то и правая тоже. Так как не кратно четырем, то mod 4). Из этого следует, что , отсюда , теперь подставим значение ) в исходное уравнение, получаем: , далее выразим имеем: Объединим запись:

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

Чтобы обобщить, давайте проделаем тоже самое для буквенной записи:

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

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

Алгоритм решения

1. Проверяем уравнение на существование у него целых корней при помощи Теоремы о делителях линейной суммы.
2. Находим любое решение уравнения ручным перебором.
3. Используем параметрический метод решения для получения всех возможных корней уравнения.

Обобщение

1. Параметрический метод решения:
2. Ручной метод поиска решений: одно из бесконечного множества решений диофантового уравнения можно найти ручным перебором любых значений или .
3. Теорема о делителях линейной суммы: если результат линейной суммы при разложении на множители содержит наибольший общий делитель всех её членов, то уравнение имеет целые корни.
4. Свойства коэффициентов:

1. Если в линейном диофантовом уравнении вида: , четное, четное, то обязательно четное, иначе уравнение не имеет целых решений.
2. Если в линейном диофантовом уравнении вида: , , то одним из бесконечного множества решений обязательно будет

Литература:

1. Diophantine equation, Wikipedia: сайт. [электронный ресурс] URL: https://en.wikipedia.org/wiki/Diophantine_equation(дата обращения: 11.02.2025).