连分数与佩尔方程的最小整数解

连分数与佩尔（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】连分数示法 一个“既约”分数（分子可以比分母大，但无公因子）可以表示成连分数的形式。例如将 表示成连分数，程序如下： ContinuedFraction[ ] 得到结果：{0，1，1，1，5}。这表示 二次整系数方程的根叫做二次无理数。 初等数论中已经证明：一切二次无理数表示成连分数，都具有无穷循环节。例如将表示成连分数，程序如下： ContinuedFraction[] 得到结果：{4，{3，6}}。这表示 其中{3，6}用花括号括起来，表示无穷循环节。 反之，我们可以通过一个数的连分数表示形式求其正常形式。例如： FromContinuedFraction[{ 1，2，3 }] 得到结果： 。这表示：连分数 又例如， FromContinuedFraction[ { 2, 1, { 4, 2, 3 } } ] 得到结果：。这表示： 【2】佩尔（Pell）方程的最小正整数解 公元前３世纪下半叶古希腊科学家阿基米德（Archimedes，公元前287—公元前212年）在其论著中记载了一个牲畜问，普遍称作群牛问题。历史上对这问题的研究丰富了初等数论的内容。 原文用诗句写成，大意是：西西里岛草原上有一大群牛，公牛和母牛各有４种颜色。设 、 、 、 分别表示白、黑、黄、花色的公牛数， 、 、 、 分别表示这白、黑、黄、花色的母牛数。它们满足： 、 、 、 、 、 、 （1）不附加条件的群牛问题 求解方程组： 、 、 、 、 、 、 在Mathematica4.1软件包中编程如下［3］： 执行后得到结果： 其中， 是自由变量。求分母的最小公倍数，就可以得到整数解： LCM[367903,3679030,7358060,790,1580] 执行后得到最小的z =7358060，将其代入方程组及需求解： 执行后得到： 即，百色母牛 （头），黑色母牛 （头），黄色母牛 （头），杂色母牛 （头）；百色公牛 （头），黑色公牛 （头），黄色公牛 （头），杂色公牛 （头）。 不附加条件的群牛问题，总数最少为4149426239697（头），即，大约四万一千四百九十四亿头。 （2）附加条件的群牛问题 求解方程组： 、 、 、 、 、 、 并且， 为一个三角数，即， ，其中， 是一个正整数，以及 为一个长方形数，即， 1 较简问题 因为牛的身长与体宽不一样，“较简问题”表示，将牛排成长方形，两边的数目不一样。有文章说，较简问题求解后，牛的总数近６万亿头。 2 完全问题 （长与宽的数目相等），即，将牛排成正方形，两边的数目相等时，称为“完全问题”。求解完全问题，最后归结为求解二元二次方程不定方程（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是正的非完全平方数，则 是二次无理数，它的连分数循环节表示形式是： 当无穷循环节中数字的个数r是偶数时，取的近似分数： 得到解x、y，这就是Pell方程X2 – A*Y2 = 1的解； 当无穷循环节中数字的个数r是奇数时，取的近似分数： 得到解x、y，这就是Pell方程X2 – A*Y2 = 1的解。 例1 公元650年左右，首创0不能作除数的印度数学家Brahmagupta（婆罗摩及塔）曾致力研究Pell方程a·x2 + 1 = y2,他说：“在一年里头能解出 X2 – 92Y2 = 1的人是一位数学家”。用Mathematica5编程求解如下： 得到： {9,{1,1,2,4,2,1,1,18}} 8 无穷循环节中数字的个数共8个（即r = 8是偶数的情况），再输入： 得到分数： 即x = 1151，y = 120是此Pell方程X2 – 92Y2 = 1的最小正整数解。 例2 据说有人曾向英国数学家瓦利斯提出挑战，要他解X2 – 313Y2 = 1，结果，他在一小时之内就找到正确的。 17 无穷循环节中数字的个数共17个（即r = 17是奇数的情况），再输入： 得到分数： 即x = 32188120829134849，y = 1819380158564160是此Pell方程X2 – 313Y2 = 1的最小正整数解。 （3）直接求解佩尔（Pell）方程的最小正整数解 第一步 建立一个求解模块。首先执行以下程序： PellSolve[m_Integer?Positive] := Module[ { cf, n, s }, cf = ContinuedFraction[ ]; n = Length[ Last[ cf ] ]; If[ OddQ[ n ], n = 2n ]; s = FromContinuedFraction[ContinuedFraction[ , n ] ]; { 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的最小正整数解； PAGE 6 _1204357017.unknown _1204357483.unknown _1204357636.unknown _1204357700.unknown _1204357728.unknown _1204357762.unknown _1204357666.unknown _1204357602.unknown _1204357444.unknown _1204349650.unknown _1204349933.unknown _1204350128.unknown _1204350219.unknown _1204350295.unknown _1204354305.unknown _1204350162.unknown _1204349969.unknown _1204350050.unknown _1204349766.unknown _1204349843.unknown _1204349713.unknown _1204349587.unknown _1204349608.unknown _1204349617.unknown _1204349597.unknown _1204349539.unknown _1204349563.unknown _1204349575.unknown _1204349550.unknown _1098254820.unknown _1098256393.unknown _1204349486.unknown _1100325143.unknown _1098255819.unknown _1098254781.unknown