Modular arithmetic

Modular arithmetic computes the remainder of a sum, a difference, a product or a power after dividing by some number m, without ever computing the huge number itself. You need it whenever a problem says "print the answer modulo $1 0^{9} + 7$ 10^9 + 7". If the problem needs all the digits of the huge number, use big integers instead.

Explanation

The last digit of 23 · 49 doesn't need the whole product. The last digits of the two numbers are 3 and 9, and 3 · 9 = 27 ends in 7. The whole product, 23 · 49 = 1127, ends in 7 too. Sums work the same way: 23 + 49 = 72 and 3 + 9 = 12 both end in 2.

Two small tables. Left: 23 times 49 is 1127, and 3 times 9 is 27. Right: 23 plus 49 is 72, and 3 plus 9 is 12. The last digits 3 and 9 of the numbers, the 7 ending 1127 and 27, and the 2 ending 72 and 12 are in green.

Fig. 1. The last digit of a product or a sum depends only on the last digits of the numbers.

Contest problems ask the same question about numbers too big for long long. Take five six-digit numbers: 123456, 789012, 345678, 901234 and 567890. What are the last three digits of their product? The answer has three digits, but the product has 29. The largest standard integer type in C++, long long, holds numbers up to about $9.2 \cdot 1 0^{18}$ 9.2 \cdot 10^{18}, that is, 19 digits.

The first program most people write multiplies all five numbers in long long and takes the last three digits at the end. The fourth multiplication already gives a number with 23 digits, more than long long can hold. From there on the program works with a wrong number, and at the end it prints a wrong answer, sometimes even a negative one.

Five bars show the number of digits of the running product 123456 × 789012 × 345678 × 901234 × 567890: 6, 11, 17, 23 and 29; a dashed line at 19 digits marks the limit of long long, and the last two bars, 23 and 29, are red because they cross it.

Fig. 2. Multiplying first and taking the last digits at the end: the fourth product has 23 digits, more than long long can hold.

So the question is whether the program needs the whole product at all. It doesn't: by the tiny example, the last three digits of a product depend only on the last three digits of the two numbers. So after every multiplication the program keeps only the last three digits, and of each new number it also uses only the last three digits. Every number it touches stays below 1000 · 1000, and the result is 160. The exact product, 17233335359777734620784220160, does end in 160.

The last three digits of a number are its remainder after dividing by 1000. The rule holds for any divisor, not only for 1000: the remainder of a sum or a product depends only on the remainders of the numbers. Check it with 9: 23 leaves 5 and 49 leaves 4, so 23 · 49 should leave the same remainder as 5 · 4 = 20, which is 2. It does: 1127 = 9 · 125 + 2.

Working with remainders like this is called modular arithmetic. The divisor is the modulus, "a modulo m", written a mod m, is the remainder after dividing a by m, and taking that remainder is called reducing modulo m.

Five six-digit numbers in a row with their remainders modulo 1000 appearing under them one by one; below, the kept remainder starts at 1 and is multiplied by each remainder in turn, the product reduced to its last three digits, ending at 160.

Start: the number kept is 1.

1/12

Fig. 3. Step through the computation with the buttons or the arrow keys. Blue is what changed, green is the remainder that is kept.

However many numbers come, every kept number stays below 1000 and every product below 1000 · 1000. With the modulus $1 0^{9} + 7$ 10^9 + 7, the products stay below about $1 0^{18}$ 10^{18}, which fits in long long.

Subtraction and negative remainders

Subtraction follows the rule too, but the result can be negative. Let's count the six-digit numbers that contain at least one digit 7, modulo 1000. It is easier to count all six-digit numbers, 900000, and subtract those without a 7. A number without a 7 has 8 choices for the first digit (1 to 9 except 7) and 9 for each of the other five, so there are 8 · 59049 = 472392 of them. The answer is 900000 − 472392 = 427608.

With remainders, 900000 leaves 0 and 472392 leaves 392, and 0 − 392 = −392. A remainder can't be negative, but adding the modulus once doesn't change the remainder and fixes the sign: −392 + 1000 = 608, and 427608 does end in 608. In C++ this matters, because % keeps the sign of the left number: (0 - 392) % 1000 is −392. So for two remainders a and b, write (a - b + m) % m.

Powers

A power is repeated multiplication, so the same loop computes it. Take the last three digits of $2^{20}$ 2^{20}: start with 1 and multiply by 2 twenty times, keeping the last three digits. The first nine steps give 2, 4, 8, …, 512, and the tenth gives 1024, so the program keeps 24. The next ten give 48, 96, 192, 384, 768, 536, 72, 144, 288 and 576, and $2^{20}$ 2^{20} = 1048576 does end in 576. A loop of $n$ multiplications is fine for $n$ up to about $1 0^{8}$ 10^8, a rule of thumb for what runs in a second. For $n$ up to $1 0^{18}$ 10^{18}, use binary exponentiation: it takes the remainder after every multiplication in the same way but needs only about $2 lo g_{2} n$ 2 \log_2 n of them.

Why problems use 1000000007

Most problems ask for the answer modulo $1 0^{9} + 7$ 10^9 + 7 = 1000000007.

Every remainder is below $1 0^{9} + 7$ 10^9 + 7, so it fits in int.
The sum of two remainders is at most 2000000012, below the int limit 2147483647.
The product of two remainders is below about $1 0^{18}$ 10^{18}, which fits in long long (up to about $9.2 \cdot 1 0^{18}$ 9.2 \cdot 10^{18}).
It is a prime number, which makes division possible with the modular inverse.
It is large, so a wrong answer only rarely has the same remainder as the right one, and the checker catches almost every mistake.

