Modular Arithmetic Essentials for Contests

Why This Matters

Modular arithmetic is the working language of contest number theory. Almost every olympiad number-theory problem either is a modular-arithmetic problem or reduces to one in the first few steps. The basic claim:

Two integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b \pmod{n}$ , if $n \mid a - b$ . The relation partitions $\mathbb{Z}$ into $n$ equivalence classes, and arithmetic operations descend to those classes in a controlled way.

The technique-level question every contest writer must answer: which operations are sound modulo $n$ , and which are treacherous? Get this right and Fermat, Euler, Wilson, CRT, and quadratic residues are all natural extensions. Get it wrong and your "proof" silently violates the rules in step 3.

Recognize a modular argument when:

The problem asks about divisibility, remainders, or "last digits" of an integer expression.
The problem involves periodic or cyclic behavior of integer sequences (powers, Fibonacci, factorials).
The problem reduces to showing some integer expression is or is not a perfect square / cube / $k$ -th power.
The problem statement itself contains " $\bmod$ " or " $\equiv$ ".

This page covers the fundamentals every olympiad student must own cold: the equivalence relation, the four sound operations, the four unsound operations, modular inverses, and linear congruences. The remaining number-theory pages build on this base.

The Equivalence Relation

Theorem

Congruence Modulo n is an Equivalence Relation

Statement

Define $a \equiv b \pmod{n}$ iff $n \mid a - b$ . This is a reflexive, symmetric, and transitive relation on $\mathbb{Z}$ . The equivalence classes are exactly the $n$ sets $\{a + kn : k \in \mathbb{Z}\}$ for $a \in \{0, 1, \ldots, n - 1\}$ .

Intuition

"Same remainder when divided by $n$ " is the operational content. The equivalence classes (called residue classes $\bmod n$ ) form the quotient ring $\mathbb{Z} / n \mathbb{Z}$ , which has $n$ elements. Arithmetic operations on integers descend to operations on residue classes provided they respect the equivalence.

Proof Sketch

Reflexivity: $n \mid 0 = a - a$ , so $a \equiv a$ .

Symmetry: $n \mid a - b \Leftrightarrow n \mid -(a - b) = b

a $, so$ a \equiv b \Leftrightarrow b \equiv a$.

Transitivity: $n \mid a - b$ and $n \mid b - c$ give $n \mid (a - b) + (b - c) = a - c$ , so $a \equiv b$ and $b \equiv c$ give $a \equiv c$ .

Equivalence classes: by the division algorithm every integer $a$ can be written uniquely as $a = q n + r$ with $0 \le r < n$ . The class of $a$ is determined by $r$ . Hence the $n$ classes correspond to $r \in \{0, 1, \ldots, n - 1\}$ .

Why It Matters

The equivalence-relation framing is what makes " $\bmod n$ " behave like a number system: you can replace any integer by any other integer in the same class, and arithmetic still works. This freedom is the source of every clean modular-arithmetic argument.

Failure Mode

Equivalence is preserved by addition and multiplication; it is not automatically preserved by exponentiation in the exponent (changing the base mod $n$ is fine; changing the exponent mod $n$ generally is not). It is also not preserved by cancellation unless you have coprimality. Both are detailed below.

report a correction →

The Four Sound Operations

If $a \equiv a' \pmod{n}$ and $b \equiv b' \pmod{n}$ , then:

$a + b \equiv a' + b' \pmod{n}$
$a - b \equiv a' - b' \pmod{n}$
$a b \equiv a' b' \pmod{n}$
$a^k \equiv (a')^k \pmod{n}$ for any non-negative integer $k$ (operation 3 iterated)

These four operations descend cleanly because the relation is defined by an additive subgroup ( $n \mathbb{Z}$ ) that is also closed under multiplication.

You can substitute any representative of a residue class for any other when computing sums, differences, products, and powers. This is the freedom that makes modular arithmetic practical: $123456789 \pmod 7$ becomes $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 \equiv ? \pmod 7$ via "replace each digit position by its weight $\bmod 7$ ".

The Four Unsound Operations

These do not descend to residue classes, or descend only under additional hypotheses.

Division by $b$ . $a \equiv b \pmod n$ and $c \mid a, c \mid b$ does not imply $a/c \equiv b/c \pmod n$ . Example: $10 \equiv 4 \pmod 6$ but $10/2 = 5 \not\equiv 2 = 4/2 \pmod 6$ . Division is only sound when $\gcd(c, n) = 1$ (in which case it is multiplication by $c^{-1}$ , see below).

Cancellation. $a c \equiv b c \pmod n$ does not imply $a \equiv b \pmod n$ unless $\gcd(c, n) = 1$ . Example: $2 \cdot 3 \equiv 0 \cdot 3 \pmod 6$ but $2 \not\equiv 0 \pmod 6$ .

Exponentiation in the exponent. $k \equiv k' \pmod n$ does not imply $a^k \equiv a^{k'} \pmod n$ in general. To reduce the exponent you need a separate condition: by Fermat or Euler, the exponent reduces $\bmod \, \varphi(n)$ when $\gcd(a, n) = 1$ .

