主题
Search

Pell方程

二次丢番图方程的一个特例，形式如下

x^2-Dy^2=1,
(1)

其中 D>0 是一个非平方自然数 (Dickson 2005)。方程

x^2-Dy^2=+/-4
(2)

在基本单位的计算中出现，有时也被称为Pell方程 (Dörrie 1965, Itô 1987)，Dörrie称方程 (2) 的正形式为费马差方程。虽然费马因首次广泛研究该方程而 заслужить 赞誉，但将此方程错误地归因于Pell的人正是欧拉本人 (Nagell 1951, p. 197; Burton 1989; Dickson 2005, p. 341)。Pell方程也由印度数学家婆什迦罗 (Bhaskara) 解出。Pell方程在数论中极其重要，并且出现在研究以多种方式为有形数的数字中，例如，同时为平方数和三角形数。

该方程有一个明显的推广形式，即类Pell方程

ax^2+/-by^2=c,
(3)

以及更一般的二阶二元丢番图方程

ax^2+bxy+cy^2+dx+ey+f=0.
(4)

然而，对于任意值 a, b, 和 c，需要几种不同的技术来求解该方程。Wolfram 语言 命令Reduce[f[x, y] && Element[x|y, Integers]] 查找一般方程 (4) 的解（如果存在）。

形式为 (1) 的Pell方程，以及右侧带有负号的类似方程的某些情况，

x^2-Dy^2=-1,
(5)

可以通过找到 sqrt(D) 的连分数 [a_0,a_1,...] 来求解。请注意，尽管方程 (5) 仅对某些值 D 可解，但连分数技术在解存在时提供解，并且始终在方程 (1) 的情况下提供解，方程 (1) 始终有解。方程 (5) 可解的必要条件是 D 的所有奇素因子都形如 4n+1，并且 D 不能是双偶数（即，可被 4 整除）。然而，这些条件不是解存在的充分条件，方程 x^2-34y^2=-1 就证明了这一点，该方程在整数中无解 (Nagell 1951, pp. 201 and 204)。

在所有后续讨论中，忽略平凡解 x=1, y=0。令 p_n/q_n 表示第 n 个收敛项 [a_0,a_1,...,a_n]，那么如果我们能找到一个收敛项满足恒等式，我们就解决了方程 (1) 或 (5)

p_n^2-Dq_n^2=(-1)^(n+1).
(6)

令人惊讶的是，由于 二次無理數 的连分数总是在某个项 a_(r+1) 处变为周期性的事实，这总是有可能的，其中 a_(r+1)=2a_0，即，

sqrt(D)=[a_0,a_1,...,a_r,2a_0^_].
(7)

要计算 sqrt(D) 的连分数收敛项，请使用通常的递推关系

a_0=|_sqrt(D)_|
(8)
p_0=a_0
(9)
p_1=a_0a_1+1
(10)
p_n=a_np_(n-1)+p_(n-2)
(11)
q_0=1
(12)
q_1=a_1
(13)
q_n=a_nq_(n-1)+q_(n-2),
(14)

其中 |_x_| 是向下取整函数。出于稍后将解释的原因，还要计算由下式定义的另外两个量 P_n 和 Q_n

P_0=0
(15)
P_1=a_0
(16)
P_n=a_(n-1)Q_(n-1)-P_(n-1)
(17)
Q_0=1
(18)
Q_1=D-a_0^2
(19)
Q_n=(D-P_n^2)/(Q_(n-1))
(20)
a_n=|_(a_0+P_n)/(Q_n)_|.
(21)

现在，连分数收敛项满足两个重要的恒等式

p_nq_(n-1)-p_(n-1)q_n=(-1)^(n+1)
(22)
p_n^2-Dq_n^2=(-1)^(n+1)Q_(n+1)
(23)

(Beiler 1966, p. 262)，因此线性的

ax-by=+/-1
(24)

和二次的

x^2-Dy^2=+/-c
(25)

方程都可以通过简单地找到合适的连分数来求解。

令 a_(r+1)=2a_0 为连分数变为周期性的项（对于二次無理數，这总是会发生）。对于Pell方程

