数学史 · 中文镜像

数学史专题

佩尔方程Pell's equation

我们将在下面讨论约翰·佩尔的方程是否命名恰当。我们的意思很简单:约翰·佩尔是否对约翰·佩尔的方程的研究有所贡献?毫无疑问,在约翰·佩尔出生之前,这个方程已经被深入研究了几百年。事实上,婆罗摩笈多的第一个贡献大约在约翰·佩尔时代之前1000年左右,我们的历史研究就从婆罗摩笈多的贡献开始。

首先让我们说明约翰·佩尔的方程是什么。我们讨论的是不定二次方程

nx2+1=y2nx^{2} + 1 = y^{2}

我们也可以将其写作

y2nx2=1y^{2} - nx^{2} = 1

其中nn是给定的整数,我们寻找整数解(x,y)(x, y)

现在,虽然可以说婆罗摩笈多是第一个研究这个方程的人,但同样可以看到更早的作者已经研究了与约翰·佩尔的方程相关的问题。简要提及一些:丢番图研究了与约翰·佩尔的方程相关的问题,我们可以将阿基米德的“牛群问题”归结为求解约翰·佩尔的方程,尽管没有证据表明阿基米德做出了这种联系。

首先让我们注意到

(b2na2)(d2nc2)=(bd+nac)2n(bc+ad)2(b^{2} - na^{2})(d^{2} - nc^{2}) = (bd + nac)^{2} - n(bc + ad)^{2}

(b2na2)(d2nc2)=(bdnac)2n(bcad)2(b^{2} - na^{2})(d^{2} - nc^{2}) = (bd - nac)^{2} - n(bc - ad)^{2}

由此我们看到,如果

b2na2=1b^{2} - na^{2} = 1d2nc2=1d^{2} - nc^{2} = 1

然后

(bd+nac)2n(bc+ad)2=1(bd + nac)^{2} - n(bc + ad)^{2} = 1

(bdnac)2n(bcad)2=1(bd - nac)^{2} - n(bc - ad)^{2} = 1

换句话说,如果(a,b)(a, b)(c,d)(c, d)约翰·佩尔方程的解,那么以下也是

(bc+ad,bd+nac)(bc + ad, bd + nac)(bcad,bdnac)(bc - ad, bd - nac)

