Modular Addition Rules

Adding in a Circle

In the last section, we saw how modular arithmetic works like a clock, wrapping numbers around a fixed value called the modulus. This is great for telling time or cycling through an array. But what happens when we need to add numbers in this system, especially very large ones?

Let's say we want to find the remainder of a large sum when divided by some number. You could add everything up first and then find the remainder. Or, you could use a handy property of modular arithmetic that makes the job much easier and safer, especially in programming.

The remainder of a sum is the same as the sum of the remainders.

This idea is captured in the modular addition rule. It states that adding two numbers and then taking the modulo is equivalent to taking the modulo of each number first, adding them, and then taking the modulo of that result.

(a + b) \pmod n = ((a \pmod n) + (b \pmod n)) \pmod n

Let's use our clock example with a modulus of 12. Imagine you want to calculate $(10 + 5) \pmod{12}$ .

Following the left side of the rule, you'd do $10 + 5 = 15$ , and then $15 \pmod{12} = 3$ .

Now let's try the right side. First, get the remainders: $10 \pmod{12} = 10$ and $5 \pmod{12} = 5$ . Now add them: $10 + 5 = 15$ . Finally, take the modulo of the result: $15 \pmod{12} = 3$ .

Both paths lead to the same answer. While this seems like extra work for small numbers, it's a lifesaver when dealing with big ones.

Why This Matters for Computers

Computers store numbers in fixed-size containers. For example, a standard integer type in C++, int, can only hold numbers up to a certain size. If you try to store a number larger than its maximum limit, it causes a problem called integer overflow.

Think of it like a car's odometer. If it only has six digits, what happens after you drive 999,999 miles? It rolls back over to 000,000. It doesn't show 1,000,000. Integer overflow is similar; the number wraps around in an unexpected way, leading to bugs and incorrect results.

This is where our modular addition rule becomes essential. If we're adding two very large numbers and only care about the result modulo n, adding them directly might cause an overflow. But if we apply the modulo to each number before adding, we keep the intermediate values small and prevent overflow from ever happening.

#include <iostream>

int main() {
    // Let's use a large modulus
    int m = 1000000007; // A common prime modulus

    // Two large numbers close to the max int value
    int a = 2000000000;
    int b = 2000000000;

    // --- The WRONG Way (risks overflow) ---
    // This sum (4,000,000,000) is larger than max int.
    // The result will be incorrect due to overflow before the modulo.
    int result_wrong = (a + b) % m;
    std::cout << "Wrong result: " << result_wrong << std::endl;

    // --- The RIGHT Way (safe from overflow) ---
    // Apply the modular addition rule.
    // 1. Take the modulo of each number first.
    int a_mod = a % m; // a_mod is 999999993
    int b_mod = b % m; // b_mod is 999999993
    
    // 2. Add the smaller results.
    int sum_of_mods = a_mod + b_mod; // sum is 1999999986

    // 3. Take the final modulo.
    int result_correct = sum_of_mods % m; // Correct result is 999999979
    std::cout << "Correct result: " << result_correct << std::endl;

    return 0;
}

The first method fails because a + b overflows before the computer even gets to the % m part. The second method works perfectly because every number involved in the calculation stays safely within the int limit.

A Safe Addition Function

To make this process reusable, we can wrap the logic in a simple C++ function. This function will always give the correct modular sum without risking overflow.

// A function to safely add two integers under a modulus.
// We use 'long long' for the intermediate sum to be extra safe,
// as the sum of two remainders could still exceed the int limit.
long long modular_add(long long a, long long b, int m) {
    // Take modulo of each number to keep them small
    a = a % m;
    b = b % m;

    // Add them and take the final modulo
    return (a + b) % m;
}

int main() {
    int a = 2000000000;
    int b = 2000000000;
    int m = 1000000007;

    long long result = modular_add(a, b, m);
    std::cout << "Result from function: " << result << std::endl; // Prints 999999979
}

Using this function ensures your calculations are correct and robust, which is crucial in fields like competitive programming and cryptography where you often work with massive numbers.

Quiz Questions 1/4

Which of the following expressions correctly represents the modular addition rule?

Quiz Questions 2/4

In programming, what is the primary benefit of calculating ((a % m) + (b % m)) % m instead of (a + b) % m when a and b are very large numbers?

Mastering Modular Arithmetic for Beginners

Mastering Modular Arithmetic for Beginners

Modular Addition Rules

Adding in a Circle

Why This Matters for Computers

A Safe Addition Function