Уравнение Пелля: как найти фундаментальное решение

Уравнение Пелля $x^2 - D y^2 = 1$ - одно из старейших диофантовых уравнений теории чисел: нужно найти целые $x$ и $y$, при которых квадрат $x$ ровно на $D y^2$ превосходит квадрат, дающий единицу. Несмотря на простоту записи, оно имеет богатую структуру решений: если $D$ - целое положительное число и не точный квадрат, решений бесконечно много, а все они получаются из одного, наименьшего, по простой рекуррентной формуле. Ключ к этому наименьшему решению - цепная (непрерывная) дробь числа $\sqrt{D}$. Ниже разберём, как её строить, как из неё вытащить первое решение и как затем эти решения растут почти взрывным образом. Чтобы сразу увидеть картину целиком, покрутите калькулятор ниже - он строит цепную дробь и график роста решений для любого $D$ из списка.

Что такое уравнение Пелля и почему x=1, y=0 не считается

Уравнение Пелля записывается как

$x^2 - D y^2 = 1,$

где $D$ - фиксированное натуральное число, не являющееся точным квадратом. Условие «не точный квадрат» существенно: если $D = k^2$, уравнение превращается в $(x-ky)(x+ky) = 1$, а такое диофантово уравнение имеет только тривиальные решения. Формальное решение $x = 1$, $y = 0$ существует для любого $D$, но его не считают содержательным - интересны решения в натуральных числах, то есть с $y \ge 1$. Именно наименьшее такое решение $(x_1, y_1)$ называют фундаментальным: оно единственное среди «маленьких» пар и порождает все остальные.

Имя уравнение получило благодаря Джону Пеллю, хотя сам он к его изучению почти не причастен - Леонард Эйлер по ошибке приписал ему результаты, полученные другими математиками (в частности, Уильямом Броункером и индийскими математиками Брахмагуптой и Бхаскарой II на много веков раньше). Историческая случайность не помешала названию закрепиться.

Цепная дробь корня из D: как найти фундаментальное решение

Фундаментальное решение находят через разложение $\sqrt{D}$ в цепную (непрерывную) дробь. Для любого целого не-квадратного $D$ это разложение периодично и вычисляется по рекуррентному алгоритму:

$$a_0 = \left\lfloor \sqrt{D} \right\rfloor, \qquad m_0 = 0, \quad d_0 = 1,$$ $$m_{k+1} = d_k a_k - m_k, \qquad d_{k+1} = \frac{D - m_{k+1}^2}{d_k}, \qquad a_{k+1} = \left\lfloor \frac{a_0 + m_{k+1}}{d_{k+1}} \right\rfloor.$$

Числа $a_k$ и есть неполные частные цепной дроби $\sqrt{D} = [a_0;\, a_1, a_2, \ldots]$; период заканчивается, как только очередное $a_k$ становится равным $2a_0$. Дальше по этим неполным частным строят подходящие дроби $h_n/k_n$ - стандартные числитель и знаменатель приближения:

$$h_{-1} = 1, \quad h_{-2} = 0, \qquad k_{-1} = 0, \quad k_{-2} = 1,$$ $$h_n = a_n h_{n-1} + h_{n-2}, \qquad k_n = a_n k_{n-1} + k_{n-2}.$$

Рассчитать для своей задачи

Если длина периода $l$ чётна, фундаментальное решение - это как раз $(h_{l-1}, k_{l-1})$. Если период нечётный, эта пара решает не исходное уравнение, а «соседнее» $x^2 - D y^2 = -1$, и нужно пройти период ещё раз: фундаментальное решение уравнения со знаком плюс тогда равно $(h_{2l-1}, k_{2l-1})$.

Рекуррентная формула для всех решений

Как только найдено фундаментальное решение $(x_1, y_1)$, все остальные натуральные решения получаются простой рекуррентой:

$$x_{n+1} = x_1 x_n + D y_1 y_n, \qquad y_{n+1} = x_1 y_n + y_1 x_n,$$

с начальным условием $(x_1, y_1)$ на первом шаге. Удобно записывать это через алгебраическое число $x_n + y_n \sqrt{D}$: оказывается, что

