课件13_连分数与佩尔方程的最小整数解.doc

1连分数与佩尔（Pell）方程的最小正整数解【0】基本命令① LCM[2,3,5]：求 2，3，5 的最小公倍数GCD[3,6,9]：求 3，6，9 的最大公因子② RealDigits[2008]：对 2008 进行数字分解，并别求出 2008 是几位数程序执行后结果：{{2,0,0,8},4}③ Drop[{x,y,z},{3}]：从向量 {x,y,z}中去掉第 3 个元素1】连分数表示法一个“既约”分数（分子可以比分母大，但无公因子）可以表示成连分数的形式例如将 表示成连分数，程序如下：17ContinuedFraction[ ]得到结果：{0 ，1，1，1，5} 这表示ܱܱܱܱ㜽 ܱЫܱܱ㜽 ܱܱ㜽 ܱܱī ܱוּ二次整系数方程的根叫做二次无理数初等数论中已经证明：一切二次无理数表示成连分数，都具有无穷循环节例如将 ܱ+ ܱ 表示成连分数，程序如下：ContinuedFraction[ܱ+ ܱ ]得到结果：{4 ，{3 ，6}}这表示1+ ܱ =4+ 13+ 16+ 13+ 16+ܱܱ 其中{3，6}用花括号括起来，表示无穷循环节反之，我们可以通过一个数的连分数表示形式求其正常形式。

例如：FromContinuedFraction[{ 1，2，3 }]得到结果： 这表示：连分数71081ܱ′,3<=1+ 12+13=ܱ 72又例如，FromContinuedFraction[ { 2, 1, { 4, 2, 3 } } ]得到结果：బబబIబ9 + బబ M这表示：82,ıܱ84┬2,3<=2+ 11+ 14+ 12+ 13+ 14ȫܱ. Ƚ 1ܱ ɉܱ9 + ܱܱ M【2】佩尔（Pell）方程的最小正整数解公元前３世纪下半叶古希腊科学家阿基米德（Archimedes，公元前 287—公元前 212 年）在其论著中记载了一个牲畜问题，普遍称作群牛问题历史上对这问题的研究丰富了初等数论的内容 原文用诗句写成，大意是：西西里岛草原上有一大群牛，公牛和母牛各有４种颜色设 、 、 、 分别表示白、黑、黄、花色的公牛数， 、 、WXYZwx、 分别表示这白、黑、黄、花色的母牛数它们满足：yz、 、 、312514YW716、 、 、xXw4zZy5Wy716（1）不附加条件的群牛问题求解方程组：、 、 、YX32YZ514YW716、 、 、xw41zy5Wy76在 Mathematica4.1 软件包中编程如下 ［3］ ：3Solve㜽W㜽㜽㜽12㜽 13㜽㜽X㜽 Y,X㜽㜽㜽14㜽 15㜽㜽Z㜽 Y,Z㜽㜽㜽16㜽 17㜽㜽W㜽 Y,w㜽㜽㜽13㜽 14㜽㜽 X㜽 x㜽,x㜽㜽㜽14㜽 15㜽㜽 Z㜽 z㜽,z㜽㜽㜽15㜽 16㜽㜽 Y㜽 y㜽,y㜽㜽㜽16㜽 17㜽㜽 W㜽 w㜽,㜽w,x,y,z,W,X,Y,Z㜽执行后得到结果：Solve::svars㜽: 㜽Equations may notgive solutions for all "solve" variables.㜽w㜽 360318Z367903 ,x㜽 2446623Z3679030 ,y㜽 5439213Z7358060 ,z㜽 175791Z367903 ,W㜽 1113Z790 ,X㜽 801Z790 ,Y㜽 891Z1580㜽其中， 是自由变量。

