当前位置：首页 > Java

java如何求同余

2026-03-24 07:21:13Java

同余的概念

在数学中，同余是指两个整数除以同一个正整数后余数相同。表示为 $a \equiv b \pmod{m}$，表示 $a$ 和 $b$ 除以 $m$ 后余数相同。

Java中实现同余运算

Java中可以通过取模运算符 % 来实现同余的判断。具体方法是检查两个数对模数的取模结果是否相等。

public class Congruence {
    public static boolean isCongruent(int a, int b, int m) {
        return (a % m) == (b % m);
    }

    public static void main(String[] args) {
        int a = 17;
        int b = 5;
        int m = 6;
        System.out.println(isCongruent(a, b, m)); // 输出 true，因为 17 % 6 = 5，5 % 6 = 5
    }
}

处理负数的情况

Java的取模运算 % 对于负数可能返回负余数，而数学上的同余要求余数为非负数。可以通过调整取模结果来正确处理负数。

public static int mod(int a, int m) {
    return (a % m + m) % m;
}

public static boolean isCongruent(int a, int b, int m) {
    return mod(a, m) == mod(b, m);
}

扩展：求解线性同余方程

对于形如 $ax \equiv b \pmod{m}$ 的线性同余方程，可以通过扩展欧几里得算法求解。

java如何求同余

public static int[] extendedGCD(int a, int b) {
    if (b == 0) {
        return new int[]{a, 1, 0};
    }
    int[] vals = extendedGCD(b, a % b);
    int d = vals[0];
    int x = vals[2];
    int y = vals[1] - (a / b) * vals[2];
    return new int[]{d, x, y};
}

public static int solveLinearCongruence(int a, int b, int m) {
    int[] vals = extendedGCD(a, m);
    int d = vals[0];
    if (b % d != 0) {
        throw new RuntimeException("No solution exists");
    }
    int x0 = (vals[1] * (b / d)) % m;
    if (x0 < 0) {
        x0 += m;
    }
    return x0;
}