x^2-Dy^2=1
(26)

当 r 为奇数时，(-1)^(r+1) 为正数，并且以最小整数表示的解为 x=p_r 和 y=q_r，其中 p_r/q_r 是第 r 个收敛项。如果 r 为偶数，则 (-1)^(r+1) 为负数，但是

p_(2r+1)^2-Dq_(2r+1)^2=1,
(27)

因此，以最小整数表示的解为 x=p_(2r+1), y=q_(2r+1)。总结一下，

(x,y)={(p_r,q_r) for r odd; (p_(2r+1),q_(2r+1)) for r even.
(28)

方程

x^2-Dy^2=-1
(29)

可以与右侧为 +1 的方程类似地求解，当且仅当 r 为偶数时，但如果 r 为奇数，则无解，

(x,y)={(p_r,q_r) for r even; no solution for r odd.
(30)

给定一个解 (x,y)=(p,q)（可以通过上述方法找到），可以通过将每一边取 n 次幂来找到整个解族，

x^2-Dy^2=(p^2-Dq^2)^n=1.
(31)

因式分解得到

(x+sqrt(D)y)(x-sqrt(D)y)=(p+sqrt(D)q)^n(p-sqrt(D)q)^n
(32)

和

x+sqrt(D)y=(p+sqrt(D)q)^n
(33)
x-sqrt(D)y=(p-sqrt(D)q)^n,
(34)

这给出了解族

x=((p+qsqrt(D))^n+(p-qsqrt(D))^n)/2
(35)
y=((p+qsqrt(D))^n-(p-qsqrt(D))^n)/(2sqrt(D)).
(36)

这些解也适用于

x^2-Dy^2=-1,
(37)

除了 n 只能取奇数值。

下表给出了常数 D<=102 的 Pell 方程的最小整数解 (x,y) (Beiler 1966, p. 254)。平方数 D=d^2 不包括在内，因为它们会导致形式为的方程

x^2-d^2y^2=x^2-(dy)^2=x^2-y^('2)=1,
(38)

该方程无解（因为两个平方数之差不能为 1）。

DxyDxy
2325448566
321558912
59456152
6525715120
78358196032574
8315953069
1019660314
11103611766319049226153980
127262638
136491806381
141546512916
154166658
1733867488425967
1817468334
1917039697775936
20927025130
215512713480413
221974272172
23245732281249267000
2451743699430
26511075263
2726576577996630
28127247735140
299801182078536
3011279809
3115202738091
321738216318
3323483829
3435684556
35618528576930996
37731286104051122
3837687283
392548819721
401938950000153000
41204932090192
42132911574165
433482531921151120
441993093121511260
4516124942143295221064
4624335358895394
4748796495
487197628096336377352
509914989910
5150799101
526499010120120
5366249910010210110

对于非平方 D，x 和 y 的前几个最小值分别为 3, 2, 9, 5, 8, 3, 19, 10, 7, 649, ... (OEIS A033313) 和 2, 1, 4, 2, 3, 1, 6, 3, 2, 180, ... (OEIS A033317)。具有 x=2, 3, ... 的 D 值是 3, 2, 15, 6, 35, 12, 7, 5, 11, 30, ... (OEIS A033314)，具有 y=1, 2, ... 的 D 值是 3, 2, 7, 5, 23, 10, 47, 17, 79, 26, ... (OEIS A033318)。增量最大最小 x 的值是 3, 9, 19, 649, 9801, 24335, 66249, ... (OEIS A033315)，它们出现在 D=2, 5, 10, 13, 29, 46, 53, 61, 109, 181, ... (OEIS A033316)。增量最大最小 y 的值是 2, 4, 6, 180, 1820, 3588, 9100, 226153980, ... (OEIS A033319)，它们出现在 D=2, 5, 10, 13, 29, 46, 53, 61, ... (OEIS A033316)。

更复杂的类 Pell 方程

x^2-Dy^2=c
(39)

其中 |c|<sqrt(D) 有解 当且仅当 c 是值 (-1)^kQ_k 之一，对于 k=1, 2, ..., r 在找到 sqrt(D) 的收敛项的过程中计算出的值（其中，如上所述，a_(r+1)=2a_0 是连分数变为周期性的项）。如果 |c|>sqrt(D)，则过程会复杂得多 (Beiler 1966, p. 265; Dickson 2005, pp. 387-388)，并在 Gérardin (1910) 和 Chrystal (1961) 中进行了讨论。

无论如何找到一个解，如果已知方程 (39) 的单个解 x=p, y=q，则可以找到其他解。令 p 和 q 为方程 (39) 的解，r 和 s 为 “单位” 形式的解

x^2-Dy^2=1.
(40)

那么恒等式

(p^2-Dq^2)(r^2-Ds^2)=(pr+/-Dqs)^2-D(ps+/-qr)^2
(41)
=c
(42)

允许通过使用增量较大的 (r,s) 值来找到 c 方程的更大解 (x,y)=(pr+/-Dqs,ps+/-qr)，可以使用 Pell 方程的标准技术轻松计算出 (r,s) 值。然而，这样的解族不一定生成所有解。例如，方程

x^2-10y^2=9
(43)

有三个不同的基本解集，(x,y)=(7,2), (13, 4), 和 (57, 18)。使用 (42)，这些生成下表所示的解，从中可以生成所有解集 (7, 2), (13, 4), (57, 18), (253, 80), (487, 154), (2163, 684), (9607, 3038), ...。

基本解生成的解
(7, 2)(253, 80), (9607, 3038), (364813, 115364), (13853287, 4380794), ...
(13, 4)(487, 154), (18493, 5848), (702247, 222070), (26666893, 8432812), ...
(57, 18)(2163, 684), (82137, 25974), (3119043, 986328), (118441497, 37454490), ...

情况

ax^2-by^2=c
(44)

可以通过乘以 a 简化为上述情况，

(ax)^2-(ab)y^2=ac,
(45)

在 (x^'=ax,y) 中找到解，然后选择 x^'/a 为整数的解。

根据 Dickson (2005, pp. 408 和 411)，方程

ax^2+by^2=c
(46)

其中 a,b,c>0，它要么无解，要么只有有限数量的解，由高斯在 1863 年使用排除法解决，并由欧拉 (1773) 和 Nasimoff (1885) 考虑过，尽管欧拉的方法不完整 (Smith 1965; Dickson 2005, p. 378)。根据 Itô (1987)，该方程可以使用 Pell 方程的解完全求解。Nasimoff (1885) 应用 Jacobi 椭圆函数来表示方程对于 a,c 为奇数时的解的数量 (Dickson 2005, p. 411)。Dickson (2005, pp. 387-391) 给出了包括与椭圆函数联系的其他讨论。

Cornacchia 解决了 a=1 和 c 为素数的特殊情况 (Cornacchia 1908, Cox 1989, Wagon 1990)。Hardy et al. (1990) 给出了一个确定性算法，用于找到 (46) 对于固定的互质整数 a,b,c>0, c>=a+b+1, 和 (c,ab)=1 的所有本原解。该算法推广了 Hermite (1848)、Serret (1848)、Brillhart (1972)、Cornacchia (1908) 和 Wilker (1980) 的算法。它需要对 c 进行因式分解，并且最坏情况运行时间为 O(c^(1/4)(lnc)^3(lnlnc)(lnlnlnc))，独立于 a 和 b。在 Wolfram 语言 中，用于查找所有解的算法方法实现为Reduce[x^2 + d y^2 == n, {x, y},Integers].

另请参阅

二元二次型, 丢番图方程, 二次幂丢番图方程, 基本单位, 希尔伯特符号, 拉格朗日数, 单态, 多态

使用 Wolfram|Alpha 探索

参考文献

Beiler, A. H. "The Pellian." Ch. 22 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, pp. 248-268, 1966.Brillhart, J. "Note on Representing a Prime as a Sum of Two Squares." Math. Comput. 26, 1011-1013, 1972.Burton, D. M. Elementary Number Theory, 4th ed. Boston, MA: Allyn and Bacon, pp. 379-382 and 392, 1989.Chrystal, G. Textbook of Algebra, 2nd ed., Vol. 2. New York: Chelsea, pp. 478-486, 1961.Cipolla, M. "Un metodo per la risoluzione della congruenza di secondo grado." Rend. Accad. Sci. Fis. Mat. Napoli 9, 154-163, 1903.Cohn, H. "Pell's Equation." §6.9 in Advanced Number Theory. New York: Dover, pp. 110-111, 1980.Cornacchia, G. "Su di un metodo per la risoluzione in numeri unteri dell' equazione sum_(h=0)^(n)c_hx^(n-h)y^h=P." Giornale di Matematiche di Battaglini 46, 33-90, 1908.Cox, D. A. Primes of the form x^2+ny^2. New York: Wiley, 1989.Degan, C. F. Canon Pellianus. Copenhagen, Denmark, 1817.Dickson, L. E. "Pell Equation: ax^2+bx+c Made Square." Ch. 12 in History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Dover, pp. 341-400, 2005.Dörrie, H. 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, 1965.Euler, L. Novi Comm. Acad. Petrop. 18, 218, 1773. Reprinted in Opera Omnia, Series Prima, Vol. 3, p. 310.Euler, L. Comm. Arith. 570. Reprinted in Opera Omnia, Series Prima, Vol. 3, p. 310.Gérardin, A. "Formules de récurrence." Sphinx-Oedipe 5, 17-29, 1910.Hardy, K.; Muskat, J. B.; and Williams, K. S. "A Deterministic Algorithm for Solving n=fu^2+gv^2 in Coprime Integers u and v." Math. Comput. 55, 327-343, 1990.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 91-92, 2003.Hermite, C. "Note au sujet de l'article précédent." J. Math. Pures Appl. 13, 15, 1848.Itô, K. (Ed.). Encyclopedic Dictionary of Mathematics, 2nd ed., Vol. 1. Cambridge, MA: MIT Press, p. 450, 1987.Lagarias, J. C. "On the Computational Complexity of Determining the Solvability or Unsolvability of the Equation X^2-DY^2=-1." Trans. Amer. Math. Soc. 260, 485-508, 1980.Lenstra, H. W. Jr. "Solving the Pell Equation." Not. Amer. Math. Soc. 49, 182-192, 2002.Nagell, T. "The Diophantine Equation x^2-Dy^2=1," "The Diophantine Equation x^2-Dy^2=-1," and "The Diophantine Equation u^2-Dv^2=C." §56-58 in Introduction to Number Theory. New York: Wiley, pp. 195-212, 1951.Nasimoff, P. S. Ch. 1 in Application of Elliptic Functions to the Theory of Numbers. Moscow, 1885. French summary in Ann. sci. de l'École normale supér. 5, 23-31, 1888.Robertson, J. "Home Page for John Robertson." http://www.jpr2718.org/.Serret, J. A. "Sur un théorème rélatif aux nombres enti'eres." J. Math. Pures Appl. 13, 12-14, 1848.Sloane, N. J. A. Sequences A033313, A033314, A033315, A033316, A033317, A033318, and A033319 in "The On-Line Encyclopedia of Integer Sequences."Smith, H. J. S. Collected Mathematical Papers I. New York: Chelsea, pp. 195-202, 1965.Smarandache, F. "Un metodo de resolucion de la ecuacion diofantica." Gaz. Math. 1, 151-157, 1988.Smarandache, F. "Method to Solve the Diophantine Equation ax^2-by^2+c=0." In Collected Papers, Vol. 1. Lupton, AZ: Erhus University Press, 1996.Stillwell, J. C. Mathematics and Its History. New York: Springer-Verlag, 1989.Wagon, S. "The Euclidean Algorithm Strikes Again." Amer. Math. Monthly 97, 124-125, 1990.Whitford, E. E. Pell Equation. New York: Columbia University Press, 1912.Wilker, P. "An efficient Algorithmic Solution of the Diophantine Equation u^2+5v^2=m." Math. Comput. 35, 1347-1352, 1980.

在 Wolfram|Alpha 上引用

Pell方程

请引用本文为

Weisstein, Eric W. "Pell方程。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PellEquation.html

学科分类