连分数

简单的想法　　

设两数为a、b(b＜a)，求它们最大公约数(a，b)的步骤如下：

用b除a，得a＝b×q+r(0≤r)。若r=0，则(a，b)＝b；若r≠0，则再用r除b，得b＝r×q+r2 (0≤r2).若r2＝0，则(a，b)＝r，若r2≠0，则继续用r2除r,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

 

原理及其详细证明　　

在介绍这个方法之前，先说明整除性的一些特点（下文的所有数都是正整数，不再重复），我们可以这样给出：

   整除的定义：

　　对于二个自然数a和b，若存在正整数q，使a=b×q，则a能被b整除，b为a的因子，a为b的倍数。

　　如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。

    由此我们可以得出以下推论：

　　推论1：如果a能被b整除（a=q×b），若k为正整数，则ka也能被b整除（k×a=k×q×b）

　　推论2：如果a能被c整除（a=h×c），b也能被c整除（b=t×c），则(a±b)也能被c整除

　　       ∵将二式相加：a+b=h×c+t×c=(h+t)×c；同理，二式相减：a－b=h×c－t×c=(h－t)×c

　　       ∴(a±b)也能被c整除

　　推论3：如果a能被b整除（a=q×b），b也能被a整除（b=t×a），则a=b

　　       ∵a=q×b　b=t×a　a=q×t×a，

            ∴q×t=1

            ∵q、t均为正整数，

            ∴t=q=1

            ∴a=b

辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。

其理论如下:

　　如果 q 和 r 是 m 除以 n 的商及余数，即 m=n×q+r，则 gcd(m,n)=gcd(n,r)。

　　证明:

    设 a=gcd(m,n)，b=gcd(n,r)  

　　∵a为m,n的最大公约数，

　　∴m能被a整除，且n也能被a整除，

　　∴由推论1得：qn也能被a整除，

　　∴ 由推论2得：m-qn也能被a整除，

　　又 ∵m-qn=r，

　　∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）

　　∵b为n和r的最大公约数，a为n和r的公约数

　　∴a≤b，

　　同理，

　　∵b为n, r的最大公约数，

　　∴n能被b整除，且r也能被b整除，

　　∴由推论1得：qn也能被b整除，

　　∴由推论2得：qn+r也能被b整除，

　　又∵m=qn+r，

　　∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）

　　∵a为m,n的最大公约数，b为m和n的公约数，

　　∴b≤a，

　　由以上可知：

　　a≤b与b≤a同时成立，

　　故可得

　　a=b，

　　证毕。

最小公倍数：

根据：（a，b）（最大公约数）×[a，b]（最小公倍数）=a×b，得到最小公倍数。

连分数：（竖式写法）

      

 

 

上一篇：阴历
下一篇：蚂蚁人生