PrevNext
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 mm. We call this taking modulo mm. For example, if we take m=23m = 23, then instead of working with x=247x = 247, we use xmod23=17x \bmod 23 = 17. Usually, mm will be a large prime, given in the problem; the two most common values are 109+710^9 + 7 and 998244353=119223+1998\,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)modm=(amodm+bmodm)modm(a+b) \bmod m = (a \bmod m + b \bmod m) \bmod m
(ab)modm=(amodmbmodm)modm(a-b) \bmod m = (a \bmod m - b \bmod m) \bmod m
(ab)(modm)=((amodm)(bmodm))modm(a \cdot b) \pmod{m} = ((a \bmod m) \cdot (b \bmod m)) \bmod m
abmodm=(amodm)bmodma^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 xnmodmx ^ n \mod m. To do this, let's break down xnx ^ n into binary components. For example, 5105 ^ {10} = 5101025 ^ {1010_2} = 58525 ^ 8 \cdot 5 ^ 2. Then, if we know xyx ^ y for all yy which are powers of two (x1x ^ 1, x2x ^ 2, x4x ^ 4, \dots , x2log2nx ^ {2^{\lfloor{\log_2n} \rfloor}}, we can compute xnx ^ n in O(logn)\mathcal{O}(\log n).

To deal with mm, observe that modulo doesn't affect multiplications, so we can directly implement the above "binary exponentiation" algorithm while adding a line to take results (modm)\pmod m.

Solution - Exponentiation

Solution

Modular Inverse

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

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

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

For example, 10i5(mod109+7)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 aa not divisible by pp satisfy ap11(modp)a^{p - 1} \equiv 1 \pmod{p}. Consequently, ap2a1(modp)a^{p-2} \cdot a \equiv 1 \pmod{p}. Therefore, ap2a^{p - 2} is a modular inverse of aa modulo pp.

C++

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

Java

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

Because it takes O(logp)\mathcal{O}(\log p) time to compute a modular inverse modulo pp, 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:

int main() {
{
int a = 1e8, b = 1e8, c = 1e8;
cout << (ll)a*b%MOD*c%MOD << "\n"; // 49000000
}
{
mi a = 1e8, b = 1e8, c = 1e8;
// cout << a*b*c << "\n"; // doesn't work
// ^ not silently converted to int
cout << int(a*b*c) << "\n"; // 49000000
}
}

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

modular arithmetic

External Sol
CFEasy
Show Tags

modular arithmetic

Check CF

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Modular Arithmetic!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext