Modular Arithmetic and Number Theory Tricks

"What's the last digit of $7^{100}$?" isn't about computing $7^{100}$ — it's about realizing that only remainders matter, then working entirely in that smaller world. Modular arithmetic is that world, and a surprising number of brainteasers live there.

Working mod n

$a \equiv b \pmod{n}$ means $a$ and $b$ leave the same remainder dividing by $n$. The superpower: congruences respect addition and multiplication — you may reduce at every step. Last digit questions are "work mod 10":

$$7^1 \equiv 7,\quad 7^2 \equiv 9,\quad 7^3 \equiv 3,\quad 7^4 \equiv 1 \pmod{10}$$

Powers of 7 cycle with period 4. Since $100 = 4 \times 25$, $7^{100} \equiv (7^4)^{25} \equiv 1$: last digit 1. Every "last digit / remainder of a huge power" question is: find the cycle, reduce the exponent. (Fermat's little theorem guarantees such cycles: $a^{p-1} \equiv 1 \pmod p$ for prime $p$ not dividing $a$ — worth naming, rarely needed in full.)

Divisibility rules, explained not memorized

Why does "sum of digits divisible by 3" test divisibility by 3? Because $10 \equiv 1 \pmod 3$, so $d_k 10^k + \cdots + d_0 \equiv d_k + \cdots + d_0$. The mod-9 rule is identical ("casting out nines" — a genuinely useful checksum for mental arithmetic in the trainer: your answer's digit sum must match the inputs'). For 11: $10 \equiv -1$, so alternate-sum the digits. Deriving a rule on demand beats memorizing all of them.

Parity and invariants: the brainteaser engine

The deepest use of "mod 2" is the invariant argument — find a quantity that every allowed move preserves, then show start and target differ on it:

• Mutilated chessboard: remove two opposite corners; can 31 dominoes tile the rest? Each domino covers one black and one white square, but the removed corners share a color: 32 of one color, 30 of the other. Impossible — one sentence, once you count mod colors.
• Cup flips: 7 cups face-down, flip exactly 4 at a time — can all end face-up? Each move changes the number of face-up cups by an even amount; you need a change of 7, odd. Never.
• The locker puzzle from the question bank was this too: divisor-count parity.

The meta-skill: when a puzzle asks "can you get from A to B with these moves?", hunt for a conserved quantity before hunting for a sequence of moves. Invariants prove impossibility; exhibiting moves proves possibility; nothing else does either.

Small kit worth carrying

Squares are $\equiv 0$ or $1 \pmod 4$ (so a number $\equiv 3 \pmod 4$ is never a sum of two squares); $n$ and its digit sum are congruent mod 9; among any $n$ integers, some pair differs by a multiple of... rather, some subset sums to a multiple of $n$ (pigeonhole on prefix sums mod $n$ — a classic proof worth knowing); and gcd via the Euclidean algorithm, $O(\log)$ steps — also the coding course's canonical recursion.

The interview version

"Remainder of $2^{50}$ divided by 7?" — $2^3 \equiv 1 \pmod 7$, $50 = 3\cdot16 + 2$, so $2^{50} \equiv 2^2 = \mathbf{4}$. "A dragon has 100 heads; you can cut 15, 17, 20, or 5, but heads regrow…" — whatever the variant, check what each move does mod some small number before anything else. Modular thinking is fast precisely because it throws information away — keeping only what the question actually depends on.