← Topic 2 · Number Theory
AMC 10/12 · Topic Cheatsheet

Topic 2 · Number Theory

17 key results accumulated across 4 chapters.

Congruence
Ch 1
a≡b(modm)  ⟺  m∣(a−b)a \equiv b \pmod m \iff m \mid (a-b)
Operations
Ch 1
Add, subtract, multiply congruences freely; division only by residues coprime to mm.
Last digit
Ch 1
Powers cycle mod 10; reduce the exponent by the cycle length.
Divisor count
Ch 1
n=∏piai⇒d(n)=∏(ai+1)n=\prod p_i^{a_i} \Rightarrow d(n)=\prod (a_i+1)
Perfect squares
Ch 1
Odd number of divisors ⟺ perfect square.
GCD / LCM
Ch 2
gcd⁡:min⁡ exps,    lcm⁡:max⁡ exps\gcd: \min\text{ exps},\;\; \operatorname{lcm}: \max\text{ exps}
Product identity
Ch 2
gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab
Base = polynomial
Ch 2
dk⋯d0‾b=∑dibi\overline{d_k\cdots d_0}_b = \sum d_i b^i
Digit-sum (mod 9)
Ch 2
n≡n \equiv digit sum (mod9)\pmod 9 since 10i≡110^i\equiv1.
Fermat
Ch 3
ap−1≡1(modp)  (p∤a)a^{p-1}\equiv 1 \pmod p\;(p\nmid a)
Euler
Ch 3
aϕ(n)≡1(modn)  (gcd⁡(a,n)=1)a^{\phi(n)}\equiv 1 \pmod n\;(\gcd(a,n)=1)
Totient
Ch 3
ϕ(pe)=pe−1(p−1)\phi(p^e)=p^{e-1}(p-1)
CRT
Ch 3
Coprime moduli ⇒\Rightarrow unique solution mod their product.
Order definition
Ch 4
ordn(a)=min⁡{k≥1:ak≡1(modn)}\text{ord}_n(a) = \min\{k \ge 1 : a^k \equiv 1 \pmod n\}
Lagrange bound
Ch 4
ordn(a)∣ϕ(n)\text{ord}_n(a) \mid \phi(n)
Power reduction
Ch 4
ak≡ak mod ordn(a)(modn)a^k \equiv a^{k \bmod \text{ord}_n(a)} \pmod n
Primitive root
Ch 4
Element of order ϕ(n)\phi(n); exists mod every prime pp.