求分母的最小公倍数，就可以得到整数解：LCM[367903,3679030,7358060,790,1580]执行后得到最小的 z =7358060，将其代入方程组及需求解：Z㜽 7358060;Solve㜽W㜽㜽㜽12㜽 13㜽㜽X㜽 Y,X㜽㜽㜽14㜽 15㜽㜽Z㜽 Y,Z㜽㜽㜽16㜽 17㜽㜽W㜽 Y,w㜽㜽㜽13㜽 14㜽㜽 X㜽 x㜽,x㜽㜽㜽14㜽 15㜽㜽 Z㜽 z㜽,z㜽㜽㜽15㜽 16㜽㜽 Y㜽 y㜽,y㜽㜽㜽16㜽 17㜽㜽 W㜽 w㜽,㜽w,x,y,z,W,X,Y㜽执行后得到：㜽w㜽 7206360,x㜽 4893246,y㜽 5439213,z㜽 3515820,W㜽 10366482,X㜽 7460514,Y㜽 4149387㜽即，百色母牛 （头） ，黑色母牛 （头） ，黄色母牛26x（头） ，杂色母牛 （头） ；百色公牛 （头） ，49yz 106482W黑色公牛 （头） ，黄色公牛 （头） ，杂色公牛76051X41938（头） 38Z不附加条件的群牛问题，总数最少为 4149426239697（头） ，即，大约四万一千四百九十四亿头2）附加条件的群牛问题求解方程组：、 、 、YXW31YZ514YW7164、 、 、xXw413zZ514yY615Wy76并且， 为一个三角数，即， ，其中， 是一个正整数，ZY21mZY以及 为一个长方形数，即，X完 全 问 题较 简 问 题，,*2nXW① 较简问题因为牛的身长与体宽不一样， “较简问题”表示，将牛排成长方形，两边的数目不一样。

有文章说，较简问题求解后，牛的总数近６万亿头② 完全问题（长与宽的数目相等） ，即，将牛排成正方形，两边的数目相2nXW等时，称为“完全问题” 求解完全问题，最后归结为求解二元二次方程不定方程（Pell 方程）X2 – 410286423278424Y2 = 1这个不定方程的解，已经通过计算机在几分钟之内求出这个方程的最小正整数解是名副其实的天文数字(求解结果在后面)17 世纪，费尔马重新提出求解不定方程 X2 – A*Y2 = 1 的解的问题，其中A 是正的非完全平方数他提出此方程有无穷多组正整数解同时他向所有的数学家挑战：求出此方程的无穷多组正整数解英国皇家学会的第一任会长布龙克尔勋爵（Lord Brouncker）给出了解，但他未能证明解有无穷多个瓦利斯（J. Wallis，1616--1703）彻底解决了这个问题佩尔（J. Pell，1611—1685）在他的一本著作中附录了瓦利斯的结果欧拉在他于 1732 年发表的一篇论文中错误地称 X2 – A*Y2 = 1 为 Pell 方程，这个错误就沿袭至今假设 A 是正的非完全平方数，则 是二次无理数，它的连分数循环节表A示形式是： A=8a0,8a1,a2,ܱ. ,ar<当无穷循环节中数字的个数 r 是偶数时，取 㜽A的近似分数：ܱܱ㜽㜽ܱܱܱܱܱܱܱܱܱܱܱ ܱܱܱ㜽ܱ5得到解 x、y，这就是 Pell 方程 X2 – A*Y2 = 1 的解；当无穷循环节中数字的个数 r 是奇数时，取 㜽A的近似分数：ܱܱ㜽㜽ܱܱܱܱܱܱܱܱܱܱܱ ܱܱܱܱܱܱܱܱܱܱܱܱ ܱܱܱ㜽ܱ得到解 x、y，这就是 Pell 方程 X2 – A*Y2 = 1 的解。