The other common modulus is 998244353, also a prime below $1 0^{9}$ 10^9.

Implementation

The program reads n numbers into an array and prints their product and their sum modulo m. The number kept is res, the new number is x, and the modulus is m. At the start res = 1 and sum = 0, and each number goes through two steps:

Reduce the input: x = (x % m + m) % m, the remainder of the new number.
Multiply, reduce the product: res = res * x % m. For the sum the step is "add, reduce the sum": sum = (sum + x) % m.

After the last number, res and sum are the answers.

All values are long long, even when m and the remainders fit in int, because res * x can reach m · m. If you keep remainders in int, write the product as 1LL * a * b % m: the 1LL is a long long 1, so the multiplication is done in long long.

The input is n and m, then n numbers, each fitting in long long. For the five numbers above:

5 1000
123456 789012 345678 901234 567890

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long res = 1;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        // reduce the input
        long long x = (a[i] % m + m) % m;   // + m only matters for negative input

        // multiply, reduce the product
        res = res * x % m;

        // add, reduce the sum
        sum = (sum + x) % m;
    }

    cout << res << '\n';
    cout << sum << '\n';
}

The program does a constant number of operations per number, so it takes $O (n)$ time. It stores the array, $O (n)$ memory; reading each number inside the loop would need only $O (1)$ .

Correctness proof

The claim is that the remainder of a sum or a product depends only on the remainders of the numbers.

Look first at the last digit of 23 · 49. Split 23 into 20 + 3 and 49 into 40 + 9. The product is the area of a rectangle 49 wide and 23 high, and the splits cut it into four blocks: 40 · 20, 9 · 20, 40 · 3 and 9 · 3. Each of the first three blocks has a factor 40 or 20, so it is a multiple of 10 and adds nothing to the last digit. Only the block 9 · 3 = 27 is left, and its last digit, 7, is the last digit of the product.

A rectangle 49 wide and 23 high, cut into 40 and 9 across and 20 and 3 down, giving four blocks: 40 · 20, 9 · 20 and 40 · 3 in grey, and 9 · 3 = 27 in green in the bottom right corner.

Fig. 4. Every block except 9 · 3 has a factor 40 or 20, so it is a multiple of 10 and doesn't change the last digit.

The same split works for any modulus $m$ . Write $a = q_{a} m + r_{a}$ a = q_a m + r_a and $b = q_{b} m + r_{b}$ b = q_b m + r_b, where $r_{a}$ r_a and $r_{b}$ r_b are the remainders. Then

a \cdot b = q_{a} q_{b} m^{2} + q_{a} m r_{b} + q_{b} m r_{a} + r_{a} r_{b} .

a \cdot b = q_a q_b m^2 + q_a m r_b + q_b m r_a + r_a r_b.

The first three terms are multiples of $m$ , so $a \cdot b$ a \cdot b has the same remainder as $r_{a} r_{b}$ r_a r_b. For the sum, $a + b = (q_{a} + q_{b}) m + r_{a} + r_{b}$ a + b = (q_a + q_b) m + r_a + r_b, which has the same remainder as $r_{a} + r_{b}$ r_a + r_b. A difference works the same way, $a - b = (q_{a} - q_{b}) m + r_{a} - r_{b}$ a - b = (q_a - q_b) m + r_a - r_b, except that $r_{a} - r_{b}$ r_a - r_b can be negative, and adding $m$ makes it a remainder again.

Division has no such split. Modulo 7, 24 leaves 3 and 6 leaves 6, but 24 / 6 = 4 can't be built from 3 and 6: 3 / 6 isn't even a whole number. The multiples of $m$ drop out of a sum or a product because each of them stays a multiple of $m$ , and nothing like that holds for a quotient.

The program applies the rule once per number. Before each step, res is the remainder of the product of the numbers so far. The step multiplies it by the remainder of the next number and reduces the result, which by the rule gives the remainder of the product of all numbers so far. After the last number, res is the remainder of the whole product.

Common mistakes

Taking the remainder only at the end. The product overflows long before the end, as with the five six-digit numbers above. Reduce after every operation.
Multiplying two int remainders. With m = $1 0^{9} + 7$ 10^9 + 7 and a = b = 1000000000, a * b % m overflows, while the right answer is 49. Use long long or 1LL * a * b % m.
Leaving a negative remainder after a subtraction. A range sum from prefix sums modulo 1000 with pre[r] = 5 and pre[l] = 990 gives (5 - 990) % 1000 = −985 instead of 15. Write (a - b + m) % m, and (x % m + m) % m for input that can be negative.
Dividing remainders. Modulo 7, 24 / 6 = 4 but the remainders give 3 / 6 = 0, as the proof shows. When m is prime, multiply by the modular inverse instead, or find a way that uses only sums and products, such as Pascal's triangle for binomial coefficients.
Comparing remainders as if they were the numbers. Modulo $1 0^{9} + 7$ 10^9 + 7, the value $1 0^{9} + 8$ 10^9 + 8 leaves 1 and the value 5 leaves 5, so the larger value looks smaller. Compare the real values and reduce only what you print.

Similar algorithms

Binary exponentiation computes a power with an exponent up to $1 0^{18}$ 10^{18} by squaring.

The modular inverse replaces division by $b$ modulo a prime with multiplication by $b^{m - 2}$ b^{m-2} mod $m$ . Binomial coefficients modulo $1 0^{9} + 7$ 10^9 + 7 need it.