Olympiad number theory

Legendre's formula is the standard tool for computing exact prime-power divisibility of factorials and binomial coefficients, and combined with Kummer's theorem it explains exactly which binomial coefficients are divisible by a given prime.

**Step 1: Write $v_p(n!)$ as a sum over the factors.** By definition $n! = 1\cdot 2\cdots n$, so $v_p(n!) = \sum_{k=1}^{n} v_p(k)$, the sum of the $p$-adic valuation of every integer from $1$ to $n$.

**Step 2: Rewrite each $v_p(k)$ as a count.** For each $k$, $v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$ (using Iverson bracket notation, $1$ if true, $0$ if false), since $k$ is divisible by $p^i$ for exactly $v_p(k)$ values of $i$ (namely $i=1,\dots,v_p(k)$).

Step 3: Swap the order of summation. Substituting, $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$, exchanging the (finite, so justified) double sum.

**Step 4: Count multiples of $p^i$ directly.** The inner sum $\sum_{k=1}^n [p^i \mid k]$ counts how many integers from $1$ to $n$ are multiples of $p^i$, which is exactly $\left\lfloor \frac{n}{p^i} \right\rfloor$ (the multiples are $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$).

Step 5: Conclude. Substituting back, $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$, which is finite since $\lfloor n/p^i \rfloor = 0$ once $p^i > n$, completing the proof.

LTE turns a hard question about divisibility of a difference of high powers into simple arithmetic on valuations, and is one of the fastest ways to solve olympiad problems asking for the largest power of a prime dividing an expression like $a^n-b^n$ or to prove such an expression is never (or always) divisible by some prime power.

**Step 1: Reduce to the case $n=p$ via multiplicativity.** Write $n = p^{v_p(n)} \cdot m$ with $p \nmid m$. Repeated application of the $n=p$ case (proved below) to $a^m, b^m$ in place of $a,b$ shows $v_p(a^n-b^n) = v_p((a^m)^{p^{v_p(n)}} - (b^m)^{p^{v_p(n)}}) = v_p(a^m-b^m) + v_p(n)$, so it suffices to prove $v_p(a^m - b^m) = v_p(a-b)$ whenever $p \nmid m$, and to prove the base step $v_p(a^p-b^p) = v_p(a-b)+1$.

Step 2: Prove the base step using the factorization. Factor $a^p - b^p = (a-b)(a^{p-1}+a^{p-2}b+\cdots+b^{p-1})$. We must show the second factor $S = \sum_{j=0}^{p-1} a^{p-1-j}b^j$ has $v_p(S) = 1$.

**Step 3: Show $p \mid S$.** Since $p \mid a-b$, we have $a \equiv b \pmod p$, so each term $a^{p-1-j}b^j \equiv b^{p-1-j}b^j = b^{p-1} \pmod p$. Summing all $p$ terms, $S \equiv p\cdot b^{p-1} \equiv 0 \pmod p$ (using $p \nmid b$), so $p \mid S$.

**Step 4: Show $p^2 \nmid S$.** Write $a = b + pt$ for integer $t$ (possible since $p\mid a-b$). Expand each term $a^{p-1-j}b^j = (b+pt)^{p-1-j}b^j \equiv b^{p-1-j}b^j + (p-1-j)pt\, b^{p-2-j}b^j \pmod{p^2}$ (binomial expansion, dropping terms with $p^2$ or higher). Summing over $j=0,\dots,p-1$: the leading terms sum to $p\,b^{p-1}$ as before, and the correction terms sum to $pt\,b^{p-2}\sum_{j=0}^{p-1}(p-1-j) = pt\,b^{p-2}\cdot\frac{p(p-1)}{2}$, which is divisible by $p^2$ (since $p$ is odd, $\frac{p-1}{2}$ is an integer, so this correction is $p^2\cdot(\text{integer})$, hence $\equiv 0 \pmod{p^2}$). So $S \equiv p\,b^{p-1} \pmod{p^2}$, and since $p \nmid b$, $p\,b^{p-1}$ is divisible by $p$ but not $p^2$, giving $v_p(S)=1$.

Step 5: Combine. From Steps 2–4, $v_p(a^p-b^p) = v_p(a-b) + v_p(S) = v_p(a-b)+1$. Combined with the reduction in Step 1 (and the fact $v_p(a^m-b^m)=v_p(a-b)$ when $p\nmid m$, provable the same way since then $S \equiv m\,b^{m-1} \not\equiv 0 \pmod p$), induction on $v_p(n)$ gives $v_p(a^n-b^n) = v_p(a-b)+v_p(n)$ for all positive integers $n$.