← Back to AMC course
Number Theory · Recognition Drill
Number Theory · 30 stems · 8s per card
30 contest stems on integers — divisibility, primes, modular arithmetic, bases. Classify each in 5 seconds (8 in coach mode).
Year-8 notation glossary — read this first
' divides ' — there is an integer with .
and leave the same remainder when divided by .
Greatest common divisor — largest integer dividing both.
Least common multiple — smallest positive multiple of both.
or
Number of positive divisors of .
Sum of positive divisors of .
(Euler totient)
Number of integers with .
Floor — round DOWN to an integer.
Technique deck — what the button labels mean
Modular arithmetic
Arithmetic on remainders: $a \equiv b \pmod m$ means $m \mid (a - b)$.
Fermat's little theorem
If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod p$.
Euler's totient theorem
Generalises Fermat: $a^{\phi(n)} \equiv 1 \pmod n$ when $\gcd(a, n) = 1$.
Cycle of powers (period mod n)
Powers of $a$ mod $n$ eventually repeat — find the period and reduce the exponent.
Prime factorization
Every positive integer has a unique factorization $p_1^{a_1} \cdots p_k^{a_k}$.
Divisor count $d(n)$
If $n = p_1^{a_1} \cdots p_k^{a_k}$, then $d(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$.
Divisor sum $\sigma(n)$
Sum of all positive divisors of $n$; multiplicative across coprime factors.
GCD / Euclidean algorithm
$\gcd(a, b) = \gcd(b, a \bmod b)$ — fast greatest common divisor.
LCM
$\text{lcm}(a, b) = ab / \gcd(a, b)$.
Bezout's identity
There exist integers $x, y$ with $ax + by = \gcd(a, b)$.
Chinese Remainder Theorem
Solve $x \equiv a \pmod m, x \equiv b \pmod n$ uniquely mod $mn$ when $\gcd(m, n) = 1$.
Legendre's formula (factorial exponent)
Exponent of prime $p$ in $n!$ is $\sum_{i \ge 1} \lfloor n/p^i \rfloor$.
Trailing-zero count
Trailing zeros of $n!$ = exponent of $5$ in $n!$ (Legendre with $p = 5$).
Base conversion
Repeatedly divide by the new base; the remainders (read in reverse) give the digits.
Last-digit / mod-10 cycle
Last digits of $a^n$ cycle with period dividing $4$; reduce $n$ mod $4$.
Divisibility rules
By $3$/$9$: digit sum. By $11$: alternating digit sum. By $4$: last two digits.
Difference of squares (factoring)
$x^2 - y^2 = (x - y)(x + y)$ — for Diophantines of this form.
SFFT (Simon's Favourite Factoring)
Add a constant to $xy + ax + by$ so it factors as a product.
Bounding (size argument)
Show $a < n < b$ to pin down a unique integer or rule out solutions.
Perfect square / parity mod 4
Squares are $0$ or $1$ mod $4$ — use to rule out cases.
Sum of digits
Used for divisibility by $3$ or $9$ and for digit-based contest problems.
Number of factors of a binomial
Prime $p$ appears in $\binom{n}{k}$ by $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ or directly via Kummer's theorem.
Wilson's theorem
$p$ prime $\Leftrightarrow (p - 1)! \equiv -1 \pmod p$.
Modular inverse
$a^{-1} \pmod m$ exists iff $\gcd(a, m) = 1$; find via extended Euclidean or Fermat.
Direct enumeration
When the search space is small, just list cases.
Casework
Partition the problem into disjoint scenarios (e.g., by parity, residue, sign), solve each, combine.
Inclusion-exclusion (PIE)
$|A \cup B| = |A| + |B| - |A \cap B|$ — count divisible-by-this OR divisible-by-that without double counting.
Complementary counting
Count the OPPOSITE event and subtract from the total.