What is it?

Modular Arithmetic encompasses all sorts of theorems and optimizations surrounding the % operator in C and Python.

As you’ll see in the related problems, modulo arithmetic is often tied together in a question regarding counting things (combinatorics) or probabilities.

For those who haven’t come up across it before, % is an operation normally performed on two integers \(a\) and \(b\), and \(a\ \%\ b\) can be intuitively though of as the remainder when you divide \(a\) by \(b\).

For positive integers, this gives us the relation

Where \(//\) denotes floor division.

C++ vs Python

The % operator actually does slightly different things in Python and C++. In particular, when the left hand side is a negative number, while Python will always return a positive number, C++ will always return a negative number!

1

print(-4 % 3)

1
2
3

int main() {
  cout << (-4 % 3) << endl;
}

The Python code will output 2, while the C++ code will output -1.

Characteristics

While % at first might not seem to have much use, it does have some very interesting characteristics.

For most of this we’ll be assuming that both numbers are positive, just because most contest problems do and its easier to wrap your head around.

Addition, Subtraction, Multiplication

The % operator can have its ordered swapped with any of the above operations. In particular:

Multiples

\(a\ \%\ b = 0\) iff \(b\) is a factor of \(a\).

Inverse

For some particular \(a\) and \(b\), with \(b\) prime, let \(a^{-1}\) denote the modular inverse of \(a\). The modular inverse of \(a\) is the only number between \(1\) and \(b-1\) such that \(a*a^{-1}\ \%\ b = 1\).

As long as \(b\) is prime (or at least \(a, b\) are coprime), this inverse will always exist and there will always only be one of them.

We’ll come back to inverses later because they pop up in a few questions, often regarding probabilities.

Fermat’s Little Theorem

For prime \(p\), we know the following is true for any \(a\):

In particular, we also have

so \(a^{p-2}\) is \(a^{-1}\).

Computing things

Exponentials

The most common application of modular arithmetic is simply because the expected output would normally be way too large to store in a long long or something similar, and so the question asks to output the answer modulo (%) 100000007 or some other number (This one happens to be prime).

To compute \(a^b\ \%\ m\), you might think this requires us to do \(O(b)\) calculation, but in fact we can do it in \(O(\log(B))\).

1
2
3
4
5
6
7
8
9

def expmod(a, b, m):
  res = 1 % m
  a %= m
  while b:
    if (b & 1):
      res = (res * a) % m
    a = (a*a) % m
    b //= 2
  return res

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef __int128 big;

big expmod(big a, big b, big m) {
  big res=1%m;
  a %= m;
  for (; b; b /= 2) {
    if (b&1) {
      res=(res*a)%m;
    }
    a=(a*a)%m;
  }
  return res;
}

This is just a modification to the normal integer exponent algorithm, utilising the fact that we can decompose

The binary decomposition of \(b\).

Modular Inverse

1
2
3
4
5
6
7

# works for any a, m coprime
def inv(a, m):
  _, x, y = gcd(m, a)
  return y % m
# works for m prime
def inv(a, m):
  return expmod(a, m-2, m)

1
2
3
4
5
6
7
8
9
10
11

// works for any a, m coprime
ll inv(ll a, ll m) {
  ll x, y;
  gcd(m, a, x, y);
  // Ensure outcome is positive. CPP exclusive.
  return ((y % m) + m) % m;
}
// works for m prime
ll inv(ll a, ll m) {
  return expmod(a, m-2, m);
}

Here gcd is the function that takes two numbers \(a\) and \(b\), and returns:

• The greatest common factor of \(a\) and \(b\)
• Two numbers \(x\) and \(y\) such that \(ax + by = \text{gcd}(a, b)\).

This works because \(ya = \text{gcd}(m, a) - xm\). But, for \(m\) prime, we have \(\text{gcd}(m, a) = 1\):

And so \(y\ \%\ m\) has to be the multiplicative inverse of \(a\).

Fractions and Modular inverses

The final, and often most crucial trick goes as follows:

A common contest problem ends with the following statement:

The output can be expressed as an irreducible fraction \(\frac{p}{q}\). Output \(pq^{-1}\) modulo 100000007.

While this can seem daunting, \(pq^{-1}\) has some nice properties. Let’s see them:

Properties

Addition

Consider two fractions \(\frac{a}{b}\) and \(\frac{c}{d}\). We have:

and (modulo \(m\)):

Multiplication

Consider two fractions \(\frac{a}{b}\) and \(\frac{c}{d}\). We have:

and (modulo \(m\)):

Factorisation

Consider for the last time a single reducible fraction \(\frac{ka}{kb}\). We have:

Wrap up

So, given the above, rather than having to store \(\frac{a}{b}\) for ludicrously sized \(a\) and \(b\), we can instead compute \(ab^{-1}\) and do arithmetic with these values.

As an example, if we wanted to compute \(\frac{p}{q} = (\frac{a}{b} + \frac{c}{d}) \times \frac{e}{f}\), then we could instead output

How cool is that!