主題
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].

另請參閱

二元二次型, 丟番圖方程, 二次冪丟番圖方程, 基本單位, 希爾伯特符號, 拉格朗日數, 單態, 多型

使用 探索

參考文獻

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.

在 上引用

Pell方程

請引用本文為

Weisstein, Eric W. "Pell方程。" 來自 Web 資源。 https://mathworld.tw/PellEquation.html

學科分類