这个极其重要的事实很容易推广,从而给出婆罗摩笈多引理,即如果(a,b(a, b(c,d)(c, d)是形如以下形式的‘约翰·佩尔型方程’的整数解

na2+k=b2na^{2} + k = b^{2}nc2+k=d2nc^{2} + k' = d^{2}

然后

(bc+ad,bd+nac)(bc + ad, bd + nac)(bcad,bdnac)(bc - ad, bd - nac)

都是‘约翰·佩尔型方程’的整数解

nx2+kk=y2nx^{2} + kk' = y^{2}

我们给出的证明归功于17世纪的欧洲数学家(我们将在本文后面进一步评论这一点),但婆罗摩笈多引理是由婆罗摩笈多在公元628年发现的。这种方法被印度数学家称为samasa,但我们将称之为‘复合方法’。事实上,这种复合方法使婆罗摩笈多能够关于约翰·佩尔方程做出若干根本性的发现。

他推导出的一个性质是,如果(a,b)(a, b)满足约翰·佩尔的方程,那么(2ab,b2+na2)(2ab, b^{2} + na^{2})也满足。这立即通过将复合方法应用于(a,b)(a, b)(a,b)(a, b)而得出。现在当然可以再次将复合方法应用于(a,b)(a, b)(2ab,b2+na2)(2ab, b^{2}+ na^{2})以得到另一个解,婆罗摩笈多立即看到,从约翰·佩尔的方程的一个解,他可以生成许多解。

这并不是婆罗摩笈多使用复合方法的唯一方式。他还注意到,使用与我们刚刚给出的论证类似的论证,如果x=a,y=bx = a, y = bnx2+k=y2nx^{2} + k = y^{2}的解,那么对(a,b)(a, b)(a,b)(a, b)应用复合方法会给出(2ab,b2+na2)(2ab, b^{2} + na^{2})作为nx2+k2=y2nx^{2} + k^{2} = y^{2}的解,于是除以k2k^{2},得到

x=1k2ab,y=1k(b2+na2)x = \large\frac{1}{k}\normalsize 2ab , y = \large\frac{1}{k}\normalsize (b^{2} + na^{2})

作为约翰·佩尔的方程nx2+1=y2nx^{2} + 1 = y^{2}的一个解。

这有什么帮助呢?xxyy的这些值看起来不像整数。那么如果k=2k = 2,由于(a,b)(a, b)nx2+k=y2nx^{2} + k = y^{2}的一个解,我们有na2=b22na^{2} = b^{2} - 2。因此

x=1k2ab=abx = \large\frac{1}{k}\normalsize 2ab = ab

y=12(b2+na2)=12(2b22)=b21y = \large\frac{1}{2}\normalsize (b^{2} + na^{2}) = \large\frac{1}{2}\normalsize (2b^{2} - 2) = b^{2} - 1

而这是约翰·佩尔的方程的一个整数解。如果k=2k = -2,那么本质上相同的论证也成立;而如果k=4k = 4k=4k = -4,那么一种更复杂的方法,仍然基于复合方法,表明可以找到约翰·佩尔的方程的整数解。所以婆罗摩笈多能够表明,如果他能找到(a,b)(a, b),它“几乎”满足约翰·佩尔的方程,即na2+k=b2na^{2} + k = b^{2},其中kk= 1、-1、2、-2、4或-4,那么他就能找到约翰·佩尔的方程的一个整数解,从而找到许多个。他常常能找到对这些kk值之一有效的尝试解,因此在许多情况下他能够给出解。

例如,如果我们尝试解23x2+1=y223x^{2} + 1 = y^{2},我们看到a=1,b=5a = 1, b = 5满足23a2+2=b223a^{2} + 2 = b^{2},所以根据上述论证,x=5,y=24x = 5, y = 24满足约翰·佩尔的方程。对(5, 24)这一对应用复合方法得到

x=2×5×24=240, y=242+23×52=1151x = 2\times 5\times 24 = 240,  y = 24^{2} + 23\times 5^{2} = 1151

作为另一个解。再次应用复合方法得到

x=11515, y=55224x = 11515,  y = 55224

再应用一次得到

x=552480, y=2649601x = 552480,  y = 2649601

等等。

婆罗摩笈多自己给出的例子中,有一个是约翰·佩尔方程的解法

83x2+1=y283x^{2} + 1 = y^{2}

他注意到数对(1, 9)满足

83×122=9283\times 1^{2} - 2 = 9^{2}

并运用他的方法求出解

x=9, y=82x = 9,  y = 82

我们现在可以生成一个解序列(x,y)(x,y)

(9, 82),
(1476, 13447),
(242055, 2205226),
(39695544, 361643617),
(6509827161, 59307347962),
(1067571958860, 9726043422151),
(175075291425879, 1595011813884802)

等等。

人们只能惊叹于婆罗摩笈多在公元628年做出的这项杰出工作。

下一步进展由婆什迦罗第二在1150年取得。他发现了循环法,印度人称之为chakravala,这是一种算法,从任意“接近”的配对(a,b)(a, b)(满足na2+k=b2na^{2} + k = b^{2})出发,产生约翰·佩尔方程nx2+1=y2nx^{2} + 1 = y^{2}的一个解。我们可以假设aabb互素,否则我们可以将每个除以它们的最大公约数,得到一个具有更小kk的“更接近”的解。显然,a,ka, k然后也是互素的。

该方法基于一个简单的观察,即对于任意m,(1,m)m, (1, m),都满足“约翰·佩尔型方程”

n×12+(m2n)=m2n\times 1^{2} + (m^{2} - n) = m^{2}

婆什迦罗第二现在把合成方法应用于数对(a,b)(a, b)(1,m)(1, m),得到

n(am+b)2+(m2n)k=(bm+na)2n(am + b)^{2} + (m^{2} - n)k = (bm + na)^{2}

除以k2k^{2},我们注意到

x=1k(am+b),y=1k(bm+na)x = \large\frac{1}{k}\normalsize (am+b), y = \large\frac{1}{k}\normalsize (bm+na)

是以下方程的解

nx2+1k(m2n)=y2nx^{2} + \large\frac{1}{k}\normalsize (m^{2} - n) = y^{2}

由于a,ka, k互素,我们可以选取mm使得am+bam + bkk整除。婆什迦罗第二现在知道(但他没有给出证明),当选取mm使得am+bam + bkk整除时,m2nm^{2} - nbm+nabm + na也被kk整除。因此,通过这样选取mm,他得到了整数解

x=1k(am+b),y=1k(bm+na)x = \large\frac{1}{k}\normalsize (am+b) , y = \large\frac{1}{k}\normalsize (bm+na)

对于“约翰·佩尔型方程”nx2+1k(m2n)=y2nx^{2} + \large\frac{1}{k}\normalsize (m^{2} - n) = y^{2},其中1k(m2n)\large\frac{1}{k}\normalsize (m^{2} - n)也是整数。

接下来婆什迦罗第二知道存在无穷多个mm使得am+bam + b能被kk整除。他选择使m2nm^{2} - n的绝对值尽可能小的那个。如果1k(m2n)\large\frac{1}{k}\normalsize (m^{2} - n)是1、-1、2、-2、4、-4之一,那么我们可以应用婆罗摩笈多的方法来找到约翰·佩尔方程nx2+1=y2nx^{2} + 1 = y^{2}的一个解。如果1k(m2n)\large\frac{1}{k}\normalsize (m^{2} - n)不是这些值之一,那么这次从‘约翰·佩尔型方程’nx2+1k(m2n)=y2nx^{2} + \large\frac{1}{k}\normalsize (m^{2} - n) = y^{2}的解x=1k(am+b),y=1k(bm+na)x = \large\frac{1}{k}\normalsize (am+b) , y = \large\frac{1}{k}\normalsize (bm + na)开始,以与我们将过程应用于na2+k=b2na^{2} + k = b^{2}完全相同的方式重复该过程。婆什迦罗第二知道(几乎肯定是通过经验而非通过证明)该过程将在有限步数后结束。当达到形式为nx2+t=y2nx^{2} + t = y^{2}的方程时,其中tt是1、-1、2、-2、4、-4之一,这种情况就会发生。

婆什迦罗第二Bijaganita中给出了例子,我们首先看的是

61x2+1=y261x^{2} + 1 = y^{2}

他用上述方法选择mm,使得(m+8)/3(m + 8)/3为整数,并确保m261m^{2} - 61尽可能小。取m=7m = 7,他得到

x=5, y=39x = 5,  y = 39

作为“约翰·佩尔型方程”nx24=y2nx^{2} - 4 = y^{2}的一个解。但这是一个婆罗摩笈多的方法能求解的方程,给出

x=226153980, y=1766319049x = 226153980,  y = 1766319049

作为61x2+1=y261x^{2} + 1 = y^{2}的最小解。

为什么我们怀疑婆什迦罗第二没有该方法的证明?嗯,至少有两个原因。首先,证明冗长且困难,似乎远远超出了12世纪的数学水平。其次,该算法总是在有限步数后达到约翰·佩尔方程的一个解,而不会在达到类型为nx2+k=y2nx^{2} + k = y^{2}的方程(其中kk = -1、2、-2、4或-4)时停止,然后应用婆罗摩笈多的方法。如果对该算法的经验仅来自例子,那么当知道在达到kk = -1、2、-2、4或-4时如何继续,此时自然切换到婆罗摩笈多的方法。然而,当写下证明时,应该清楚该算法切换到婆罗摩笈多的方法从来不是必要的(尽管可以更快地达到解)。

约翰·佩尔方程的下一个贡献是由娜里亚纳的牛只做出的,他在14世纪写了一部对婆什迦罗第二Bijaganita.的评注。娜里亚纳的牛只给出了一些循环法的新例子。以下是他的两个例子:

103x2+1=y2103x^{2} + 1 = y^{2}

选择a=1,b=10a = 1, b = 10娜里亚纳的牛只得到

103×123=102103 \times 1^{2} - 3 = 10^{2}

选择mm使得m+10m + 10能被-3整除,且m2103m^{2} - 103尽可能小,导致m=11m = 11,我们得到

103×726=712103 \times 7^{2} - 6 = 71^{2}

接下来我们必须选择mm,使得7m+717m + 71能被-6整除,且m2103m^{2} - 103尽可能小。取m=7m = 7得到方程

103×202+9=2032103 \times 20^{2} + 9 = 203^{2}

继续,选择mm使得20m+20320m+203能被9整除,且m2103m^{2} - 103尽可能小。取m=11m = 11得到方程

103×472+2=4772103 \times 47^{2} + 2 = 477^{2}

现在娜里亚纳的牛只应用婆罗摩笈多的方法,采用我们上面针对k=2k = 2的方程所给出的形式,来得到解

x=22419, y=227528x = 22419,  y = 227528

他的下一个例子是约翰·佩尔的方程的一个解

97x2+1=y297x^{2} + 1 = y^{2}

通过应用循环方法,这依次导致方程

97×12+3=10297\times 1^{2} + 3 = 10^{2}

97×72+8=69297\times 7^{2} + 8 = 69^{2}

97×202+9=197297\times 20^{2} + 9 = 197^{2}

97×532+11=522297\times 53^{2} + 11 = 522^{2}

97×8623=847297\times 86^{2} - 3 = 847^{2}

97×56921=5604297\times 569^{2} - 1 = 5604^{2}

最后娜里亚纳的牛只婆罗摩笈多的方法应用于最后一个方程以得到解

x=6377352, y=62809633x = 6377352,  y = 62809633

现在,婆罗摩笈多婆什迦罗第二娜里亚纳的牛只的卓越思想在17世纪对欧洲数学家来说完全未知。欧洲的兴趣始于1657年,当时皮埃尔·德·费马向欧洲和英格兰的数学家发出挑战。皮埃尔·德·费马写道:

我们等待这些解答,如果英格兰、比利时或凯尔特高卢不能给出,那么纳博讷高卢将会给出。

当然,纳博讷高卢就是皮埃尔·德·费马居住的图卢兹周边地区!皮埃尔·德·费马的挑战问题之一就是约翰·佩尔方程的同一个例子,该方程在500年前已被婆什迦罗第二研究过,即寻找以下方程的解

61x2+1=y261x^{2} + 1 = y^{2}

几位数学家参与了皮埃尔·德·费马的挑战,特别是福兰尼可威廉·布朗克约翰·沃利斯。随后在1657-58年间这些数学家之间进行了通信,约翰·沃利斯于1658年在Commercium epistolicum中发表。威廉·布朗克发现了一种解法,其本质上与连分数的方法相同,后者后来由约瑟夫·拉格朗日严格发展。福兰尼可列出了约翰·佩尔方程对于所有nn直到150的解,尽管这从未发表,他的努力已经失传。他挑战威廉·布朗克,后者声称能够解决约翰·佩尔方程的任何例子,去解决

313x2+1=y2313x^{2} + 1 = y^{2}

威廉·布朗克使用他的方法找到了最小的解,即

x=1819380158564160, y=32188120829134849x = 1819380158564160,  y = 32188120829134849

然后他把这些寄给福兰尼可,声称他找到它们只花了“一两个小时”。

Commercium epistolicum中,约翰·沃利斯给出了两种证明婆罗摩笈多引理的方法,这两种方法本质上都等价于我们在本文开头基于该结果所给出的论证。

(b2na2)(d2nc2)=(bd+nac)2n(bc+ad)2(b^{2} - na^{2})(d^{2} - nc^{2}) = (bd + nac)^{2} - n(bc + ad)^{2}

1658年,约翰·海因里希·雷恩出版了一本代数书,其中包含一个约翰·佩尔方程的实例。这本书是在约翰·佩尔的帮助下写成的,这是已知的约翰·佩尔与以他命名的方程之间唯一的联系。

约翰·沃利斯于1685年出版了Treatise on Algebra,该著作的第98章专门给出了基于他1658年在Commercium epistolicum中发表的通信来解约翰·佩尔方程的方法。然而,在他的代数教材约翰·沃利斯中,他将所有方法整理成了标准形式。

我们应该注意到,到这时已有几位数学家声称约翰·佩尔方程nx2+1=y2nx^{2} + 1 = y^{2}对任何nn都有解。约翰·沃利斯在描述威廉·布朗克的方法时提出了这一主张,皮埃尔·德·费马在评论对他的挑战所提出的解答时也如此。事实上,皮埃尔·德·费马声称,当然这是正确的,对于任何nn约翰·佩尔方程都有无穷多个解。

莱昂哈德·欧拉以与我们上面给出的类似形式给出了婆罗摩笈多引理及其证明。他当然知道威廉·布朗克关于约翰·佩尔方程的工作,如约翰·沃利斯所呈现的,但他完全不知道印度数学家的贡献。他给出了用连分数方法解约翰·佩尔方程的基础,该方法由约瑟夫·拉格朗日在1766年整理成完善的形式。莱昂哈德·欧拉的另一个主要贡献是将该方程命名为“约翰·佩尔方程”,普遍认为他之所以这样命名,是因为他混淆了威廉·布朗克约翰·佩尔,以为约翰·沃利斯所报告的归功于威廉·布朗克的主要贡献实际上是约翰·佩尔的工作。

约瑟夫·拉格朗日于1771年出版了他的Additions to 莱昂哈德·欧拉's Elements of algebra,其中包含了他对莱昂哈德·欧拉用连分数方法解约翰·佩尔方程的严格版本。这严格地确立了对于每个nn约翰·佩尔方程都有无穷多个解这一事实。解依赖于n√n的连分数展开。在整数平方根的连分数中,相同的分母周期性地出现。此外,大多数循环序列中的模式是“回文”的,即除了最后一个元素外,周期序列的后半部分是前半部分的逆序。循环序列中的最后一个数字是平方根整数部分的两倍。

例如√19的连分数展开为

19=4+12+11+13+11+12+18+12+11+13+11+12+18+12+11+...\sqrt{19} = 4+ \Large\frac{1}{2+} \frac{1}{1+} \frac{1}{3+} \frac{1}{1+} \frac{1}{2+} \frac{1}{8+} \frac{1}{2+} \frac{1}{1+} \frac{1}{3+} \frac{1}{1+} \frac{1}{2+} \frac{1}{8+} \frac{1}{2+} \frac{1}{1+} ...

它表示

19=4+12+11+13+11+12+18+12+11+...\sqrt{19} = 4+ \Large\frac{1}{2+ \Large\frac{1}{1+\Large\frac{1}{3 + \Large\frac{1}{1 + \Large\frac{1}{2 + \Large\frac{1}{8 + \Large\frac{1}{2 + \Large\frac{1}{1 + ...}}}}}}}}

它以长度6循环出现。在它开始重复的那一点之前的收敛项是17039\Large\frac{170}{39}\normalsize,而约瑟夫·拉格朗日的理论表明

x=39, y=170x = 39,  y = 170

将是约翰·佩尔方程的最小解

19x2+1=y219x^{2} + 1 = y^{2}

要找到无穷多个解,取170 + 39√19的幂。例如

(170+3919)2=57799+1326019(170 + 39√19)^{2} = 57799 + 13260√19

x=13260,y=57799x = 13260, y = 57799

将给出方程的第二个解。再次

(170+3919)3=19651490+450836119(170 + 39√19)^{3} = 19651490 + 4508361√19

给出

x=4508361, y=19651490x = 4508361,  y = 19651490

作为下一个解。下面是 (170 + 39√19) 的前几个幂,从它的平方开始,这给出了方程 19x2+1=y219x^{2} + 1 = y^{2} 的前几个解。

57799 + 13260√19

19651490 + 4508361√19

6681448801 + 1532829480√19

2271672940850 + 521157514839√19

772362118440199 + 177192022215780√19

262600848596726810 + 60244766395850361√19

89283516160768675201 + 20483043382566906960√19

尽管用连分数方法解 约翰·佩尔 的方程对于 nn 的较小值来说是一种很好的方法,但人们已经分析了该方法的困难程度,以确定它对于大的 nn 是否最为有效。一个关于输入 nn 长度的多项式时间方法,将是一个运行时间以 log nn(输入的长度)的固定幂为界的算法。连分数方法不是多项式时间算法,而且现在已知不存在解 约翰·佩尔 的方程的多项式时间算法。