Уравнение Пелля: $x^2-D{y}^2=1$ при целом невырожденном (неквадратном) $D>0$. Коротко — как получить бесконечно много целых решений и какую роль играет период непрерывной дроби для $\sqrt{D}$.
1) Фундаментальная идея.
- Нелинейный диофантов характер уравнения связан с единицами в кольце $\mathbb{Z}[\sqrt{D}]$. Если найдено нетривиальное решение $(x_1,y_1)$ с $x_1^2-D{y}_1^2=1$ (называемое фундаментальным), то все положительные решения получаются как степени этого «единичного» элемента:
$$x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D}{)}^n,n=1,2,3,\dots$$ В частности,
$$x_{n+1}=x_1{x}_n+D{y}_1{y}_n,y_{n+1}=x_1{y}_n+y_1{x}_n.$$ Таким образом из одного нетривиального решения вытекает бесконечно много.
2) Метод непрерывных дробей (основной эффективный метод).
- Разложите $\sqrt{D}$ в непрерывную дробь:
$$\sqrt{D}=[a_0;\overline{a_1,a_2,\dots ,a_k}],$$ где последовательность $\overline{a_1,\dots ,a_k}$ периодична длины $k$. Обозначим числители и знаменатели приводимых дробей (сверток) через $p_n/q_n$.
- Ключевое правило (роль периода):
- Если период $k$ чётен, то фундаментальное нетривиальное решение даёт свёрток с индексом $k-1$:
$$x_1=p_{k-1},y_1=q_{k-1}.$$ - Если период $k$ нечётен, то нужен свёрток с удвоенным периодом: фундаментальное решение даёт
$$x_1=p_{2k-1},y_1=q_{2k-1},$$ то есть берём свёрток после повторения периода дважды.
- Объяснение роли: при развёрнутой цепочке свёртки удовлетворяют приближению $\sqrt{D}$ и дают целочисленные сопоставления для формы $x^2-D{y}^2$. Парность периода определяет, даёт ли один период решение уравнения $=1$ или лишь $=-1$; при нечётном периоде возможен случай уравнения $x^2-D{y}^2=-1$, тогда нужно удвоить период, чтобы получить решение $=1$.
3) Альтернативные методы.
- Алгоритм Чакравалы (индийский метод) эффективно находит фундаментальное решение без полного разложения в непрерывную дробь.
- Теоретически можно использовать методы алгебраической теории чисел: фундаментальная положительная единица в поле $\mathbb{Q}(\sqrt{D})$ и её степени дают все решения.
4) Пример (простой и наглядный): $D=2$.
- $\sqrt{2}=[1;\overline{2}]$ — период $k=1$ (нечётен).
- По правилу: берём свёрток с индексом $2k-1=1$. Свёрток $p_1/q_1=3/2$, значит фундаментальное решение
$$x_1=3,y_1=2,$$ потому что $3^2-2\cdot 2^2=9-8=1$.
- Все положительные решения:
$$x_n+y_n\sqrt{2}=(3+2\sqrt{2}{)}^n.$$ Например, для $n=2$: $(3+2\sqrt{2}{)}^2=17+12\sqrt{2}$, даёт решение $x=17,y=12$ (и т.д.).
Кратко: непрерывная дробь $\sqrt{D}$ даёт фундаментальное решение через её период и соответствующие свёртки; затем все решения получаются степенями найденного «единичного» элемента $x_1+y_1\sqrt{D}$.