Mixed moduli. $a \equiv b \pmod n$ and $a \equiv b \pmod m$ do not in general combine to a useful relation $\pmod{nm}$ unless $\gcd(n, m) = 1$ , in which case CRT applies.

These four unsound operations are the single largest source of errors in olympiad number-theory writeups. Beginners apply them by reflex from ordinary arithmetic and produce statements that look right but are not.

Modular Inverses

Theorem

Existence of Modular Inverses

Statement

$a$ has a multiplicative inverse modulo $n$ , i.e., there exists $b$ with $a b \equiv 1 \pmod n$ , if and only if $\gcd(a, n) = 1$ .

Intuition

Bezout's identity: $\gcd(a, n) = 1$ iff there exist integers $b, k$ with $a b + n k = 1$ , i.e., $a b \equiv 1 \pmod n$ .

When the inverse exists it is unique modulo $n$ , and "division by $a$ " modulo $n$ is well-defined as multiplication by the inverse. When $\gcd(a, n) > 1$ , division is genuinely not well-defined; you cannot work around this.

Proof Sketch

( $\Leftarrow$ ) If $\gcd(a, n) = 1$ , Bezout gives $a b + n k = 1$ for some integers $b, k$ . Then $a b \equiv 1 \pmod n$ , so $b$ is the inverse.

( $\Rightarrow$ ) If $a b \equiv 1 \pmod n$ for some $b$ , then $a b - 1 = k n$ for some $k$ , so $a b - k n = 1$ . Any common divisor of $a$ and $n$ divides $a b - k n = 1$ , hence is 1. So $\gcd(a, n) = 1$ .

Why It Matters

