Not Frequent
0/3

# Modular Arithmetic

Authors: Darren Yao, Michael Cao, Andi Qu, Benjamin Qi, Andrew Wang

### Prerequisites

Working with remainders from division.

Resources
IUSACOvery brief, module is based off this
David Altizioplenty of examples from math contests
CPH
PAPS
CFsome practice probs

## 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 \bmod 23 = 17$. Usually, $m$ will be a large prime, given in the problem; the two most common values are $10^9 + 7$ and $998\,244\,353=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:

$(a+b) \bmod m = (a \bmod m + b \bmod m) \bmod m$$(a-b) \bmod m = (a \bmod m - b \bmod m) \bmod m$$(a \cdot b) \pmod{m} = ((a \bmod m) \cdot (b \bmod m)) \bmod m$$a^b \bmod {m} = (a \bmod m)^b \bmod m$

## Modular Exponentiation

Focus Problem – read through this problem before continuing!

### Resources

Resources
cp-algo

Binary exponentiation can be used to efficently compute $x ^ n \mod 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_2n} \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 $\pmod m$.

Solution

## 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$,

$(2x)\cdot i\equiv x\cdot (2i)\equiv x\pmod{10^9+7}.$

For example, $10i\equiv 5\pmod{10^9+7}$.

Resources
cp-algoVarious ways to take modular inverse, we'll only discuss the second here

### 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 \pmod{p}$. Consequently, $a^{p-2} \cdot a \equiv 1 \pmod{p}$. Therefore, $a^{p - 2}$ is a modular inverse of $a$ modulo $p$.

C++

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

Java

1public class main2{3   public static void main(String[] args) throws IOException4   {5    long m = (long)1e9+7;6    long x = binpow(2,m-2,m);7    System.out.println(x); // 5000000048    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.

Optional: Another Way to Compute Modular Inverses

We can also use the extended Euclidean algorithm. See the module in the Advanced section.

## Templates

Resources
Benq
Benqfeasible to type up during a contest

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"; // 490000005    }6    {7        mi a = 1e8, b = 1e8, c = 1e8;8        // cout << a*b*c << "\n"; // doesn't work9        // ^ not silently converted to int10        cout << int(a*b*c) << "\n"; // 49000000

## Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

modular arithmetic

View Solution
CFEasy
Show Tags

modular arithmetic

Check CF