$$x_n + y_n \sqrt{D} = (x_1 + y_1 \sqrt{D})^{\,n}.$$

То есть каждое следующее решение получается умножением на одну и ту же «фундаментальную единицу» $\lambda = x_1 + y_1 \sqrt{D}$. Например, для $D = 2$ фундаментальное решение $(3, 2)$ даёт $\lambda = 3 + 2\sqrt{2} \approx 5{,}83$, а последовательность решений выглядит так: $(3, 2)$, $(17, 12)$, $(99, 70)$, $(577, 408)$, $(3363, 2378)$ - каждая следующая пара примерно в 5,83 раза больше предыдущей.

Геометрия: гипербола и взрывной рост решений

Уравнение $x^2 - D y^2 = 1$ на плоскости $(x, y)$ задаёт гиперболу с двумя ветвями; интересующая нас правая ветвь проходит через точку $(1, 0)$ и уходит вверх и вправо при $y > 0$. Целочисленные решения - это узлы решётки $\mathbb{Z}^2$, которые лежат ровно на этой кривой. Первое такое пересечение после тривиального $(1,0)$ и есть фундаментальное решение; все следующие лежат на той же ветви значительно дальше.

Рассчитать для своей задачи

Именно поэтому решения растут так стремительно: на линейной шкале уже третье-четвёртое решение делает график бесполезным, а на логарифмической шкале рост выглядит как равномерная лестница - каждая ступенька соответствует умножению на $\lambda$. Это прямое следствие того, что $\lambda > 1$ - фундаментальная единица кольца $\mathbb{Z}[\sqrt{D}]$, и возведение её в степень $n$ геометрически растягивает решение вдоль ветви гиперболы.

Когда разрешимо уравнение x² - Dy² = -1

Смежное уравнение $x^2 - D y^2 = -1$ разрешимо в целых числах далеко не для всех $D$: необходимое и достаточное условие (в терминах цепной дроби) - длина периода разложения $\sqrt{D}$ должна быть нечётной. Например, для $D = 2$ период равен $[1; 2, 2, 2, \ldots]$ длины 1 (нечётный), и уравнение $x^2 - 2y^2 = -1$ имеет решение $(1, 1)$: действительно, $1 - 2 = -1$. Возведя соответствующую единицу в квадрат, $(1 + \sqrt{2})^2 = 3 + 2\sqrt{2}$, снова получаем фундаментальное решение $(3, 2)$ уравнения со знаком плюс.

А вот для $D = 3$ период равен $[1; 1, 2, 1, 2, \ldots]$ длины 2 (чётный), и уравнение $x^2 - 3y^2 = -1$ решений не имеет вовсе - сколько бы целых $x, y$ ни перебирали, левая часть никогда не станет $-1$. Проверить это перебором несложно: $x^2 - 3y^2$ при малых значениях принимает значения $-2, 1, -3, 6, \ldots$, но никогда $-1$.

Пример решения типовой задачи

Найдём фундаментальное решение для $D = 7$. Строим цепную дробь по алгоритму: $a_0 = \lfloor\sqrt{7}\rfloor = 2$, дальше последовательно получаем $a_1 = 1$, $a_2 = 1$, $a_3 = 1$, $a_4 = 4 = 2a_0$ - период $[1, 1, 1, 4]$ длины 4 (чётный). Строим подходящие дроби по рекурренте $h_n = a_n h_{n-1} + h_{n-2}$:

$$\begin{aligned} h_0 &= 2,\ k_0 = 1 \quad (2/1),\\ h_1 &= 3,\ k_1 = 1 \quad (3/1),\\ h_2 &= 5,\ k_2 = 2 \quad (5/2),\\ h_3 &= 8,\ k_3 = 3 \quad (8/3). \end{aligned}$$

Период чётной длины 4, поэтому фундаментальное решение - это как раз пара с индексом $l - 1 = 3$: $(x_1, y_1) = (8, 3)$. Проверяем: $8^2 - 7 \cdot 3^2 = 64 - 63 = 1$ - верно. Следующее решение находим по рекурренте:

$$x_2 = 8 \cdot 8 + 7 \cdot 3 \cdot 3 = 64 + 63 = 127, \qquad y_2 = 8 \cdot 3 + 3 \cdot 8 = 24 + 24 = 48.$$

