Modular Arithmetic

What you need to know

• What "mod" means. $a \equiv b \pmod m$ means $a$ and $b$ leave the same remainder when divided by $m$; in other words, $m$ divides $a-b$. Example: $17 \equiv 2 \pmod 5$, since $5$ divides $15$.
• Working with remainders. You can add, subtract, and multiply congruences, swapping any number for its remainder. You may divide both sides by $c$ only when $c$ shares no factor with $m$. Example: $17\cdot23 \equiv 2\cdot3 = 6 \equiv 1 \pmod 5$. But $6 \equiv 16 \pmod{10}$ while $3 \not\equiv 8 \pmod{10}$: dividing by $2$ failed.
• Units digits cycle. The units digits of $a, a^2, a^3, \dots$ repeat with a cycle length that divides $4$. Example: powers of $2$ end in $2, 4, 8, 6, \dots$; since $2026 = 4\cdot506+2$, $2^{2026}$ ends in $4$.
• Any modulus. The remainders of $a^n$ mod $m$ always start repeating at some point, so once inside the cycle, reduce the exponent by the cycle length. A few powers may come before the cycle starts. Example: mod $12$, powers of $2$ go $2, 4, 8, 4, 8, \dots$; the cycle starts at $2^2$.
• Fermat's Little Theorem. If $p$ is prime and does not divide $a$, then $a^{p-1} \equiv 1 \pmod p$.
• Squares. A square leaves remainder $0$ or $1$ when divided by $3$ or by $4$. Divided by $8$, a square leaves $0$, $1$, or $4$, and an odd square always leaves $1$. Example: $49 = 8\cdot6+1$ and $36 = 8\cdot4+4$.
• Chinese Remainder Theorem. If $\gcd(m,n) = 1$, a number's remainders mod $m$ and mod $n$ pin down its remainder mod $mn$. Example: remainder $2$ mod $3$ and $3$ mod $5$ means remainder $8$ mod $15$.
• Digit shortcuts. A number and its digit sum agree mod $9$. Mod $11$, use the alternating digit sum, starting with $+$ on the units digit. Mod $100$, keep the last two digits. Example: $2026$ leaves $1$ mod $9$ (digit sum $10$), $2$ mod $11$ ($6-2+0-2$), and $26$ mod $100$.

How AMC 10 tests it

• "What is the units digit (or remainder mod $7$) of $3^{2026}+\ldots$?" Find the cycle and reduce the exponent (problems 8–15).
• Day-of-week or clock problems: count days, reduce mod $7$ or $12$, watch leap years.
• "Find the smallest $n$ with $n \equiv 2 \pmod 3$, $n \equiv 3 \pmod 5$, $n \equiv 1 \pmod 7$": the Chinese Remainder Theorem, by listing or stepping through multiples (problems 12–20).
• Showing an equation has no solutions by working mod $3$, $4$, $8$, or $9$.
• Divisibility in disguise, such as "the average was a whole number after each entry," which means the first $k$ entries add up to a multiple of $k$.

Standard approaches

1. Reduce the base first, find the cycle length of its powers, and reduce the exponent by that length (never by $m$).
2. In sums of factorials or products, every term past some point is $\equiv 0$, so only the first few matter. Example: from $5!$ on, factorials end in $0$, so $1!+2!+\dots+100!$ ends in the same digit as $1+2+6+24 = 33$.
3. For several congruences, start with the largest modulus and step through its numbers until the others hold. Example: above, $n \equiv 1 \pmod 7$ gives $1, 8, \dots$, and $8$ already works.
4. For "no integer solutions," use a modulus where squares or cubes have few remainders. Example: $x^2+y^2$ leaves $0$, $1$, or $2$ mod $4$, so it never equals $2027$.
5. Use negative remainders to make powers easy: $10 \equiv -1 \pmod{11}$, so $10^{2026} \equiv 1 \pmod{11}$.

Worked example

What is the remainder when $3^{2026} + 2026$ is divided by $7$?

(A) $0$ (B) $1$ (C) $3$ (D) $4$ (E) $6$

Step 1: the cycle. Multiply by $3$ and keep the remainder mod $7$ each time: $3^1 \equiv 3$, $3^2 \equiv 2$, $3^3 \equiv 6$, $3^4 \equiv 4$, $3^5 \equiv 5$, $3^6 \equiv 1$. The pattern $3, 2, 6, 4, 5, 1$ repeats every $6$ powers.

Step 2: place $3^{2026}$. $2026 = 6\cdot337+4$, so $3^{2026} \equiv 3^4 \equiv 4 \pmod 7$.

Step 3: add. $2026 = 7\cdot289+3$, so $2026 \equiv 3$. Then $3^{2026}+2026 \equiv 4+3 = 7 \equiv 0 \pmod 7$.

The answer is $\boxed{\textbf{(A)}\ 0}$.

Pitfalls

• Reducing the exponent by $m$ instead of the cycle length. Example: using $2026 \equiv 3 \pmod 7$ gives $3^3 \equiv 6$, which is wrong.
• Misplacing remainder $0$: it means the end of the cycle. Example: $2028 = 6\cdot338$, so $3^{2028}$ is the $6$th entry, $1$, not the first entry, $3$. Likewise $2^{2028}$ ends in $6$, the last of $2, 4, 8, 6$, not in $2^0 = 1$.
• Dividing both sides by a number that shares a factor with the modulus (see the $6 \equiv 16$ example above).
• Off-by-one errors in calendar problems: counting the starting day, or February in leap years. Example: $10$ days after a Monday is a Thursday ($10 = 7+3$), not a Wednesday.

Traps that recur

• Assuming the bits repeat 111 or 011 from the first few (x₀ = x₁ = x₂ = 1) without computing far enough to see the period-3 pattern 0,1,1. (2022 AMC 10B #25)
• Reducing 90! mod 100 directly (it is 0) or forgetting that removing 21 factors of 5 also requires removing exactly 21 factors of 2. (2010 AMC 10A #24)
• Assuming powers spread out over many residues (answering 25 or 125) instead of testing whether 100 is a multiple of the order of every unit mod 125. (2024 AMC 10B #18)
• Testing only whether each fraction is an integer separately; for odd m none of them is, yet the fractional parts 1/2 + 1/4 + 1/8 + 1/8 add up to exactly 1. (2024 AMC 10B #24)