C学习记录0：求两数的最大公约数之辗转相除法，以及最小公倍数
先理解数学逻辑，如有不对的，请各位多多交流，谢谢！百度百科：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
辗转相除法 ：设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下：用a除以b(a≥b)，得a÷b=q......r1(0≤r1)。若r1=0，则(a，b)=b；若r1≠0，则再用b除以r1，得b÷r1=q......r2 (0≤r2）.若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个余数为0的除数即为(a, b)的最大公约数。
例如：a=25,b=15，a/b=1......10,b/10=1......5,10/5=2.......0,最后一个余数为0的除数就是5, 5就是所求最大公约数。
问题：1.(a,b)=Ra,b之间的最大公约数R,即(a,b)=r_0 为什么最后会转变为了b对余数r的最大公约数呢(b,r)=r_0？
2. 为什么是(b,r)=r_0,而不是（r,b）=r_0?
3. 为什么要走一直除到余数为0呢？
答1. 其实很简单，我们在做除法运算的时候，把被除数a，分为了2个部分。一个部分是可以被除数b整除的商q，另一个是不能被b整除的余数r。能被b整除的那部分q，余数自然为0。没有被b整除的那部分r，自然有余数。 但是此时我们要求的是a（包括能被b整除的部分，以及不能被b整除的部分）。所以，此时就相当于求不能被b整除的部分r和除数b之间的最大公因数。故(a,b)=r也可表示为(b,r)=r。
答2.因为商q的那部分能被整数，而余数r的部分不能被整除。所以是b对r求最大公约数r0。
答3.不同的a，b值，对于q有不同的选择。而我们要做的就是求出余数为0为止！ 举个例子：a=25,b=3. 商q1=1，2，3，4，5，6，7，8.每一次的商，都可以做不同的选择。但是只有余数为0的时候，最后一个式子中的除数才是，才是a，b的最大公约数，即(a,b)=r。
最小公倍数：两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。
最小公倍数=两数的乘积/最大公约（因）数
[此贴子已经被作者于2017-7-28 19:00编辑过]
