Методы (кратко):
- Непрерывные дроби (Пелл): разложение $\sqrt{5}=[2;\overline{4}]$ даёт непрерывную дробь с периодом 1; простая сопряжённая приближающая дробь $9/4$ даёт фундаментальное решение $(x_1,y_1)=(9,4)$.
- Теория единиц в $\mathbb{Q}(\sqrt{5})$: искать элементы с нормой $1$ в $\mathbb{Z}[\sqrt{5}]$ (фундаментальная единица $\epsilon =9+4\sqrt{5}$).
- Возведение в степень (алгебраические целые или матрицы): генерация больших решений через степени фундаментальной единицы или степени матрицы $\left(\begin{array}{cc}9& 20\\ 4& 9\end{array}\right)$.
- Линейные рекурренты/формулы в закрытом виде: использовать выражения через ${\epsilon }^n$ или рекурренту второго порядка.
Сравнение эффективности для больших решений:
- Нахождение фундаментального решения: метод непрерывных дробей — стандартный и эффективный (для $\sqrt{5}$ он тривиален).
- Генерация очень больших решений (с большим числом цифр): самый эффективный — быстрый показ степеней фундаментальной единицы (возведение по бинарному алгоритму) в кольце $\mathbb{Z}[\sqrt{5}]$ или быстрое возведение матрицы в степень; требует $O(\log n)$ умножений больших целых чисел (каждое умножение — стоимость $M(B)$ битовых операций при длине чисел $B$). Наивный поочередный шаг рекуррентой требует $O(n)$ умножений и поэтому значительно медленнее при больших $n$.
- Для получения конкретного решения заданного размера (битовая длина $B$) количество степеней $n$ примерно $n\approx B/{\log }_2(9+4\sqrt{5})$; вычислять нужно ${\epsilon }^n$ — лучше бинарным возведением.
Структура всех решений:
- Все целые решения уравнения $x^2-5y^2=1$\, задаются формулой
$$x_n+y_n\sqrt{5}=\pm (9+4\sqrt{5}{)}^n,n\in \mathbb{Z}.$$ В частности для неотрицательных $n$: $(x_0,y_0)=(1,0)$, $(x_1,y_1)=(9,4)$, $(x_2,y_2)=(161,72)$ и т.д.
- Закрытая форма:
$$x_n=\frac{(9+4\sqrt{5}{)}^n+(9-4\sqrt{5}{)}^n}{2},y_n=\frac{(9+4\sqrt{5}{)}^n-(9-4\sqrt{5}{)}^n}{2\sqrt{5}}.$$ - Эквивалентно рекуррентно:
$$x_{n+1}=18x_n-x_{n-1},y_{n+1}=18y_n-y_{n-1},$$ с начальными условиями $x_0=1,x_1=9$ и $y_0=0,y_1=4$.
- Или умножением на единицу:
$$x_{n+1}=9x_n+20y_n,y_{n+1}=4x_n+9y_n.$$
Критерий генерации последовательности решений:
- Выберите целое $n\ge 0$; тогда $(x_n,y_n)$, определённые любой из приведённых формул (степень $(9+4\sqrt{5}{)}^n$, рекурренты или матричная степень), дают все решения с положительным $x$. Отрицательные $x$ и $y$ получаются умножением на $-1$ или взятием отрицательных индексов.
- Альтернативный компактный критерий: элемент $\alpha =x+y\sqrt{5}$ даёт решение тогда и только тогда, когда $\mathrm{Norm}(\alpha )=x^2-5y^2=1$; все такие $\alpha$ — степени фундаментальной единицы $\pm {\epsilon }^n$.
Замечание: существует элемент $2+\sqrt{5}$ с нормой $-1$; его чётные степени дают те же решения: $(2+\sqrt{5}{)}^{2n}=(9+4\sqrt{5}{)}^n$.