Modular Arithmetic
Authors: Darren Yao, Michael Cao, Andi Qu, Benjamin Qi, Andrew Wang
Contributor: Kevin Sheng
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 . We call this taking modulo . For example, if we take , then instead of working with , we use . Usually, will be a large prime, given in the problem; the two most common values are and . 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:
Modular Exponentiation
Focus Problem – read through this problem before continuing!
Resources
Resources | ||||
---|---|---|---|---|
cp-algo |
Binary exponentiation can be used to efficently compute . To do this, let's break down into binary components. For example, = = . Then, if we know for all which are powers of two (, , , , , we can compute in .
To deal with , observe that modulo doesn't affect multiplications, so we can directly implement the above "binary exponentiation" algorithm while adding a line to take results .
Solution - Exponentiation
Solution
Modular Inverse
The modular inverse is the equivalent of the reciprocal in real-number arithmetic; to divide by , multiply by the modular inverse of . We'll only consider prime moduli here.
For example, the inverse of modulo is . This means that for any integer ,
For example, .
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 not divisible by satisfy . Consequently, . Therefore, is a modular inverse of modulo .
C++
const int MOD = 1e9 + 7;int main() {ll x = binpow(2, MOD - 2, MOD);cout << x << "\n"; // 500000004assert(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 = binpow(2, MOD - 2, MOD);System.out.println(x); // 500000004assert(2 * x % MOD == 1);}}
Python
MOD = 10 ** 9 + 7x = pow(2, MOD - 2, MOD);print(x) # 500000004assert(2 * x % MOD == 1);
Because it takes time to compute a modular inverse modulo , 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 BenQ's template, both of these do the same thing:
#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;
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | Show TagsModular Arithmetic | |||
CF | Easy | Show TagsModular Arithmetic | |||
CSES | Normal | Show TagsModular Arithmetic | |||
DMOJ | Hard | Show TagsModular Arithmetic |