uniolympiads Ελληνικά

Number theory: divisibility and congruences

Bézout, Fermat–Euler–Wilson, the order modulo nn, the Chinese remainder theorem, Legendre's formula for vp(n!)v_p(n!), lifting the exponent, quadratic residues and pigeonhole arguments.

What to know by heart

Divisibility. gcd⁡(a,b)\gcd(a, b) is the smallest positive integer of the form ax+byax + by with x,y∈Zx, y \in \Z (Bézout). Consequences:

  • if d∣ad \mid a and d∣bd \mid b, then d∣gcd⁡(a,b)d \mid \gcd(a, b);
  • if pp is prime and p∣abp \mid ab, then p∣ap \mid a or p∣bp \mid b;
  • if gcd⁡(a,n)=1\gcd(a, n) = 1, then aa has an inverse modulo nn, and from ac≡bcac \equiv bc you may cancel cc when gcd⁡(c,n)=1\gcd(c, n) = 1;
  • gcd⁡(am−1,an−1)=agcd⁡(m,n)−1\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1 for an integer a≥2a \ge 2.

The three classical theorems. For a prime pp and gcd⁡(a,n)=1\gcd(a, n) = 1:

ap≡a(modp)(Fermat),aφ(n)≡1(modn)(Euler),(p−1)!≡−1(modp)(Wilson).a^p \equiv a \pmod p \quad \text{(Fermat)}, \qquad a^{\varphi(n)} \equiv 1 \pmod n \quad \text{(Euler)}, \qquad (p - 1)! \equiv -1 \pmod p \quad \text{(Wilson)}.

Order. If gcd⁡(a,n)=1\gcd(a, n) = 1, the order ord⁡n(a)\operatorname{ord}_n(a) is the least d≥1d \ge 1 with ad≡1(modn)a^d \equiv 1 \pmod n. Then

ak≡1(modn)  ⟺  ord⁡n(a)∣k,soord⁡n(a)∣φ(n).a^k \equiv 1 \pmod n \iff \operatorname{ord}_n(a) \mid k, \qquad \text{so} \quad \operatorname{ord}_n(a) \mid \varphi(n).

Primitive roots (statement only). There is gg with ord⁡n(g)=φ(n)\operatorname{ord}_n(g) = \varphi(n) exactly when n∈{1,2,4,pk,2pk}n \in \{1, 2, 4, p^k, 2p^k\} with pp an odd prime. In particular (Z/pZ)∗(\Z/p\Z)^{*} is cyclic of order p−1p - 1, so xd≡1(modp)x^d \equiv 1 \pmod p has exactly gcd⁡(d,p−1)\gcd(d, p - 1) solutions.

Chinese remainder theorem. If gcd⁡(m,n)=1\gcd(m, n) = 1, then for all a,ba, b the system x≡a(modm)x \equiv a \pmod m, x≡b(modn)x \equiv b \pmod n has exactly one solution modulo mnmn. Hence the number of solutions of a polynomial congruence modulo nn is the product of the numbers of solutions modulo the prime powers of nn.

Legendre's formula. With vpv_p the exponent of pp and sp(n)s_p(n) the digit sum of nn in base pp:

vp(n!)=∑i≥1⌊npi⌋=n−sp(n)p−1.v_p(n!) = \sum_{i \ge 1} \left\lfloor \frac{n}{p^i} \right\rfloor = \frac{n - s_p(n)}{p - 1} .

For example v2(100!)=97v_2(100!) = 97 and v5(100!)=24v_5(100!) = 24, so 100!100! ends in 2424 zeros.

Lifting the exponent. If pp is an odd prime, p∣a−bp \mid a - b and p∤abp \nmid ab, then for every n≥1n \ge 1

vp(an−bn)=vp(a−b)+vp(n).v_p(a^n - b^n) = v_p(a - b) + v_p(n) .

For p=2p = 2, with a,ba, b odd and nn even: v2(an−bn)=v2(a−b)+v2(a+b)+v2(n)−1v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1. Example: v3(427−1)=1+3=4v_3(4^{27} - 1) = 1 + 3 = 4 and v2(38−1)=1+2+3−1=5v_2(3^8 - 1) = 1 + 2 + 3 - 1 = 5.

