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.

### 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 $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 – try your best to solve 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 - 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++) {

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

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)  # 500000004assert 2 * x % MOD == 1

### With Euclidean Division

We can also find modular inverses through Euclidean Division. Given the prime modulus $m > a$ we have: $m = k \cdot a + r$, where k = $floor(\frac{m}{a})$ and $r = m \mod a$. Then: $0 = 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)$ in $\mathcal{O}(MOD)$.

C++

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

Java

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

Python

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

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.

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

### 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!