最大公约数问题(欧几里得算法)

讨论范围为自然数(N)范围

题目描述：求m,n的最大公约数Xmax，m > n, m,n∈N

分析：

　　m(0) =m(input), n(0) = n(input)求 Xmax 满足 :

　　m(input) % Xmax = 0  ①

　　n(input) % Xmax = 0  ②

       因为 m(input) > n(input) ,所以m(input)可以表示为 m(input) = a *  n(input)+ m(input) % n(input)  代入到 ①  中有

　　m(input) % Xmax = [m(input) % n(input)] % Xmax = 0 ③

　　因为[m(input) % n(input)] < n(input)

　　② ③系数对等 n(n) = n(n-1) * m(n -1) ,x(n) = n(n)

　　① ②系数对等m(n) = n(n-1)

　　x(0) = n(0)

程序：

   public static int gcdEuclidean(int m, int n) {
        if (m % n == 0) {
            return n;
        }
        return gcdEuclidean(n, m % n);
    }