Modular Arithmetic in Competitive Programming

Introduction to Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value, called the modulus. It's a crucial concept in number theory and is extensively used in competitive programming for handling large numbers and avoiding overflow errors.

The modulus is typically denoted by n, and we say that two integers a and b are congruent modulo n, written as a ≡ b (mod n), if their difference (a - b) is divisible by n. In other words, a and b have the same remainder when divided by n.

Modular Arithmetic: Properties and Operations

Properties

• Reflexivity: a ≡ a (mod n)
• Symmetry: If a ≡ b (mod n), then b ≡ a (mod n)
• Transitivity: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)

Operations

Modular Addition

(a + b) mod n = (a mod n + b mod n) mod n

This means you can add the remainders when a and b are divided by n, and then take the remainder of the result when divided by n.

 // Java code for modular addition
    public static int modularAddition(int a, int b, int n) {
        return (a % n + b % n) % n;
    } 

Modular Subtraction

(a - b) mod n = (a mod n - b mod n + n) mod n

We add n to the result before taking the modulo to ensure a positive result, as Java's modulo operator can return negative values when the first operand is negative.

 // Java code for modular subtraction
    public static int modularSubtraction(int a, int b, int n) {
        return (a % n - b % n + n) % n;
    } 

Modular Multiplication

(a * b) mod n = (a mod n * b mod n) mod n

Similar to addition, we can multiply the remainders and then take the modulo. However, be careful about potential integer overflow if a * b is large. Use long data type to prevent it, and apply the mod operator often.

 // Java code for modular multiplication
    public static long modularMultiplication(long a, long b, long n) {
        return (a % n * b % n) % n;
    } 

Modular Division (Modular Inverse)

Modular division is not as straightforward as the other operations. We cannot directly divide in modular arithmetic. Instead, we multiply by the modular multiplicative inverse.

The modular multiplicative inverse of an integer a modulo n exists if and only if a and n are coprime (their greatest common divisor is 1). The inverse of a modulo n, denoted as a-1 (mod n), is an integer x such that (a * x) ≡ 1 (mod n).

To calculate the modular inverse, we can use the Extended Euclidean Algorithm or Fermat's Little Theorem (when n is prime). Let's demonstrate using the Extended Euclidean Algorithm.

 // Java code for calculating modular inverse using Extended Euclidean Algorithm
    public static long modularInverse(long a, long n) {
        long m0 = n;
        long y = 0, x = 1;

        if (n == 1)
            return 0;

        while (a > 1) {
            // q is quotient
            long q = a / n;
            long t = n;

            // n is remainder now, process same as
            // Euclid's algo
            n = a % n;
            a = t;
            t = y;

            // Update y and x
            y = x - q * y;
            x = t;
        }

        // Make x positive
        if (x < 0)
            x += m0;

        return x;
    }

    //Java code for modular division

    public static long modularDivision(long a, long b, long n){
        long inverse_b = modularInverse(b, n);
        return (a % n * inverse_b % n) % n;
    } 

Fermat's Little Theorem and Euler's Theorem

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, ap-1 ≡ 1 (mod p).

This theorem is useful for calculating modular inverses when the modulus is prime. Specifically, if p is prime and a is not divisible by p, then a-1 ≡ ap-2 (mod p).

 // Java code for calculating modular inverse using Fermat's Little Theorem
    // Only works when n is prime
    public static long modularInverseFermat(long a, long n) {
        return power(a, n - 2, n);
    }

    // Helper function for calculating (base^exp) % mod using binary exponentiation
    public static long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    } 

Euler's Theorem

Euler's Theorem is a generalization of Fermat's Little Theorem. It states that if a and n are coprime (their greatest common divisor is 1), then aφ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.

Euler's totient function, φ(n), counts the number of positive integers less than or equal to n that are relatively prime to n.

If a and n are coprime, then a-1 ≡ aφ(n)-1 (mod n).

 // Java code for calculating Euler's Totient Function
    public static long phi(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }

    // Java code for calculating modular inverse using Euler's Theorem
    public static long modularInverseEuler(long a, long n) {
        long phi_n = phi(n);
        return power(a, phi_n - 1, n);
    }