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 mabmodm=(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++

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}

Java

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

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

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

modular arithmetic

View Solution
CFEasy
Show Tags

modular arithmetic

Check CF

Module Progress:

Give Us Feedback on Modular Arithmetic!

PrevNext