Modular inverses turn $(\mathbb{Z}/n\mathbb{Z})^*$ — the set of residue classes coprime to $n$ — into an abelian group under multiplication. This group has order $\varphi(n)$ (Euler's totient), and Lagrange's theorem on it gives Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod n$ .

Inverses are computed via the extended Euclidean algorithm, which runs in $O(\log n)$ steps. They are also computed via Fermat's little theorem when $n$ is prime: $a^{-1} \equiv a^{p-2} \pmod p$ .

Failure Mode

$2$ has no inverse modulo $4$ , because $\gcd(2, 4) = 2$ . Any " $2 b \equiv 1 \pmod 4$ " attempt is doomed. In particular, problems that involve $\frac{1}{2}$ in modular arithmetic modulo an even number are ill-defined; rephrase to avoid the inverse before applying any technique.

report a correction →

Worked Example: A Linear Congruence

Example

Solve $7x \equiv 3 \pmod{15}$

Problem. Find all integer solutions to $7 x \equiv 3 \pmod {15}$ .

Solution. $\gcd(7, 15) = 1$ so $7$ has an inverse mod 15. Find it via the extended Euclidean algorithm: $15 = 2 \cdot 7

1 $, so$ 1 = 15 - 2 \cdot 7 $, giving$ 7 \cdot (-2) \equiv 1 \pmod $, i.e.,$ 7^ \equiv -2 \equiv 13 \pmod$.

Multiply both sides of $7 x \equiv 3$ by $13$ : $x \equiv 13 \cdot 3 = 39 \equiv 9 \pmod{15}$ .

So the solutions are $x \in \{9, 24, 39, \ldots, -6, -21, \ldots\}$ , i.e., $x \equiv 9 \pmod{15}$ .

Verification: $7 \cdot 9 = 63 = 4 \cdot 15 + 3 \equiv 3 \pmod {15}$ . ✓

Worked Example: Last Two Digits of a Power

Example

Last two digits of $3^{100}$

Problem. Compute the last two digits of $3^{100}$ .

Solution. "Last two digits" means $3^{100} \pmod{100}$ .

By the Chinese Remainder Theorem (since $100 = 4 \cdot 25$ with $\gcd(4, 25) = 1$ ), it suffices to compute $3^{100} \pmod 4$ and $3^{100} \pmod{25}$ then combine.

$3^{100} \pmod 4$ : $3 \equiv -1 \pmod 4$ , so $3^{100} \equiv (-1)^{100} = 1 \pmod 4$ .

$3^{100} \pmod{25}$ : $\gcd(3, 25) = 1$ and $\varphi(25) = 20$ , so by Euler's theorem $3^{20} \equiv 1 \pmod {25}$ . Hence $3^{100} = (3^{20})^5 \equiv 1 \pmod{25}$ .

So $3^{100} \equiv 1 \pmod 4$ and $\equiv 1 \pmod{25}$ . By CRT, $3^{100} \equiv 1 \pmod{100}$ , i.e., the last two digits are 01.

This is the canonical " $\bmod n$ as a primary tool" technique: factor $n$ , compute mod each factor (using Euler or Fermat to reduce exponents), recombine with CRT.

Common Mistakes

Watch Out

Dividing in modular arithmetic without coprimality

" $8 \equiv 0 \pmod 4$ , so dividing by 4 gives $2 \equiv 0 \pmod 4$ " is wrong. Division by $a$ modulo $n$ is only well-defined when $\gcd(a, n) = 1$ . Without coprimality, "divide by $a$ " must be replaced by "factor $a$ from both sides and reduce the modulus" (so $a x \equiv a y \pmod{ka}$ becomes $x \equiv y \pmod k$ ).

Watch Out

Reducing the exponent without justification

$2^{100} \pmod 7$ is not computed by reducing the 100 mod 7. Reducing exponents requires either Fermat (modulus prime and base coprime) or Euler (general modulus, base coprime to modulus). The base reduces modulo $n$ ; the exponent reduces modulo $\varphi(n)$ (when applicable).

Watch Out

Confusing mod with divisibility

" $a \equiv 0 \pmod n$ " means $n \mid a$ . Beginners sometimes treat " $\bmod n$ " as a function returning the remainder (the programmer's view) rather than as a relation between integers (the mathematician's view). Both are valid notations; the relation form is more flexible for proof writing.

Watch Out

Mixing moduli without CRT

" $a \equiv 1 \pmod 2$ and $a \equiv 2 \pmod 3$ so $a \equiv ? \pmod 6$ " is solved by CRT (specifically $a \equiv 5 \pmod 6$ ), not by averaging or combining the residues directly. $\gcd(2, 3) = 1$ is what makes CRT work.

Watch Out

Applying mod after the fact

If you compute a giant integer expression "honestly" and only then take mod, you have done none of the simplification work. Apply mod to each step: replace $123 \cdot 456 \pmod{7}$ by $(123 \bmod 7) \cdot (456 \bmod 7) = 4 \cdot 1 = 4 \pmod 7$ . Modular arithmetic is most powerful when you apply it as you go.

Exercises

ExerciseCore

Problem

Find $7^{222} \pmod{11}$ .

ExerciseCore

Problem

Find all $x$ with $0 \le x < 30$ satisfying $4 x \equiv 6 \pmod{10}$ .

ExerciseAdvanced

Problem

Show that for all positive integers $n$ , $n^7 - n$ is divisible by 42.

Cross-Network Links

ProofsPath: fermats-little-theorem-applications is the prime-modulus exponent-reduction tool; eulers-theorem-applications generalizes Fermat to composite moduli; chinese-remainder-theorem-applications combines multiple moduli; quadratic-residues-and-legendre-symbol is the structured study of squares mod $p$ .
TheoremPath: game-theory uses modular arithmetic in finite-strategy game analysis; the Nim-sum is a $\mathbb{Z}/2\mathbb{Z}$ vector-space computation.
ComputationPath: modular exponentiation by repeated squaring is the practical algorithm for the operations on this page; cryptographic primitives (RSA, Diffie-Hellman, ECC) all live here.

References

See structured references block. Primary entry points: Hardy-Wright Ch 5-6 for the canonical analytic treatment; Burton Elementary Number Theory Ch 4-5 for a textbook-style treatment with worked examples; Engel Problem-Solving Strategies Ch 6 for olympiad-flavored applications; Chen's online text Modern Olympiad Number Theory for the contest synthesis. Gauss's Disquisitiones Arithmeticae (1801) is the foundational primary source.