public static Pair<Integer, Integer> linearCongruence(int a, int b, final int n) {
        positiveCheck(n);
        a = normalizeIntModulo(a, n);
        b = normalizeIntModulo(b, n);
        if (((a == 0) && (b == 0)) || (n == 1))
            return new Pair<>(0, 1);
        
        final int numberOfSolutions = gcd(a, n);
        if (b % numberOfSolutions != 0)
            return new Pair<>();
        
        int bezoutCoefficientA; // coeffient r such that ra + sn = gcd(a, n)
        if (a > n)
            bezoutCoefficientA = bezout(a, n).get(1);
        else
            bezoutCoefficientA = bezout(n, a).get(2);

        final int shiftedModulus = n / numberOfSolutions;
        int x = (bezoutCoefficientA * b) / numberOfSolutions;
        x = normalizeIntModulo(x, shiftedModulus);
        return new Pair<>(x, shiftedModulus);
    }