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

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

Понятие диофантового уравнения

Давайте поговорим о диофантовых уравнениях. Что же это за зверь такой?

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

Вот, скажем, $x^2 + y^2 = z^2$ Знакомая картинка, правда? Это же теорема Пифагора, описывающая соотношение сторон в прямоугольном треугольнике. И если мы ищем целочисленные решения, то есть такие, где $x$, $y$ и $z$ – целые числа, – мы как раз и имеем дело с диофантовым уравнением. Такие решения, кстати, называются пифагоровыми тройками – например, (3, 4, 5) или (5, 12, 13).

В отличие от обычных алгебраических уравнений, где мы ищем решения в вещественных или комплексных числах, в диофантовых уравнениях нас интересуют только целые числа. Это, казалось бы, небольшое ограничение радикально меняет картину. Например, уравнение $x^2 + y^2 = 1$ имеет бесконечно много решений в вещественных числах – это же просто уравнение окружности с радиусом 1. А вот в целых числах решений всего четыре: (1, 0), (-1, 0), (0, 1), (0, -1). Чувствуете разницу?

Диофантовы уравнения бывают самых разных степеней. Линейные диофантовы уравнения вида $ax + by = c$ достаточно просты для анализа, и мы имеем чёткий алгоритм для нахождения их решений. А вот с уравнениями более высоких степеней всё становится гораздо сложнее. Возьмём, к примеру, знаменитое уравнение Ферма $x^n + y^n = z^n$ для $n > 2$. Доказательство Великой теоремы Ферма, утверждающей, что это уравнение не имеет нетривиальных целых решений, заняло математиков несколько столетий и потребовало мощнейшего математического аппарата.

Или вот ещё один пример: уравнение Пелля $x^2 - Dy^2 = 1$, где $D$ – натуральное число, не являющееся полным квадратом. Оказывается, оно всегда имеет бесконечно много решений в целых числах. И нахождение этих решений – уже совсем нетривиальная задача.

Общие принципы решения таких уравнений

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

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

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

Если уравнение можно представить в виде произведения, равного константе, то можно перебрать возможные значения множителей. Например, уравнение $xy = 12$ в целых числах. Поскольку $12 = 1 \cdot 12 = 2 \cdot 6 = 3 \cdot 4 = (-1) \cdot (-12)$ и так далее, мы можем найти все пары целых чисел $(x, y)$, которые удовлетворяют уравнению.

Модульная арифметика

Анализ уравнения по модулю некоторого числа $n$ может помочь определить, существуют ли вообще решения. Например, рассмотрим уравнение $x^2 + y^2 = z^2$. Легко заметить, что если остаток от деления $x$ на 4 равен 3, то $x^2 \equiv 1 \pmod{4}$ (квадратичный вычет). С учетом того, что число 3 является квадратичным вычетом по модулю 4, сумма двух квадратов даст либо 0, либо 1, либо 2 по модулю 4. В то же время квадрат $z$ может давать по модулю 4 либо 0, либо 1, поэтому мы имеем ограничения на решения уравнения. Давайте рассмотрим простой пример, где использование модульной арифметики помогает показать отсутствие целочисленных решений. Возьмём уравнение $x^2 + 3y = 7$

Допустим, существуют целые числа $x$ и $y$, удовлетворяющие этому уравнению. Рассмотрим это уравнение по модулю 3. Это означает, что мы интересуемся только остатками от деления на 3. Запишем это так $x^2 + 3y \equiv 7 \pmod{3}$

Так как $3y$ делится на 3, оно сравнимо с 0 по модулю 3. Также 7 имеет остаток 1 от деления на 3, поэтому $7 \equiv 1 \pmod{3}$. Подставим эти сравнения в исходное уравнение:

$x^2 + 0 \equiv 1 \pmod{3}$

$x^2 \equiv 1 \pmod{3}$

Это означает, что квадрат числа $x$ должен давать остаток 1 при делении на 3. Давайте проверим возможные значения $x$ по модулю 3:

Если $x \equiv 0 \pmod{3}$, то $x^2 \equiv 0 \pmod{3}$

Если $x \equiv 1 \pmod{3}$, то $x^2 \equiv 1 \pmod{3}$

Если $x \equiv 2 \pmod{3}$, то $x^2 \equiv 4 \equiv 1 \pmod{3}$

Таким образом, $x^2$ может иметь остаток 0 или 1 при делении на 3, но не может иметь остаток 2. Наше сравнение $x^2 \equiv 1 \pmod{3}$ выполняется, если $x$ даёт остаток 1 или 2 при делении на 3.

