辗转相除法C语言 辗转相除

今天来聊聊关于辗转相除法C语言，辗转相除的文章，现在就为大家来简单介绍下辗转相除法C语言，辗转相除，希望对各位小伙伴们有所帮助。

1、欧几里得原本第七册的第一、二个命题告诉我们如何用辗转相除法求两整数的最大公约数。

2、辗转相除法看起来是雕虫小技，其实它还与非比数、二元一次不定方程式、算术基本定理、中国剩余定理、连分数等都有关联，可以说是数学发展中的一大成就。

3、 首先以求123及48两数的最大公约数3为例，复习一下辗转相除法。

4、辗转相除的计算过程如下: 123=2×48+27 48=1×27+21 27=1×21+6 21=3×6+3 6=2×3 以乙数除甲数，得余数丙;再以丙除乙，得余数丁。

5、如此辗转进行，最后整除无余数时，该除数就是甲乙两数的最大公约数。

6、希腊人常以线段代表数。

7、甲乙两数可以看成长度分别为甲乙两数的直尺。

8、辗转相除的意思就是拿矩尺去量长尺;若有剩余，再用剩余部分为尺，去量原来的短尺，如此继续下去。

9、如果两尺长度之比为有理数，经过辗转相量，在有限次内，总会有量尽的时候。

10、若用最后量尽时所用的尺回头分别来量原来的两把尺，也是会量尽的。

11、希腊人就说这两把尺(两个线段、两个数)是可共度的。

12、(用代数的观点来看，若两线段的长度比为m:n，m、n都是整数，则把第一线段n等分所得的小线段，可以同时量尽这两线段。

13、)原先希腊人以为任何两线段都是可共度的，后来才发现问题不那么简单。

14、我们看看下面两个例子。

15、首先我们研究正五边形ABCDE的一边AB和一对角线BE是否可共度的问题。

16、由简单的计算可知:图一中标有1的角度为36°，标有2者为72°。

17、因此AB=FB，BG=EF=FH。

18、以AB(=BF)量BE，就剩下EF;以EF(=BG )量AB(=BF)，就剩下GF;以GF量EF就是以GF量HF，也就是在中间这个小的正五边形中，以其一边量其一对角线。

19、同理，这样度量下去，焦点又会转向更小的正五边形。

20、如此下去，一个又一个更小的正五边形相继出现，永远没有量尽的时候;也就是说正五边形的一边及一对角线是无法共度的。

21、用现在的眼光来看，任何两线段的长度之比不一定是整数比，也就是说长度相除所得的不一定是比数(即有理数)，譬如在正五边形中，对角线与一边之比为(√5+1)/2就不是比数。

22、这是希腊人遭遇到非比数(即无理数)困扰的一个例子。

23、等腰直角三角形的斜边与一股，它们的比√2不是有理数是大家所熟知的。

24、用互相度量的观点可以解释如下:在图二中，作＜C的平分线交AB于D，从D点作AC的垂线DE。

25、很容易得知CE=BC=AB，AE=DE=BD。

26、所以用AB(=CE)量AC，剩下AE;用AE(=BD)量AB，剩下AD;因AD比AE还长，所以要再用AE量AD。

27、这就变成一个较原来为小的等腰直角三角形AED中，斜边与一股的度量问题。

28、和上个例子一样，一个又一个较小的等腰直角三角形会陆续出现，永远没有量尽的时候。

29、这就是说等腰直角三角形的斜边及一股是不可共度的。

30、 非比数的出现，使希腊人不得不舍弃毕氏学派所持的数学观，另外发展一套比例的理论。

31、(注一) 通常要证明√2是非比数(无理数)，都利用算术基本定理(整数因数分解唯一)，欧几里得的原本也是。

32、算术基本定理的证明却要基于辗转相除法的另一个结果。

33、 辗转相除法不但告诉我们如何求两整数a、b的最大公约数c，而且告诉我们如何解出ax+by=c的x、y。

34、以a=123、b=48、c=3为例，我们把求c所得的算式从最后第二式倒回去，得 3=21-3×6 =21-3×(27-1×21) =-3×27+4×21 =-3×27+4×(48-1×27) = 4×48-7×27 =4×48-7×(123-2×48) =-7×123+18×48因此就得x=-7, y=18。

