Modular Arithmetic

Introduction

In modular arithmetic, instead of working with integers themselves, we work with their remainders when divided by $m$. We call this taking modulo $m$. For example, if we take $m=23$, then instead of working with $x=247$, we use $x\mathrm{m}\mathrm{o}\mathrm{d}23=17$. Usually, $m$ will be a large prime, given in the problem; the two most common values are $10^9+7$ and $998244353=119\cdot 2^{23}+1$. Modular arithmetic is used to avoid dealing with numbers that overflow built-in data types, because we can take remainders, according to the following formulas:

Modular Exponentiation

Resources

Binary exponentiation can be used to efficently compute $x^n\mathrm{m}\mathrm{o}\mathrm{d}m$. To do this, let's break down $x^n$ into binary components. For example, $5^{10}$ = $5^{1010_2}$ = $5^8\cdot 5^2$. Then, if we know $x^y$ for all $y$ which are powers of two ($x^1$, $x^2$, $x^4$, $\dots$ , $x^{2^{\lfloor {\log }_{2}n\rfloor }}$, we can compute $x^n$ in $\mathcal{O}(\log n)$.

To deal with $m$, observe that modulo doesn't affect multiplications, so we can directly implement the above "binary exponentiation" algorithm while adding a line to take results $(\mathrm{m}\mathrm{o}\mathrm{d}m)$.

Solution - Exponentiation

Modular Inverse

The modular inverse is the equivalent of the reciprocal in real-number arithmetic; to divide $a$ by $b$, multiply $a$ by the modular inverse of $b$. We'll only consider prime moduli $p$ here.

For example, the inverse of $2$ modulo $p=10^9+7$ is $i=\frac{p+1}{2}=5\cdot 10^8+4$. This means that for any integer $x$,

For example, $10i\equiv 5(\mathrm{m}\mathrm{o}\mathrm{d}10^9+7)$.

With Exponentiation

Fermat's Little Theorem (not to be confused with Fermat's Last Theorem) states that all integers $a$ not divisible by $p$ satisfy $a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Consequently, $a^{p-2}\cdot a\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Therefore, $a^{p-2}$ is a modular inverse of $a$ modulo $p$.

1int main() {
2    ll m = 1e9+7;
3    ll x = binpow(2,m-2,m);
4    cout << x << "\n"; // 500000004
5    assert(2*x%m == 1);
6}

1public class main
2{
3   public static void main(String[] args) throws IOException
4   {
5    long m = (long)1e9+7;
6    long x = binpow(2,m-2,m);
7    System.out.println(x); // 500000004
8    assert(2*x%m == 1);
9   }
10}

Because it takes $\mathcal{O}(\log p)$ time to compute a modular inverse modulo $p$, frequent use of division inside a loop can significantly increase the running time of a program. If the modular inverse of the same number(s) is/are being used many times, it is a good idea to precalculate it.

Also, one must always ensure that they do not attempt to divide by 0. Be aware that after applying modulo, a nonzero number can become zero, so be very careful when dividing by non-constant values.

Templates

Using my template, both of these do the same thing:

1int main() {
2    {
3        int a = 1e8, b = 1e8, c = 1e8;
4        cout << (ll)a*b%MOD*c%MOD << "\n"; // 49000000
5    }
6    {
7        mi a = 1e8, b = 1e8, c = 1e8;
8        // cout << a*b*c << "\n"; // doesn't work
9        // ^ not silently converted to int
10        cout << int(a*b*c) << "\n"; // 49000000

Problems