Однако это не означает, что исходное уравнение имеет решение, мы лишь показали, что если решения существуют, то $x$ должно иметь определенный вид. Попробуем найти решения для $x$ вида $3k+1$ и $3k+2$

Если $x = 3k+1$, то $(3k+1)^2 + 3y = 7$ $\Rightarrow$ $9k^2+6k+1+3y=7$ $\Rightarrow$ $3(3k^2+2k+y)=6$ $\Rightarrow$ $y=-3k^2-2k+2$. Таким образом, любое $k$ будет давать нам целочисленное решение.

Если $x=3k+2$, то $(3k+2)^2 + 3y = 7$ $\Rightarrow$ $9k^2+12k+4+3y=7$ $\Rightarrow$ $3(3k^2+4k+y)=3$ $\Rightarrow$ $y=-3k^2-4k+1$. Аналогично, любое целочисленное $k$ будет давать нам целочисленные решения.

Например, при $k=1$ для первого случая имеем $x = 4, y = -3$ и, соответственно $4^2+3(-3)=16-9=7$. При $k=1$ для второго случая $x=5$ и $y=-6$. Тогда $5^2 + 3(-6) = 25-18=7$. И действительно, исходное уравнение имеет решения в целых числах, несмотря на все наши проверки.

Метод бесконечного спуска

Этот метод, восходящий ещё к Ферма, позволяет доказать отсутствие решений в некоторых случаях. Идея состоит в том, чтобы показать, что из любого решения можно получить другое, “меньшее” решение, и так далее. Но целые числа не могут неограниченно уменьшаться, поэтому это приводит к противоречию. Давайте проиллюстрируем метод бесконечного спуска на классическом примере: доказательстве того, что уравнение $x^4 + y^4 = z^2$ не имеет решений в натуральных числах. Это, кстати, частный случай Великой теоремы Ферма для $n=4$.

Допустим, существует решение $(x_0, y_0, z_0)$ в натуральных числах. Можно считать, что $x_0$, $y_0$ и $z_0$ взаимно просты (если бы у них был общий делитель $d > 1$, то мы могли бы разделить все переменные на $d$).

Тогда тройка $(x_0^2, y_0^2, z_0)$ образует пифагорову тройку. Используя известную параметризацию пифагоровых троек, можно записать:

$x_0^2 = m^2 - n^2$
$y_0^2 = 2mn$
$z_0 = m^2 + n^2$

где $m$ и $n$ – взаимно простые натуральные числа разной чётности, и $m > n$.

Из второго уравнения видно, что $y_0^2$ – четное число, значит, и $y_0$ – чётное. Поскольку $m$ и $n$ взаимно простые и $2mn = y_0^2$ — полный квадрат, значит, $m=a^2$ и $n=b^2$ или наоборот, для некоторых натуральных $a$ и $b$.

Из первого уравнения имеем $x_0^2 = m^2 - n^2 = a^4 - b^4$. Это очень похоже на исходное уравнение. Более того, если обозначить $x_1 = x_0, z_1=a$, и подставить в исходное уравнение $x^4+y^4=z^2$ значение $x_0=x_1$ и $a=z_1$ вместо $z$, то можно сделать вывод, что для некоторого целого значения $k$ выполняется равенство $b^4+k^4=a^2$. И мы снова получаем уравнение вида $x^4 + y^4 = z^2$ — то же самое, с чего начали. Обратите внимание, что здесь мы конструируем «меньшее» решение $(b, k, a)$.

Если из существования одного решения $(x_0, y_0, z_0)$ следует существование другого решения $(x_1, y_1, z_1)$, где $z_1 < z_0$, то мы можем продолжить этот процесс бесконечно. Но это невозможно, поскольку натуральные числа не могут неограниченно уменьшаться. Следовательно, исходное уравнение $x^4 + y^4 = z^2$ не имеет решений в натуральных числах.

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

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

Давайте рассмотрим пример: линейное диофантово уравнение $2x + 3y = 5$.

Один из способов решения — использовать расширенный алгоритм Евклида. Найдем наибольший общий делитель (НОД) коэффициентов 2 и 3. НОД(2,3)=1, и 1 делит 5, значит, у уравнения есть целые решения. С помощью расширенного алгоритма Евклида, находим, что $1=2*(-1)+3*1$, и домножая полученное выражение на 5, получаем: $5 = 2(-5)+3(5)$. Значит, одним из решений является $x_0 = -5, y_0 = 5$.
Общее решение имеет вид:

$x=-5+3n$

$y=5-2n$,

где $n$ – любое целое число.