Проверка: $127^2 - 7 \cdot 48^2 = 16129 - 16128 = 1$. Оба решения можно свериться прямо в калькуляторе выше, выбрав $D = 7$.

Где уравнение Пелля встречается на практике

Помимо чистой теории чисел, уравнение Пелля даёт наилучшие рациональные приближения иррационального $\sqrt{D}$: дроби $h_n / k_n$, из которых берётся фундаментальное решение, приближают корень с ошибкой порядка $1/k_n^2$ - лучше, чем почти любая другая дробь с тем же знаменателем. В алгебраической теории чисел решения уравнения Пелля - это в точности единицы кольца целых чисел $\mathbb{Z}[\sqrt{D}]$, то есть элементы с обратным того же вида; это делает уравнение Пелля частным случаем более общей задачи об обратимых элементах числовых полей. Есть у задачи и неожиданная связь с вычислительной сложностью: классические алгоритмы поиска фундаментального решения работают экспоненциально долго от числа цифр ответа (само решение для некоторых $D$ может содержать сотни знаков, как в знаменитой задаче Архимеда о быках), тогда как квантовый алгоритм Халлгрена решает уравнение Пелля за полиномиальное время - это одна из причин, почему задачу изучают и в контексте криптографии.

Частые ошибки

• Перебор вместо цепной дроби. Для больших $D$ прямой перебор $y = 1, 2, 3, \ldots$ в поиске целого $x$ работает крайне медленно - фундаментальное решение может быть огромным даже для небольшого $D$. Правильный путь - алгоритм цепной дроби.
• Путаница чётности периода. Если период нечётный, найденная подходящая дробь $(h_{l-1}, k_{l-1})$ решает уравнение $x^2 - Dy^2 = -1$, а не $+1$ - нужно пройти период дважды.
• Забытое условие «не точный квадрат». Если $D$ - точный квадрат, уравнение имеет только тривиальные решения $(x, \pm1 \cdot 0)$, и вся техника цепных дробей неприменима.
• Неверная рекуррента для следующих решений. Формулу $x_{n+1} = x_1 x_n + D y_1 y_n$ иногда путают со знаком или коэффициентом при $D$ - стоит сразу проверять равенство $x_{n+1}^2 - D y_{n+1}^2 = 1$.
• Игнорирование отрицательных и нулевых решений. Уравнение симметрично относительно знаков $x$ и $y$, но содержательными считают только решения в натуральных числах - остальные получаются из них сменой знака.

FAQ

Всегда ли уравнение Пелля имеет решения? Да, если $D$ - натуральное число и не точный квадрат, уравнение $x^2 - Dy^2 = 1$ всегда имеет бесконечно много целых решений; это доказывается через теорему Дирихле о приближении и принцип ящиков применительно к цепной дроби $\sqrt{D}$.

Как быстро растут решения уравнения Пелля? Геометрически: каждое следующее решение получается из предыдущего умножением на фундаментальную единицу $\lambda = x_1 + y_1\sqrt{D}$, поэтому уже пятое-шестое решение может быть на порядки больше первого.

Чем уравнение Пелля отличается от обобщённого уравнения Пелля? Классическое уравнение - это $x^2 - Dy^2 = 1$; обобщённое допускает произвольную правую часть $x^2 - Dy^2 = N$ и требует более тонкого анализа: решений может не быть вовсе, а если есть, они разбиваются на несколько классов.

Коротко

Уравнение Пелля $x^2 - Dy^2 = 1$ для целого не-квадратного $D$ всегда имеет бесконечно много решений, а найти их все можно из одного, фундаментального. Фундаментальное решение $(x_1, y_1)$ находится через периодическую цепную дробь $\sqrt{D}$ и подходящие дроби, а все остальные решения получаются рекуррентой $x_{n+1} = x_1 x_n + Dy_1 y_n$, $y_{n+1} = x_1 y_n + y_1 x_n$, что эквивалентно возведению фундаментальной единицы $x_1 + y_1\sqrt{D}$ в степень. Уравнение со знаком минус $x^2 - Dy^2 = -1$ разрешимо ровно тогда, когда период цепной дроби $\sqrt{D}$ нечётен.