循环法:一轮一轮把 61 逼出来
x² − 61y² = 1 的最小解是个十位数;盲目搜索要数到两亿多,这套办法转七步就到。
婆罗摩笈多 628 年就有了「合成法」:手上两组近似解,按他那条两平方和的恒等式并起来,能得到更好的一组。可这只是一件工具,不是一条路——从哪儿开始、下一步该取什么数去合,他没有说死,于是对某些 N 能撞出答案,对另一些就卡住。循环法补上的正是这一句。它把状态写成一个三元组:a² − N b² = k。一轮做三件事:找一个正整数 m,要求 k 整除 a + b·m,并在满足这个条件的 m 里挑 |m² − N| 最小的那个;然后 a 换成 (a·m + N·b)/|k|,b 换成 (a + b·m)/|k|,k 换成 (m² − N)/k。|k| 被一路逼小,转到 1 就收工——k 等于 −1 时再按合成法自乘一次。chakravāla 的意思就是「轮」。拿它去算,每一个非平方的 N 都会在有限轮内停下来;可「一定会停」这件事,印度的文献里并没有证明。欧洲那条线上,「x² − Ny² = 1 一定有解」是十八世纪由拉格朗日证明的,他走的是连分数那条路,不是这条。汉克尔 1874 年在《古代与中世纪数学史》里说,这是拉格朗日之前数论上最漂亮的成就。最后还要补一句:循环法已知最早的记载不在他书里,而在阇耶提婆(约 1000 年)那里,原书失传,只靠 1073 年一部注释转引的二十颂留了下来;婆什迦罗二世做的是把它写成一套完整可用的程序,并用它解开了 61。
挑一个 N,逐轮看三元组怎么换,再与「一个个试」要试多少次对照
婆罗摩笈多 628 年的合成法能把两组近似解并成更好的一组,可「从哪儿开始、下一步取什么」他没有说死。循环法补上的正是这一句:手上有一组 a² − N b² = k,就去找一个 m,要求 k 整除 a + b·m,并在满足这个条件的 m 里挑 |m² − N| 最小的那个;换出新的一组,再转一轮。k 一路被逼向 1,转到 |k| = 1 就收工——k = −1 时再按合成法自乘一次。 N = 61 是他书里的例题,也是最漂亮的例子:转 6 轮加一次合成,得到 x = 1766319049、y = 226153980。同一个 61,1657 年费马当作挑战题抛给英国数学家(另一个是 109),而当时没有人知道印度五百年前就解过。 右边那根长条是「盲目搜索」要付的代价:从 y = 1 数上去,要数到 226153980 才第一次撞上完全平方;一天试一百个,要六千年。两根条画的是位数,不是次数——真按次数画,短的那根连一个像素都占不到。 这里只用了 k = ±1 那条捷径;他书里还给了 k = ±2、±4 的捷径,收工还能更早。循环法已知最早的记载不在他书里,而在阇耶提婆(约 1000 年)那里——原书失传,只靠 1073 年一部注释转引的二十颂留了下来;婆什迦罗二世把它写成了一套完整可用的程序。汉克尔 1874 年在《古代与中世纪数学史》里说,这是拉格朗日之前数论上最漂亮的成就。