例 1 公元 650 年左右，首创 0 不能作除数的印度数学家 Brahmagupta（婆罗摩及塔）曾致力研究 Pell 方程 a·x2 + 1 = y2,他说：“在一年里头能解出X2 – 92Y2 = 1 的人是一位数学家” 用 Mathematica5 编程求解如下：a㜽 ContinuedFraction㜽㜽㜽92㜽n㜽 Length㜽a㜽2㜽㜽得到：{9,{1,1,2,4,2,1,1,18}}8无穷循环节中数字的个数共 8 个（即 r = 8 是偶数的情况） ，再输入：a㜽 ContinuedFraction㜽㜽㜽92㜽;a1㜽 Join㜽a㜽1㜽㜽,a㜽2㜽㜽;n㜽 Length㜽a1㜽;b㜽 Drop㜽a1,㜽n㜽;FromContinuedFraction㜽b㜽得到分数： 1151120即 x = 1151，y = 120 是此 Pell 方程 X2 – 92Y2 = 1 的最小正整数解例 2 据说有人曾向英国数学家瓦利斯提出挑战，要他解 X2 – 313Y2 = 1，结果，他在一小时之内就找到正确的答案a㜽 ContinuedFraction㜽㜽㜽㜽313n㜽 Length㜽a㜽2㜽㜽8బ ,81,2,బబబ ,1,1,3,2,2,3బబబ1,బ ,4,2,1,బ <17无穷循环节中数字的个数共 17 个（即 r = 17 是奇数的情况） ，再输入：a㜽 ContinuedFraction㜽㜽㜽㜽313 ;a1㜽 Join㜽a㜽1㜽㜽,Join㜽a㜽2㜽,a㜽2㜽㜽;n㜽 Length㜽a1㜽;b㜽 Drop㜽a1,㜽n㜽;FromContinuedFraction㜽b㜽6得到分数： 321881208291348491819380158564160即 x = 32188120829134849，y = 1819380158564160 是此 Pell 方程 X2 – 313Y2 = 1 的最小正整数解。

3）直接求解佩尔（Pell）方程的最小正整数解第一步 建立一个求解模块首先执行以下程序：PellSolve[m_Integer?Positive] := Module[ { cf, n, s },cf = ContinuedFraction[ ]; n = Length[ Last[ cf ] ];mIf[ OddQ[ n ], n = 2n ];s = FromContinuedFraction[ContinuedFraction[ , n ] ];m{ Numerator[ s ], Denominator[ s ] } ];第二步，例如，求解 Pell 方程 X2 – 92Y2 = 1 的最小正整数解，直接输入以下命令即可： PellSolve[ 92 ]得到结果：{ 1151，120 }即，x = 1151，y = 120 是 Pell 方程 X2 – 92Y2 = 1 的最小正整数解例 3 阿基米德问题 X2 – 410286423278424Y2 = 1，用现代计算机可以在几分钟之内求解程序如下：PellSolve[ 410286423278424 ] // Timing运行之后，可以知道运算时间和结果，但是得到的结果太大，不在此收录，读者自己计算即可。

另外，我们可以用以下命令求出此 Pell 方程解的位数：a = PellSolve[ 410286423278424 ];w1 = Last[ RealDigits[ a[ [ 1 ] ] ] ];Print[“w1 = ”,w1]w2 = Last[ RealDigits[ a[ [ 2 ] ] ] ];Print[“w2 = ”,w2]其中 a = PellSolve[ 410286423278424 ]运行的结果是得到 Pell 方程的最小正整数解 a = { x, y },此处 a 的第一个分量 a[ [1] ] = x, 第二个分量 a[ [2] ] = y；命令RealDigits[ a[ [1] ] ]运行的结果是得到 x = a[ [1] ] 的位数；RealDigits[ a[ [2] ] ]运行的结果是得到 y = a[ [2] ] 的位数运行后得到：x = a[ [1] ]的位数是 w1 = 103273 位，y = a[ [2] ] 的位数是 w2 = 103266 位作业（1） 求 X2 – 21Y2 = 1 的最小正整数解；（2） 求 X2 – 45Y2 = 1 的最小正整数解；（3） 求 X2 – 73Y2 = 1 的最小正整数解；7。