What to know by heart
Divisibility. gcd(a,b) is the smallest positive integer of the form ax+by with x,y∈Z (Bézout). Consequences:
- if d∣a and d∣b, then d∣gcd(a,b);
- if p is prime and p∣ab, then p∣a or p∣b;
- if gcd(a,n)=1, then a has an inverse modulo n, and from ac≡bc you may cancel c when gcd(c,n)=1;
- gcd(am−1,an−1)=agcd(m,n)−1 for an integer a≥2.
The three classical theorems. For a prime p and gcd(a,n)=1:
ap≡a(modp)(Fermat),aφ(n)≡1(modn)(Euler),(p−1)!≡−1(modp)(Wilson).
Order. If gcd(a,n)=1, the order ordn(a) is the least d≥1 with ad≡1(modn). Then
ak≡1(modn)⟺ordn(a)∣k,soordn(a)∣φ(n).
Primitive roots (statement only). There is g with ordn(g)=φ(n) exactly when n∈{1,2,4,pk,2pk} with p an odd prime. In particular (Z/pZ)∗ is cyclic of order p−1, so xd≡1(modp) has exactly gcd(d,p−1) solutions.
Chinese remainder theorem. If gcd(m,n)=1, then for all a,b the system x≡a(modm), x≡b(modn) has exactly one solution modulo mn. Hence the number of solutions of a polynomial congruence modulo n is the product of the numbers of solutions modulo the prime powers of n.
Legendre's formula. With vp the exponent of p and sp(n) the digit sum of n in base p:
vp(n!)=i≥1∑⌊pin⌋=p−1n−sp(n).
For example v2(100!)=97 and v5(100!)=24, so 100! ends in 24 zeros.
Lifting the exponent. If p is an odd prime, p∣a−b and p∤ab, then for every n≥1
vp(an−bn)=vp(a−b)+vp(n).
For p=2, with a,b odd and n even: v2(an−bn)=v2(a−b)+v2(a+b)+v2(n)−1. Example: v3(427−1)=1+3=4 and v2(38−1)=1+2+3−1=5.
Quadratic residues, briefly. For an odd prime p, exactly 2p−1 of 1,…,p−1 are squares modulo p. Euler's criterion: for p∤a,
a(p−1)/2≡{1,−1,a a square mod p,otherwise.
In particular −1 is a square modulo p exactly when p≡1(mod4).
Standard lemmas with short proofs
Bézout. Let d be the smallest positive element of {ax+by}. Dividing, a=qd+r with 0≤r<d, and r=a−qd again has the form ax+by. By minimality r=0, so d∣a, and similarly d∣b. Every common divisor of a,b divides d.
Euler (and Fermat). If r1,…,rφ(n) are the residues coprime to n, then ar1,…,arφ(n) are the same residues in another order (multiplication by a can be undone). Equating products, aφ(n)∏ri≡∏ri, and you cancel ∏ri.
Wilson. Modulo p, every x∈{1,…,p−1} has an inverse. We have x≡x−1 only when p∣(x−1)(x+1), that is x≡±1. The residues pair off with their inverses, each pair has product 1, and what is left is 1⋅(−1).
The order divides. With d=ordn(a) and k=qd+r, 0≤r<d: if ak≡1, then ar≡1, so r=0.
Legendre. vp(n!) counts each m≤n as many times as vp(m). The number m is counted once for each i with pi∣m, and the multiples of pi in {1,…,n} number ⌊n/pi⌋.
LTE for odd p.
- If p∤n: a−ban−bn=∑i=0n−1an−1−ibi≡nbn−1≡0(modp), since a≡b.
- For n=p: write a=b+tp. Then ap−1−i≡bp−1−i+(p−1−i)tpbp−2−i(modp2), and summing
i=0∑p−1ap−1−ibi≡pbp−1+tpbp−2⋅2p(p−1)≡pbp−1(modp2),
since 2p−1 is an integer (this is where p odd is needed). So the factor contains exactly one p. Writing n=pkm with p∤m, apply the two steps inductively.
Euler's criterion. If a≡x2, then a(p−1)/2≡xp−1≡1. The polynomial X(p−1)/2−1 has at most 2p−1 roots in Fp, and the 2p−1 distinct squares (x2 and (−x)2 coincide) are already roots. For the remaining a we have (a(p−1)/2)2≡1 and a(p−1)/2≡1, hence ≡−1.
Typical tricks
- Try small moduli. Squares modulo 8 are 0,1,4; fourth powers modulo 16 are 0,1; cubes modulo 9 are 0,±1. Quite a few "impossible" problems die here.
- Reduce the exponent with the order. To find aNmodn, find d with ad≡1 (the order, or a divisor of φ(n)) and keep Nmodd.
- From a congruence to an order. If x4≡−y4(modp) with p∤y, then (xy−1)4≡−1, so ordp(xy−1)=8 and 8∣p−1. In general, if p≡3(mod4) and p∣x2+y2, then p∣x and p∣y.
- Split with the CRT. The congruence x2≡x(modpk) has only the solutions 0,1, because x and x−1 are coprime. So modulo n with r distinct prime factors it has 2r solutions.
- Power sums. For a prime p and k≥1, ∑x=0p−1xk≡0(modp) unless (p−1)∣k, in which case the sum is ≡−1. (If (p−1)∤k, take c with ck≡1; multiplication by c permutes the residues, so ckS≡S.)
- Polynomials modulo p. A nonzero polynomial of degree d has at most d roots in Fp, and Xp−X=∏a∈Fp(X−a).
- Pigeonhole and density. Among n+1 integers, two are congruent modulo n. Among n integers a1,…,an, some nonempty block of consecutive terms has sum divisible by n (look at the n partial sums and 0). For real α and N≥1 there is 1≤q≤N with ∣qα−m∣<N1 for some integer m (Dirichlet: N+1 fractional parts in N intervals). The same works for several numbers at once, with cubes in place of intervals.
How they appear in the IMC
- Fourth powers modulo a prime (IMC 2007, day 2, problem 2). The nonzero fourth powers modulo 29 are only 7 residues, since 4∣28; a quick check shows which sums of three of them vanish.
- CRT to count solutions (IMC 2006, day 1, problem 2): the congruence modulo 10k splits into two congruences modulo 2k and 5k.
- Polynomial congruences modulo p (IMC 2020, day 2, problem 6; IMC 2023, day 1, problem 4; IMC 2022, day 2, problem 6): Fermat, the number of roots in Fp, power sums.
- Legendre and the prime divisors of n!+1 (IMC 2012, day 2, problem 3): every prime divisor of n!+1 is larger than n.
- 2-adic valuation of a sum (IMC 2008, day 2, problem 3).
- Greatest common divisor and Bézout in sets closed under operations (IMC 2025, day 2, problem 7).
- Simultaneous Dirichlet approximation (IMC 2026, day 2, problem 10).
Pitfalls
- Cancel only what is coprime to the modulus. From 2x≡2(mod6) you get x≡1(mod3), not (mod6).
- Euler needs gcd(a,n)=1. 2φ(4)=4≡1(mod4).
- LTE for p=2 has a different formula. v2(32−1)=3, while the odd-p formula would give v2(3−1)+v2(2)=2.
- A primitive root does not always exist. Modulo 8 every odd number has x2≡1, so no order equals φ(8)=4.
No problems with these tools yet.