Java求最大公约数（带算法详细解释）-蒲公英云

Java求最大公约数（带算法详细解释）

Java求最大公约数-带算法证明

- - 关键代码
  - 证明：两个数的最大公约数等于两个数的余数和小的整数的最大公约数
  - 结论

关键代码

/**
     * 其中a > b
     * @param a
     * @param b
     * @return
     */
    public static int maxDivisor(int a, int b){
        int n = a;
        int m = b;
        int r = 0;
        while(m!=0){
            r = n%m;
            n = m;
            m = r;
        }
        return n;
    }

证明：两个数的最大公约数等于两个数的余数和小的整数的最大公约数

假设a、b的最大公约数为d（a > b）,其中a % b = r（r > 0）,求证b、r的最大公约数也是d
证明过程
因为a、b的最大公约数为d，故a = xd、b = yd；
因为a % b = r，故a = zb + r，故a = yzd + r = xd，故r = (x - yz)d，即r整除d；
故d时b、r的约数。下面证明约数的范围。

假设b、r有约数g，则 b = ng、r = mg，则a = zng + mg = (zn + m)g，则g也是a、b的约数；
由于a、b的最大公约数为d，故g <= d，所以b、r最大公约数为d