最大公约数

                                和最小公倍数

———————————————————-                                                                  —————————————

一、定义

       1）最大公约数：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）。

       2）最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数a，b的最小公倍数记为[a，b]，

             同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。

二、定理

        1）(a,b)[a,b]=ab(a,b均为整数)。即两个数的最大公约数与最小公倍数的乘积等于这两个数的相乘。

         简单证明：

          设两个数为x和y,其最大公约数为a,则
          最小公倍数为(x/a)*(y/a)*a=xy/a,
          最大公约数和最小公倍数的乘积为xy/a*a=xy
          得证

         2）如果两个数是倍数关系，则它们的最小公倍数就是较大的数。

         3）相邻的两个自然数的最小公倍数是它们的乘积。

          简单证明：（反证法）

                            只需要证明：相邻两个自然数是互质即可。

                            假设两个连续的自然数n和n+1不是互质数，设它们有公因数q(q≠1),那么必存在非０自然数p1和p2，

                            使得n=p1×q;n+1=p2×q,两式相减得n+1-n= p2×q- p1×q，即：(p2-p1)q=1,由于q≠1,所以p2-p1＝1/q为分数，这与p2、p1为整数矛盾。

                           附加：

                                  i) 两个连续的偶数只有公因数１和２。

                                （假设两个连续的偶数为２n与2n+2，由于２n÷2=n, (2n+2) ÷2=n+1, n 与n+1是连续的自然数一定是互质的，

                                    所以２n与2n+2公因数只有１和 ２。）

                                 ii)两个连续的奇数公因数只有１，是互质数。

                                （假设两个连续的奇数为２n+1与2n+3有公因数q(q≠1)，则存在非０自然数p1和p2，

                                  使得2n+1=p1×q;2n+3=p2×q,两式相减得2n+3-(2n+1)= p2×q- p1×q，  

                                  即：(p2-p1)q=2,由于p2、p1、q均为非０自然数，若p2-p1＝１，

                                  那么q＝２，则与２n+1与2n+3是奇数矛盾，若p2-p1＝２，那么q＝１与假设矛盾。）

                                 iii)推论：

                                             １、如果连续的三个自然有两个奇数一个偶数，则这三个数一定是两两互质的。它们的最小公倍数就是它们的乘积。

                                             ２、
如果连续的三个自然数有两个偶数一个奇数。则这个奇数和这两个偶数由于是相邻的自然数一定是互质的，

                                                     而这两个连续的偶数由于只有公因数１和２，所以，把这两个偶数除以它们的公因数２，所得的商一定是互质数，

                                                     因此，它们的公因数就等于这三个数的乘积再除以２。

          4）如果两个数互质，它们的最大公约数是1。

三、求解方法

