Not Frequent

Modular Arithmetic

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

Working with remainders from division.

Edit This Page



very brief, module is based off this

David Altizio

plenty of examples from math contests


some practice probs



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!



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


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}.


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.


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


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


MOD = 10 ** 9 + 7
x = pow(2, MOD - 2, MOD);
print(x) # 500000004
assert(2 * x % MOD == 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.



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;


StatusSourceProblem NameDifficultyTags
Show TagsModular Arithmetic
Show TagsModular Arithmetic
Show TagsModular Arithmetic
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!