1. 最大公约数

欧几里得算法(辗转相除法)求最大公约数(Greatest Common Divisor，GCD)的递归定理：对任意非负整数a和任意正整数b

欧几里得算法递归实现：

// 欧几里得算法递归实现
public static int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

欧几里得算法非递归实现：

// 欧几里得算法非递归实现
public static int gcd(int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

2. 最小公倍数

求最小公倍数代码实现：

// 求最小公倍数
public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

3. 模取幂

模取幂：求一个数的幂对另一个数的模运算，

// 模取幂：Math.pow(a, b) % n
// a, b为非负整数，n为正整数
public static int modularExponentiation(int a, int b, int n) {
    int c = 0;
    int d = 1;
    String binaryB = Integer.toBinaryString(b);
    for (int i = 0; i < binaryB.length(); i++) {
        c *= 2;
        d = (d * d) % n;
        if (binaryB.charAt(i) == '1') {
            c++;
            d = (d * a) % n;
        }
    }
    return d;
}