佩尔方程

连分数

$\omega = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \cdots }}$
一个实数 $\omega$ 可以用一个正整数数列$\left[a_{i} \right]$表示,这样的表示方法称为连分数表示.有理数的连分数序列有限,无理数的连分数序列无限.
给定$\left[a_{i} \right]$数列,求原数$\frac{p_{n}}{q_{n}}$的递推公式:
$p_{n} = a_{n}p_{n-1}+p_{n-2},p_{-1}=1,p_{-2}=0$
$q_{n} = a_{n}q_{n-1}+q_{n-2},q_{-1}=0,q_{-2}=1$
一个实数的序列长度为$n$连分数表示亦称为一个数的$n$渐近分数.

佩尔(Pell)方程

$x^{2}-Ny^{2}=1$
佩尔方程有解的充要条件是正整数$N$不是完全平方数
定理:若$\sqrt N$的渐近分数为$\frac{p_{k}}{q_{k}}$,则存在$n>0$,使得$p_{n}^{2}-Nq_{n}^{2}=1$
递推寻找最小解:
初始化:
$p_{-1}=1,p_{-2}=0$
$q_{-1}=0,q_{-2}=1$
$a_{0}=\left \lfloor \sqrt{N} \right \rfloor$
$g_{-1}=0,h_{-1}=1$
递推寻找:
$g_{i}=-g_{i-1}+a_{i}h_{i-1}$
$h_{i}=\frac{N-g_{i}^{2}}{h_{i-1}}$
$a_{i+1}=\left \lfloor \frac{g_{i}+a_{0}}{h_{i}} \right \rfloor$
$p_{i}=a_{i}p_{i-1}+p_{i-2}$
$q_{i}=a_{i}q_{i-1}+q_{i-2}$
然后check $p_{i},q_{i}$

如果求得了最小解$x_{1},y_{1}$,那么可以递推出第$k$大解:
$x_{k}=x_{k-1}x_{1}+Ny_{k-1}y_{1}$
$y_{k}=x_{k-1}y_{1}+y_{k-1}x_{1}$
并且第$k$大解$(x_{k},y_{k})$满足$x_{k}+\sqrt{N}y_{k}=(x_{1}+\sqrt{N}y_{1})^{k}$
所以当$k$比较大时,可以使用二元域的快速幂求解

第二类佩尔方程

$x^{2}-Ny^{2}=-1$
若上式有解,设其最小解为$(x_{0},y_{0})$,那么上式的所有解$(x_{k},y_{k})$满足$x_{k}+y_{k}\sqrt{N}=(x_{0}+y_{0}\sqrt{N})^{2k+1}$
设$x^{2}-Ny^{2}=1$的最小解为$(a,b)$,满足$a+b\sqrt{N}=(x_{0}+y_{0}\sqrt{N})^{2}$