Introduction

Modular arithmetic is a system of arithmetic for integers, which considers the remainder when dividing by a specific number, called the modulus. It is a powerful tool in computer science and competitive programming, particularly in problems involving large numbers, combinatorics, and cryptography, allowing us to work with smaller values and prevent integer overflows. This document will cover key concepts like modular inverse, solving modular equations, and techniques for calculating modular inverse using the Extended Euclidean Algorithm and Fermat's Little Theorem, along with linear congruences, and provide Java implementations suitable for competitive programming.

Modular Inverse

The modular inverse of an integer a modulo m is an integer x such that (a * x) % m == 1. In other words, a * x ≡ 1 (mod m). The modular inverse exists if and only if a and m are coprime (i.e., their greatest common divisor (GCD) is 1).

Mathematically, if gcd(a, m) = 1, then a^-1 ≡ x (mod m) is the modular inverse of a modulo m.

Solving Modular Equations

Modular equations are equations that involve modular arithmetic. A simple modular equation is of the form ax ≡ b (mod m). To solve this, we first need to find the modular inverse of a modulo m (if it exists). If the modular inverse, a^-1, exists, we can multiply both sides of the equation by it: a^-1 * ax ≡ a^-1 * b (mod m), which simplifies to x ≡ a^-1 * b (mod m).

Calculating Modular Inverse using the Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only calculates the GCD of two numbers a and b but also finds integers x and y such that ax + by = gcd(a, b). If gcd(a, m) = 1, then ax + my = 1. Taking this equation modulo m, we get ax ≡ 1 (mod m). Therefore, x is the modular inverse of a modulo m. Since x might be negative, we can add m to it until it becomes positive and still remains within the same modulo class. For example, if x = -2 and m = 5, then -2 ≡ 3 (mod 5).

Java Implementation

 public class ModularInverseExtendedEuclidean {

    public static long extendedEuclidean(long a, long b) {
        if (b == 0) {
            return a;
        }
        return extendedEuclidean(b, a % b);
    }

    public static long[] extendedEuclideanWithCoefficients(long a, long b) {
        if (b == 0) {
            return new long[] {a, 1, 0}; // gcd, x, y
        }

        long[] result = extendedEuclideanWithCoefficients(b, a % b);
        long gcd = result[0];
        long x1 = result[1];
        long y1 = result[2];

        long x = y1;
        long y = x1 - (a / b) * y1;

        return new long[] {gcd, x, y};
    }


    public static long modularInverse(long a, long m) {
        long[] result = extendedEuclideanWithCoefficients(a, m);
        long gcd = result[0];
        long x = result[1];

        if (gcd != 1) {
            return -1; // Modular inverse does not exist
        }

        long inverse = (x % m + m) % m; // Ensure the result is positive
        return inverse;
    }

    public static void main(String[] args) {
        long a = 3;
        long m = 11;

        long inverse = modularInverse(a, m);

        if (inverse != -1) {
            System.out.println("The modular inverse of " + a + " modulo " + m + " is " + inverse); // Output: 4
        } else {
            System.out.println("Modular inverse does not exist.");
        }

        // Example of solving the modular equation 3x ≡ 5 (mod 11)
        long b = 5;
        if(inverse != -1){
            long solution = (inverse * b) % m;
            System.out.println("Solution to 3x ≡ 5 (mod 11) is x ≡ " + solution + " (mod " + m + ")"); //Output: x ≡ 8 (mod 11)
        }

    }
} 

Calculating Modular Inverse using Fermat's Little Theorem

Fermat's Little Theorem states that if p is a prime number, then for any integer a not divisible by p, a^p-1 ≡ 1 (mod p). This can be rearranged to a * a^p-2 ≡ 1 (mod p). Therefore, the modular inverse of a modulo p is a^p-2 (mod p). This method only works when m is a prime number.

