Section 31.1

Divisibility and Primes

Factorisations, divisor counting, primality checks, trailing zeros of factorials, light switches and divisors.

Toolkit

Core tool is unique prime factorisation: every integer $n=\prod p_i^{a_i}$ , and all divisibility, counting, and parity questions reduce to tracking these exponents.

Number of divisors: $d(n)=\prod (a_i+1)$ ; sum of divisors $\sigma(n)=\prod \frac{p_i^{a_i+1}-1}{p_i-1}$ .
$n$ is a perfect square iff every $a_i$ is even; a uniform random divisor of $n$ has independent exponents, each uniform on $\{0,\dots,a_i\}$ , so $\mathbb{P}(\text{divisor divisible by }m)=\prod_i \frac{a_i-b_i+1}{a_i+1}$ where $m=\prod p_i^{b_i}$ .
Legendre’s formula: $v_p(n!)=\sum_{k\ge1}\lfloor n/p^k\rfloor$ ; trailing zeros of $n!$ in base $10$ equal $v_5(n!)$ since $v_5\le v_2$ .
gcd/lcm control common structure: $a\mid b$ and $a\mid c \Rightarrow a\mid\gcd(b,c)$ ; recurring events with periods $T_1,\dots,T_k$ realign after $\mathrm{lcm}(T_1,\dots,T_k)$ .
If a product of integers equals a prime $p$ , all factors are $\pm1$ except one equal to $\pm p$ .
$n\mid 360$ (or similar) problems reduce to counting divisors from the factorisation of the fixed number.

Problems