PrevNext
Not Frequent
 0/4

Modular Arithmetic

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

Prerequisites

Working with remainders from division.

Resources
IUSACO

very brief, module is based off this

David Altizio

plenty of examples from math contests

CPH
PAPS
CF

some practice probs

MONT

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-algo

Various 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
Benq

feasible 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 NameDifficultyTags
CSESEasy
Show TagsModular Arithmetic
CFEasy
Show TagsModular Arithmetic
CSESNormal
Show TagsModular Arithmetic

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!

PrevNext