Quadratic residues, briefly. For an odd prime pp, exactly p−12\frac{p - 1}{2} of 1,…,p−11, \dots, p - 1 are squares modulo pp. Euler's criterion: for p∤ap \nmid a,

a(p−1)/2≡{1,a a square mod p,−1,otherwise.a^{(p-1)/2} \equiv \begin{cases} 1, & a \text{ a square mod } p, \\ -1, & \text{otherwise}. \end{cases}

In particular −1-1 is a square modulo pp exactly when p≡1(mod4)p \equiv 1 \pmod 4.

Standard lemmas with short proofs

Bézout. Let dd be the smallest positive element of {ax+by}\{ax + by\}. Dividing, a=qd+ra = qd + r with 0≤r<d0 \le r < d, and r=a−qdr = a - qd again has the form ax+byax + by. By minimality r=0r = 0, so d∣ad \mid a, and similarly d∣bd \mid b. Every common divisor of a,ba, b divides dd.

Euler (and Fermat). If r1,…,rφ(n)r_1, \dots, r_{\varphi(n)} are the residues coprime to nn, then ar1,…,arφ(n)a r_1, \dots, a r_{\varphi(n)} are the same residues in another order (multiplication by aa can be undone). Equating products, aφ(n)∏ri≡∏ria^{\varphi(n)} \prod r_i \equiv \prod r_i, and you cancel ∏ri\prod r_i.

Wilson. Modulo pp, every x∈{1,…,p−1}x \in \{1, \dots, p - 1\} has an inverse. We have x≡x−1x \equiv x^{-1} only when p∣(x−1)(x+1)p \mid (x - 1)(x + 1), that is x≡±1x \equiv \pm 1. The residues pair off with their inverses, each pair has product 11, and what is left is 1⋅(−1)1 \cdot (-1).

The order divides. With d=ord⁡n(a)d = \operatorname{ord}_n(a) and k=qd+rk = qd + r, 0≤r<d0 \le r < d: if ak≡1a^k \equiv 1, then ar≡1a^r \equiv 1, so r=0r = 0.

Legendre. vp(n!)v_p(n!) counts each m≤nm \le n as many times as vp(m)v_p(m). The number mm is counted once for each ii with pi∣mp^i \mid m, and the multiples of pip^i in {1,…,n}\{1, \dots, n\} number ⌊n/pi⌋\lfloor n / p^i \rfloor.

LTE for odd pp.

  • If p∤np \nmid n: an−bna−b=∑i=0n−1an−1−ibi≡nbn−1≢0(modp)\frac{a^n - b^n}{a - b} = \sum_{i=0}^{n-1} a^{n-1-i} b^i \equiv n b^{n-1} \not\equiv 0 \pmod p, since a≡ba \equiv b.
  • For n=pn = p: write a=b+tpa = b + tp. Then ap−1−i≡bp−1−i+(p−1−i) tp bp−2−i(modp2)a^{p-1-i} \equiv b^{p-1-i} + (p - 1 - i)\, t p\, b^{p-2-i} \pmod{p^2}, and summing
∑i=0p−1ap−1−ibi≡p bp−1+tp bp−2⋅p(p−1)2≡p bp−1(modp2),\sum_{i=0}^{p-1} a^{p-1-i} b^i \equiv p\, b^{p-1} + tp\, b^{p-2} \cdot \frac{p(p-1)}{2} \equiv p\, b^{p-1} \pmod{p^2},

since p−12\frac{p - 1}{2} is an integer (this is where pp odd is needed). So the factor contains exactly one pp. Writing n=pkmn = p^k m with p∤mp \nmid m, apply the two steps inductively.

Euler's criterion. If a≡x2a \equiv x^2, then a(p−1)/2≡xp−1≡1a^{(p-1)/2} \equiv x^{p-1} \equiv 1. The polynomial X(p−1)/2−1X^{(p-1)/2} - 1 has at most p−12\frac{p-1}{2} roots in Fp\F_p, and the p−12\frac{p - 1}{2} distinct squares (x2x^2 and (−x)2(-x)^2 coincide) are already roots. For the remaining aa we have (a(p−1)/2)2≡1\big(a^{(p-1)/2}\big)^2 \equiv 1 and a(p−1)/2≢1a^{(p-1)/2} \not\equiv 1, hence ≡−1\equiv -1.

Typical tricks

  • Try small moduli. Squares modulo 88 are 0,1,40, 1, 4; fourth powers modulo 1616 are 0,10, 1; cubes modulo 99 are 0,±10, \pm 1. Quite a few "impossible" problems die here.
  • Reduce the exponent with the order. To find aN mod na^N \bmod n, find dd with ad≡1a^d \equiv 1 (the order, or a divisor of φ(n)\varphi(n)) and keep N mod dN \bmod d.
  • From a congruence to an order. If x4≡−y4(modp)x^4 \equiv -y^4 \pmod p with p∤yp \nmid y, then (xy−1)4≡−1(x y^{-1})^4 \equiv -1, so ord⁡p(xy−1)=8\operatorname{ord}_p(x y^{-1}) = 8 and 8∣p−18 \mid p - 1. In general, if p≡3(mod4)p \equiv 3 \pmod 4 and p∣x2+y2p \mid x^2 + y^2, then p∣xp \mid x and p∣yp \mid y.
  • Split with the CRT. The congruence x2≡x(modpk)x^2 \equiv x \pmod{p^k} has only the solutions 0,10, 1, because xx and x−1x - 1 are coprime. So modulo nn with rr distinct prime factors it has 2r2^r solutions.
  • Power sums. For a prime pp and k≥1k \ge 1, ∑x=0p−1xk≡0(modp)\sum_{x=0}^{p-1} x^k \equiv 0 \pmod p unless (p−1)∣k(p - 1) \mid k, in which case the sum is ≡−1\equiv -1. (If (p−1)∤k(p - 1) \nmid k, take cc with ck≢1c^k \not\equiv 1; multiplication by cc permutes the residues, so ckS≡Sc^k S \equiv S.)
  • Polynomials modulo pp. A nonzero polynomial of degree dd has at most dd roots in Fp\F_p, and Xp−X=∏a∈Fp(X−a)X^p - X = \prod_{a \in \F_p} (X - a).
  • Pigeonhole and density. Among n+1n + 1 integers, two are congruent modulo nn. Among nn integers a1,…,ana_1, \dots, a_n, some nonempty block of consecutive terms has sum divisible by nn (look at the nn partial sums and 00). For real α\alpha and N≥1N \ge 1 there is 1≤q≤N1 \le q \le N with ∣qα−m∣<1N|q \alpha - m| < \frac{1}{N} for some integer mm (Dirichlet: N+1N + 1 fractional parts in NN 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 2929 are only 77 residues, since 4∣284 \mid 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 10k10^{k} splits into two congruences modulo 2k2^k and 5k5^k.
  • Polynomial congruences modulo pp (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\F_p, power sums.
  • Legendre and the prime divisors of n!+1n! + 1 (IMC 2012, day 2, problem 3): every prime divisor of n!+1n! + 1 is larger than nn.
  • 22-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)2x \equiv 2 \pmod 6 you get x≡1(mod3)x \equiv 1 \pmod 3, not (mod6)\pmod 6.
  • Euler needs gcd⁡(a,n)=1\gcd(a, n) = 1. 2φ(4)=4≢1(mod4)2^{\varphi(4)} = 4 \not\equiv 1 \pmod 4.
  • LTE for p=2p = 2 has a different formula. v2(32−1)=3v_2(3^2 - 1) = 3, while the odd-pp formula would give v2(3−1)+v2(2)=2v_2(3 - 1) + v_2(2) = 2.
  • A primitive root does not always exist. Modulo 88 every odd number has x2≡1x^2 \equiv 1, so no order equals φ(8)=4\varphi(8) = 4.

Further reading

  • Gelca & Andreescu, Putnam and Beyond, §1.3 (The Pigeonhole Principle)

Contest problems using these tools

No problems with these tools yet.