No history yet

Modular Operations

Working with Congruence

You know that numbers can be congruent to each other modulo nn. This means they belong to the same residue class. The powerful consequence is that we can perform arithmetic operations on these numbers, and the results will also be congruent.

This isn't just a mathematical curiosity. It's the key to handling calculations with enormous numbers in programming without running out of memory or getting incorrect results.

The Rules of Modular Arithmetic

The properties of modular arithmetic for addition, subtraction, and multiplication are straightforward. They essentially say you can apply the modulus operator before or after the calculation, and the result will be the same. This is what allows us to keep intermediate results small.

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

Subtraction works the same way.

(a−b)(modn)=((a(modn))−(b(modn)))(modn)(a - b) \pmod n = ((a \pmod n) - (b \pmod n)) \pmod n

And so does multiplication.

(a⋅b)(modn)=((a(modn))⋅(b(modn)))(modn)(a \cdot b) \pmod n = ((a \pmod n) \cdot (b \pmod n)) \pmod n

Putting It into Practice

These properties are critical in competitive programming and other fields where you might deal with numbers that exceed the capacity of standard data types. In C++, even a long long can overflow if you're multiplying two large numbers. A long long can hold values up to roughly 9×10189 \times 10^{18}. If you multiply two numbers close to 10910^9, their product will be around 101810^{18}, which is fine. But multiplying two numbers like 101210^{12} would result in 102410^{24}, causing an overflow.

By taking the modulo at each step of a calculation, you ensure that the numbers involved never exceed the modulus, nn. This prevents overflow entirely, as long as nn itself fits within the data type.

The time complexity for modular addition, subtraction, and multiplication is O(1)O(1) for standard integer types. The operations themselves are constant time.

Let's look at how to implement these operations safely in C++. We'll assume a standard prime modulus, which is common in competitive programming.

#include <iostream>

// A common prime modulus used in competitive programming
const int MOD = 1e9 + 7; // This is 1,000,000,007

// Modular addition
long long add(long long a, long long b) {
    return (a + b) % MOD;
}

// Modular subtraction
long long sub(long long a, long long b) {
    // The (a - b) % MOD might be negative.
    // Adding MOD and taking the modulo again ensures a positive result.
    return ((a - b) % MOD + MOD) % MOD;
}

// Modular multiplication
long long mul(long long a, long long b) {
    // Take modulo of a and b first to prevent overflow during multiplication
    // if a or b are larger than MOD.
    return ((a % MOD) * (b % MOD)) % MOD;
}

The subtraction function includes an important trick. Since a % MOD in C++ can be negative if a is negative, a simple (a - b) % MOD could yield a negative result. For instance, (3−5)(mod7)(3 - 5) \pmod 7 should be −2(mod7)-2 \pmod 7, which is congruent to 55. The C++ expression (3 - 5) % 7 evaluates to -2. Adding MOD and taking the modulo again, (-2 + 7) % 7, correctly gives 5.

This ((a - b) % MOD + MOD) % MOD pattern is a robust way to handle modular subtraction and ensure the result is always in the range [0,MOD−1][0, \text{MOD}-1].

Quiz Questions 1/5

What is the primary reason for using modular arithmetic when performing a series of calculations with very large numbers in programming?

Quiz Questions 2/5

Given two integers, a = 15 and b = 4, and a modulus MOD = 7. Which of the following statements is true?

With these basic operations, you can now solve a wide range of problems involving large numbers without worrying about the limits of data types.