Pell's Equation

Posted by JHSN on August 3, 2018

佩尔方程



标准佩尔方程

形如 $x^2 - dy^2=1 \; (d\geq 0)$ 的二元二次整数方程称为佩尔方程。

当 $d$ 为完全平方数时,不妨设 $d=k^2$,则有 $(x+ky)(x-ky)=1$,显然只有两种情况: $x+ky=x-ky=1$ 或 $x+ky=x-ky=-1$,即 $(x, y) = (\pm 1, 0)$。

当 $d$ 不为完全平方数时,仍然有平凡解 $(\pm 1, 0)$。考虑所有非平凡非负解,设其中两组解为 $(x_1,y_1),(x_2,y_2)$,则有

显然 $(x_1x_2 + dy_1 y_2, x_1 y_2 + x_2 y_1)$ 也是一组解。令 $(x_1,y_1)$ 为最小非平凡解,则由其可递推生成无限组解,递推式

可以表示为矩阵形式

因为

所以又有以下代数形式

考虑 $y_{n+1}, y_n, y_{n-1}$ 之间的关系

联立 $y_n = y_1 x_{n-1} + x_1 y_{n-1}$ 可得

同理计算 $x_{n+1}, x_n, x_{n-1}$ 之间的关系,综合可得另一个递推形式



类佩尔方程

考虑 $x^2 - dy^2=-1$

当 $d$ 为完全平方数时,不妨设 $d=k^2$,则有 $(x+ky)(x-ky)=-1$,显然只有两种情况: $x+ky=ky-x=1$ 或 $x+ky=ky-x=-1$,即 $(x, y) = (0, \pm \frac{1}{k})$,显然只有 $d=1$ 时有解。

令 $(x_1,y_1)$ 为最小非平凡解,$(x_{n+1},\,y_{n+1})=(x_1 x_n + dy_1 y_n,\,y_1 x_n + x_1 y_n)$,则有

即有 $x_n^2 - d y_n^2 = (-1)^n$,所以 $n$ 为奇数时 $(x_n, y_n)$ 均为合法解

扩展到 $x^2 - dy^2=c$,则有 $x_n^2 - d y_n^2 = c^n$



Chakravala method

令三元组 $(a, b, k)$ 表示 $a^2 - db^2 = k$,$(a, b, k)$ 结合 $(m, 1, m^2 - d)$ 利用之前提到的递推式可生成 $\left (am + db, a+bm, k(m^2-d) \right )$ 和 $\left (\frac{am + db}{k}, \frac{a+bm}{k}, \frac{m^2-d}{k}\right )$

更一般地,若存在 $(x_1, y_1, k_1)$ 和 $(x_2, y_2, k_2)$,则一定存在

以此为基础可以不断地进行花式组合,并除去第三项中多余的平方因子,来进行方程求解




评论区加载中