PrevNext
Not Frequent
 0/6

Modular Arithmetic

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

Contributors: Kevin Sheng, Mihnea Brebenel

Working with remainders from division.

Edit This Page

Prerequisites

Resources
AryanshS

introduces modular arithmetic through numerous math-contest-level examples and problems

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 – try your best to solve 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

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll exp(ll x, ll n, ll m) {
assert(n >= 0);
x %= m; // note: m * m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (n > 0) {

Java

import java.io.*;
import java.util.*;
public class Exponentation {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());

Python

We can use Python's builtin pow function to efficently compute modulo powers.

MOD = 10**9 + 7
for _ in range(int(input())):
first, second = [int(i) for i in input().split()]
print(pow(first, second, MOD))

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

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

Java

public class Main {
public static final int MOD = (int)Math.pow(10, 9) + 7;
public static void main(String[] args) throws IOException {
long x = exp(2, MOD - 2, MOD);
System.out.println(x); // 500000004
assert (2 * x % MOD == 1);
}
}

Python

MOD = 10**9 + 7
x = pow(2, MOD - 2, MOD)
print(x) # 500000004
assert 2 * x % MOD == 1

With Euclidean Division

We can also find modular inverses through Euclidean Division. Given the prime modulus m>am > a we have: m=ka+rm = k \cdot a + r, where k = floor(ma)floor(\frac{m}{a}) and r=mmodar = m \mod a. Then: 0=ka+rmodm    r=kamodm    ra1=kmodm    a1=kr1modm0 = k \cdot a + r \mod m \iff r = -k \cdot a \mod m \iff r \cdot a^{-1} = -k \mod m \iff a^{-1} = -k \cdot r^{-1} \mod m.

Here is a short recursive implementation of the above formula:

C++

int inv(int x) { return x <= 1 ? x : MOD - MOD / x * inv(MOD % x) % MOD; }

Java

static int inv(int x) {
	return x <= 1 ? x : MOD - MOD / x * inv(MOD % x) % MOD;
}

Python

def inv(x: int) -> int:
return x if x <= 1 else MOD - MOD // x * inv(MOD % x) % MOD

The advantage of this approach is that we can precompute the inverse modular of numbers in the range [1,MOD)[1, MOD) in O(MOD)\mathcal{O}(MOD).

C++

inv[1] = 1; // assume we already defined this array
for (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }

Java

inv[1] = 1; // assume we already defined this array
for (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }

Python

inv[1] = 1 # assume we already defined this array
for i in range(2, MOD):
inv[i] = MOD - MOD / i * inv[MOD % i] % MOD

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.

C++

Templates

Here are some templates that implement integer types that automatically wrap around when they exceed a certain modulus:

Resources
Benq
Benq

feasible to type up during a contest

AtCoder

contains a modint.hpp file

AtCoder

Here's an example using Benq's template:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
Code Snippet: ModInt (Click to expand)
int main() {
{
int a = 1e8, b = 1e8, c = 1e8;

And one using AtCoder's:

#include <bits/stdc++.h>
using namespace std;
// https://atcoder.github.io/ac-library/document_en/modint.html
// (included in atcoder grading)
#include <atcoder/modint>
using mint = atcoder::modint;
const int MOD = 1e9 + 7;

Java

Python

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsModular Arithmetic
CFEasy
Show TagsModular Arithmetic
KilonovaNormal
Show TagsMath, Prime Factorization
YSNormal
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