35、这种方法也适用于任何a、b。

36、一般二元一次方程式ax+by=c(c不一定是a、b的最大公约数)整数解的讨论可以以此为基础(注二)，而其讨论，在西方，由Euler(1707~1783年)全其功;在中国，由南宋秦九韶定其型。

37、算术基本定理的前导就是如下的性质:如果质数p能整除ab，则p要整除a或b。

38、这个性质可用上面所提辗转相除法的第二个结果来说明:假设p不整除a，则因p是质数，所以a与p互质，因此可以找到x、y，使得ax+py=1。

39、全式乘以b，就得abx+pby=b。

40、因为p能整除上式左边的两项，所以也能整除右边的b。

41、从上面的分析，通常用来证明√2为无理数的方法看似简单，实则要由辗转相除法经过多方转折才能得到，倒不如用辗转相除法的几何观点来得直接、来得朴实。

42、话虽这么说，算术基本定理到底是辗转相除这种朴实方法所得出的一个精致的结果，用来证明√2为无理数，也不过是牛刀小试。

43、在孙子算经中有这样的题目:「今有物不知其数。

44、三三数之，剩二;五五数之，剩三;七七数之，剩二。

45、问物几何?」这就是说要求得一数x，使得x除以3则余2，除以5则余3，除以7则余2。

46、这类问题的推广与求解就是所谓的中国剩余定理。

47、问题可推广为:设mm2、…、mn为两两互质的正整数，rr2、…、rn为任意整数。

48、求一整数x，使得x除以mj后，余数为 rj。

49、解决问题的想法可分成两步骤:一、固定i，若能找到ai，使得 ai除以mi，余数为1，而除以mj(j≠i)，余数为0 。

50、令x0=r1a1+r2a2+…+rnan，则x的通解就是x=x0+kM(M=m1m2…mn，k为任意整数)。

51、 这种想法是叠合法的典型，在数学中经常用到。

52、有了这种想法，自然会利用辗转相除解二元一次方程式的方法，而有 二、固定i。

53、令Mi=m1m2…mi-1mi+1…mn。

54、因为mi与Mi互质，所以可以找到xi、yi，使得mixi+Miyi=1。

55、那么ai=Miyi=1-mixi就有我们所要的性质。

56、 中国剩余定理还可再推广到代数数论等，是现代数论中的一个重要定理。

57、秦九韶在其数书九章中介绍求一术。

58、他所说的「以少除多，递互除之」正是辗转相除法。

59、所谓求一就是利用辗转相除法求得两互质之数的最大公约数1。

60、此外他还指出如何求解二元一次方程式及中国剩余定理。

61、「物不知其数」这种趣味性的问题固然使有关的数学引人注意，但这些数学的研究更应溯源于天文历法的需要。

62、如果有n颗星球，其周期各为mi天，假定在x天前，这几颗星球排成一直线，而今天第i个星球(绕了不知多少圈后)离开此直线有ri天。

63、如果mi、ri都知道，求x的问题就是中国剩余定理的问题。

64、古时创新历法时，历算家总想根据新历法(mi、ri可能和旧的历法不同)以求x值;根据新历法，x天前这些星球都排成一列，正好可以用来做为新历法的纪元--称为上元积年。

65、历算家对上元积年有兴趣，因此致力于研究剩余定理及相关的数学。

66、元朝以后，当历算家对上元积年失去兴趣，这一套数学也跟著在中算史中消失无影，直到清朝中叶数学家「考古」，才又重现。

67、 最后还要看看辗转相除法和连分数的关系。

68、把a、b两数辗转相除的过程用分数表出，马上就看出它其实就是求a/b的连分数过程。

69、以a=123、b=48为例，根据前面的计算，我们可得 【浏览原件】【浏览原件】a、b两数其实可以不限于整数，一样可以辗转相除，而当a/b为无理数时，它的连分数就无穷无尽。

70、连分数在分数逼进理论及解不定方程式等方面都有重大的贡献，是数论中重要而有趣的一个分支。

71、(注三) 朴实的辗转相除法辗转结出各种精致的数学美果。

相信通过辗转相除这篇文章能帮到你，在和好朋友分享的时候，也欢迎感兴趣小伙伴们一起来探讨。