Java Implementation

 public class ModularInverseFermat {

    public static long power(long base, long exp, long modulus) {
        long res = 1;
        base %= modulus;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % modulus;
            base = (base * base) % modulus;
            exp /= 2;
        }
        return res;
    }

    public static long modularInverse(long a, long p) {
        if (a % p == 0) {
            return -1; // No inverse exists
        }
        return power(a, p - 2, p);
    }

    public static void main(String[] args) {
        long a = 3;
        long p = 11; // Prime number

        long inverse = modularInverse(a, p);

        if (inverse != -1) {
            System.out.println("The modular inverse of " + a + " modulo " + p + " is " + inverse); // Output: 4
        } else {
            System.out.println("Modular inverse does not exist.");
        }

        // Example of solving the modular equation 3x ≡ 5 (mod 11)
        long b = 5;
        if(inverse != -1){
            long solution = (inverse * b) % p;
            System.out.println("Solution to 3x ≡ 5 (mod 11) is x ≡ " + solution + " (mod " + p + ")"); //Output: x ≡ 4 (mod 11)
        }
    }
} 

Solving Linear Congruences

A linear congruence is an equation of the form ax ≡ b (mod m), where a, b, and m are integers, and we want to find an integer x that satisfies the congruence. This is equivalent to finding an integer x such that ax - b is divisible by m, meaning ax - b = my for some integer y, or ax - my = b.

To solve ax ≡ b (mod m):

1. Check for existence of a solution: A solution exists if and only if gcd(a, m) divides b. Let g = gcd(a, m). If b is not divisible by g, then there are no solutions.
2. Simplify the congruence: If a solution exists (g divides b), divide all terms (a, b, and m) by g. This results in the congruence: (a/g)x ≡ (b/g) (mod (m/g)). Let a' = a/g, b' = b/g, and m' = m/g. So, we now have: a'x ≡ b' (mod m'). Note that now gcd(a', m') = 1.
3. Find the modular inverse: Find the modular inverse of a' modulo m', denoted as (a')^-1. This can be done using either the Extended Euclidean Algorithm or Fermat's Little Theorem (if m' is prime).
4. Solve for x: Multiply both sides of the simplified congruence by the modular inverse (a')^-1: (a')^-1 * a'x ≡ (a')^-1 * b' (mod m'), which simplifies to x ≡ (a')^-1 * b' (mod m').
5. Find all solutions modulo m: The solution x found in the previous step is a solution modulo m'. To find all solutions modulo m, the general solution is given by x = x₀ + k * (m/g), where x₀ is the solution found modulo m' and k is an integer such that 0 ≤ k < g. This gives g distinct solutions modulo m.

Java Implementation

 public class LinearCongruenceSolver {

    public static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static long[] extendedEuclidean(long a, long b) {
        if (b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] result = extendedEuclidean(b, a % b);
        long gcd = result[0];
        long x1 = result[1];
        long y1 = result[2];
        long x = y1;
        long y = x1 - (a / b) * y1;
        return new long[]{gcd, x, y};
    }

    public static long modularInverse(long a, long m) {
        long[] result = extendedEuclidean(a, m);
        long gcd = result[0];
        long x = result[1];
        if (gcd != 1) {
            return -1; // Inverse doesn't exist
        }
        return (x % m + m) % m; // Ensure positive result
    }

    public static void solveLinearCongruence(long a, long b, long m) {
        long g = gcd(a, m);

        if (b % g != 0) {
            System.out.println("No solutions exist.");
            return;
        }

        long aPrime = a / g;
        long bPrime = b / g;
        long mPrime = m / g;

        long inverseA = modularInverse(aPrime, mPrime);

        if (inverseA == -1) {
            System.out.println("No solutions exist (inverse error).");
            return;
        }

        long x0 = (inverseA * bPrime) % mPrime;

        System.out.println("Solutions modulo " + m + ":");
        for (int k = 0; k < g; k++) {
            long x = (x0 + k * mPrime) % m;
            System.out.println("x ≡ " + x + " (mod " + m + ")");
        }
    }

    public static void main(String[] args) {
        // Example: Solve 3x ≡ 6 (mod 15)
        long a = 3;
        long b = 6;
        long m = 15;
        solveLinearCongruence(a, b, m);


        // Example: Solve 14x ≡ 30 (mod 100)
        a = 14;
        b = 30;
        m = 100;
        solveLinearCongruence(a, b, m);
    }
} 

The above code finds all possible solutions to the linear congruence modulo m.