•  求解最小公倍数的方法：

       1）. 直接求解法

    如果较大的数是较小的数的倍数，那么较大的数就是这两个数的最小公倍数。

    例如：求14和42的最小公倍数。

    因为42是14的倍数，所以14和42的最小公倍数是42。

 

     2）. 两数相乘法

    如果两个数是互质数，那么这两个数相乘的积就是它们的最小公倍数。

    例如：求5和7的最小公倍数。

    因为5和7是互质数，所以它们的最小公倍数是。

 

    3）. 列举倍数法

    先分别写出两个数的倍数若干个（从最小的倍数写起），依次列举出来，然后找出它们公有倍数中最小的一个，就是它们的最小公倍数。

    例如：求6和8的最小公倍数。

    6的倍数有：6、12、18、24、30、36、42、48……

    8的倍数有：8、16、24、32、40、48……

    6和8公有的倍数有：24、48……

    所以，6和8的最小公倍数是24。

 

    4）. 分解质因数法

    先分别把两个数分解质因数，然后把它们公有的质因数和各自独有的质因数连乘起来，所得的积就是这两个数的最小公倍数。

    例如：求24和36的最小公倍数。

   

    所以，24和36的最小公倍数是。

 

    5）. 短除法

    短除法实质上是分解质因数法的一种简便形式。

    求两个数的最小公倍数，先用它们的公约数连续去除（公约数可为质数，也可为合数），

     一直除到商是互质数为止，然后把所有的除数和商相乘，

    所得的积就是这两个数的最小公倍数。

    例如：求12和18的最小公倍数

   

    所以，12和18的最小公倍数是。

 

   6）. 大数翻倍法

    把较大的数依次扩大2倍、3倍、4倍……一直到所得的数是较小的数的倍数为止，这个数就是这两个数的最小公倍数。

    例如：求12和15的最小公倍数。

    把15依次扩大倍数得：，因为60正好是12的倍数，

    所以，12和15的最小公倍数是60。

 

    7）. 约分后交叉相乘法

    先把两个数写成分数的形式，然后通过约分将其化成最简分数，把分子、分母交叉相乘，所得的积就是这两个数的最小公倍数。

    例如：求15和40的最小公倍数。

    将15和40写成分数的形式，通过约分将其化成最简分数，即，所以，15和40的最小公倍数是或。

 

    8）. 比例求解法

    先把两个数写成比的形式，然后应用比的基本性质把这个比化成最简的整数比，并将这两个比写成比例的形式。

   在这个比例中，两个内项的积  或两个外项的积就是这两个数的最小公倍数。

    例如：求15和25的最小公倍数。

    将15和25写成比的形式，并把这个比化成最简的整数比：。所以，15和25的最小公倍数是或。

 

    9）. 两个数的乘积除以两个数的最大公约数法

    根据两个数的最大公约数与最小公倍数的乘积为这两个数的乘积可知，要求两个数的最小公倍数，

    就要先分别求出这两个数的乘积和它们的最 大公约数，然后用这两个数的乘积除以它们的最大公约数，所得的商就是这两个数的最小公倍数。

    例如：求8和30的最小公倍数。

    因为，8和30的最大公约数是2。

    所以，8和30的最小公倍数是。

    总之，求两个数的最小公倍数的方法很多，在解答时可以根据具体情况，灵活地选用比较简便的方法，正确求出两个数的最小公倍数。

四、利用上面的【定义-定理-方法】结合运用java编程语言实现。

        注：由于两个数的最小公倍数等于两个数的乘积除以最大公约数。所以，这里只要求出最大公约数即可。

/**
 * 问题：求两个数的最大公约数
 * 解决方法：欧几里得的辗转相除法
 * @author xiaoxiaolan
 *
 */
public class Gcd {

	public static void main(String[] args) {
		int m = 686996996, n = 53435566;
		System.out.println("求解" + m + "和" + n + "的最大公约数。");
		System.out.println("欧几里得的辗转相除算法实现:");
		System.out.println(divisor(m, n));

		System.out.println("Stein算法实现:");
		System.out.println(gcd(m, n));

	}

	/**
	 * 这个是使用java中的递归方法实现辗转相除法
         * 传统算法与证明： 定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
	 * 证明：a可以表示成a = kb+ r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a,d|b，而r = a - kb，因此d|r 因此d也是（b,a mod b）
	 * 的公约数 因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证
	 * @param m
	 * @param n
	 * @return
	 */
	private static int divisor(int m, int n) {
		if (m % n == 0) {
			return n;
		} else {
			return divisor(n, m % n);
		}
	}

	

	/**
	 * 和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
	 * 为了说明Stein算法的正确性，首先必须注意到以下结论： gcd(a,a) = a，也就是一个数和他自身的公约数是其自身 gcd(ka,kb) =
	 * k gcd(a,b），也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcd(int a, int b) {
		if (a < b) // arrange so that a>b
		{
			int temp = a;
			a = b;
			b = temp;
		}
		if (0 == b) // the base case
			return a;
		if (a % 2 == 0 && b % 2 == 0) // a and b are even
			return 2 * gcd(a / 2, b / 2);
		if (a % 2 == 0) // only a is even
			return gcd(a / 2, b);
		if (b % 2 == 0)// only b is even
			return gcd(a, b / 2);
		return gcd((a - b) / 2, b);// a and b are odd
	}

}

五、小结：（设计算法来解决可计算问题的基本步骤）

• 收集当前问题的基本结论与可用定理，并对它们进行筛选，优化，组合预测。
• 选择合理的数据结构来存储数据材料。
• 规划算法步骤。
• 编码
• 验证