Advanced Modular Arithmetic

1. Introduction

Modular arithmetic is the art of doing arithmetic with remainders. Instead of tracking a giant number, you track only what it leaves behind when divided by some modulus $m$. This is exactly the tool you need for the AMC/AIME staples: "what is the last digit of $7^{2026}$?", "what is the remainder when $3^{100}$ is divided by $7$?", or "find the smallest number leaving remainder $2$ mod $3$ and $3$ mod $5$." Each of these is hopeless by brute force but immediate once you think in residues.

The power of the subject comes from three landmark theorems. Fermat's Little Theorem and its generalization Euler's theorem let you shrink astronomical exponents down to size. The Chinese Remainder Theorem (CRT) lets you stitch together information from several coprime moduli into a single answer. Together with the basic rules that congruences respect addition and multiplication, these handle essentially every contest problem about powers, last digits, and systems of remainders.

This article develops the full machinery carefully: the definition and laws of congruence, modular inverses and when division is legal, Fermat and Euler with the totient function, order of an element, and CRT with a reliable solving procedure. Worked contest examples of rising difficulty show each tool in action.

2. Core Concepts

Concept 1 — Congruence and Its Definition

We write $a \equiv b \pmod{m}$ to mean $m \mid (a - b)$, i.e. $a$ and $b$ leave the same remainder upon division by $m$. Equivalently, $a = b + km$ for some integer $k$. The modulus $m$ is always a positive integer in contest problems.

Concept 2 — Laws of Congruence

Congruence behaves like equality under the operations that matter:

• If $a \equiv b$ and $c \equiv d \pmod m$, then $a + c \equiv b + d \pmod m$.
• Under the same hypotheses, $ac \equiv bd \pmod m$.
• Consequently $a^n \equiv b^n \pmod m$ for any positive integer $n$.

These laws let you replace any number by its residue before computing, keeping every intermediate value small.

Concept 3 — Residue Classes

The integers split into $m$ residue classes modulo $m$, represented by $0, 1, \dots, m-1$. Every integer is congruent to exactly one of these representatives. Working with residues is the whole point of modular arithmetic.

Concept 4 — Euler's Totient Function

Euler's totient $\varphi(m)$ counts how many integers from $1$ to $m$ are coprime to $m$. If $m = p_1^{e_1}\cdots p_k^{e_k}$, then $\varphi(m) = m\prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right).$ For a prime $p$, $\varphi(p) = p - 1$; for a prime power, $\varphi(p^e) = p^e - p^{e-1}$. The function is multiplicative: $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m,n) = 1$.

Concept 5 — Modular Inverses

When $\gcd(c, m) = 1$, the element $c$ has a modular inverse $c^{-1}$ with $c\cdot c^{-1} \equiv 1 \pmod m$. Division by $c$ modulo $m$ means multiplication by $c^{-1}$. Find inverses via the extended Euclidean algorithm, by testing, or via Fermat: $c^{-1} \equiv c^{p-2} \pmod p$ for prime $p$.

Concept 6 — When Cancellation Fails

You may cancel a factor $c$ from both sides of $ca \equiv cb \pmod m$ only if $\gcd(c, m) = 1$. If $\gcd(c,m) = g > 1$, cancellation is invalid and can produce wrong answers. The correct rule: $ca \equiv cb \pmod m \Rightarrow a \equiv b \pmod{m/g}$.

Concept 7 — Fermat's Little Theorem

Fermat's Little Theorem. If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p.$ Equivalently, for all integers $a$, $a^p \equiv a \pmod p$. Fermat collapses exponents modulo $p-1$ when $\gcd(a,p)=1$.

Concept 8 — Euler's Theorem

Euler's Theorem. If $\gcd(a, m) = 1$, then $a^{\varphi(m)} \equiv 1 \pmod m.$ Fermat is the special case $m = p$. Euler collapses exponents modulo $\varphi(m)$ when $\gcd(a,m)=1$.

Concept 9 — Order of an Element

The order of $a$ modulo $m$, written $\operatorname{ord}_m(a)$, is the smallest positive integer $d$ with $a^d \equiv 1 \pmod m$. The order always divides $\varphi(m)$ (and divides $p-1$ for prime $p$). Knowing the order gives the sharpest exponent reduction: $a^e \equiv a^{e \bmod d} \pmod m$.

Concept 10 — The Chinese Remainder Theorem

Chinese Remainder Theorem (CRT). If $m_1, \ldots, m_r$ are pairwise coprime, the system $x \equiv a_1 \pmod{m_1}, \quad \ldots, \quad x \equiv a_r \pmod{m_r}$ has a unique solution modulo $M = m_1 m_2 \cdots m_r$. CRT is the standard tool for last-digit problems (split mod $8$ and mod $125$ for mod $1000$) and for recombining prime-power information.

Concept 11 — Last Digits as Modular Problems

The units digit of $n$ is $n \bmod 10$. The last two digits are $n \bmod 100$. The last three digits are $n \bmod 1000$. For composite moduli like $100 = 4 \cdot 25$, solve mod each coprime factor and recombine with CRT.

Concept 12 — Splitting Composite Moduli

When $m = m_1 m_2$ with $\gcd(m_1, m_2) = 1$, solve a congruence modulo $m$ by solving it modulo $m_1$ and modulo $m_2$ separately, then recombining with CRT. This is often easier than working modulo $m$ directly, especially for $m = 35, 100, 1000$.