Olympiad Number Theory V: Legendre, Pell & Möbius

It answers every "how many trailing zeros / what power of $p$ divides" question in one line: $v_3(1000!) = 333 + 111 + 37 + 12 + 4 + 1 = 498$, and the digit-sum form confirms it since $1000 = (1101001)_3$ has digit sum $4$ and $\tfrac{1000-4}{2} = 498$. Combined with Kummer's theorem — $v_p\binom{m+n}{n}$ is the number of carries when adding $m$ and $n$ in base $p$ — it also controls binomial coefficients, which is where the olympiad applications live.

Multiplicativity is what makes it fast: to test $1$ through $30$ modulo $101$ you evaluate eight prime symbols and multiply, finding $17$ residues — $1, 4, 5, 6, 9, 13, 14, 16, 17, 19, 20, 21, 22, 23, 24, 25, 30$. Exactly half of the $100$ nonzero classes are squares, so a count near $15$ is the sanity check. The symbol is also the standard way to prove a Diophantine equation has no solutions: reduce mod a well-chosen prime and show one side is a non-residue.

The solutions grow fast, so searching is hopeless: for $d = 13$ the smallest is $(649, 180)$, which no hand search finds. The continued fraction $\sqrt{13} = [3;\overline{1,1,1,1,6}]$ has odd period, so the first convergent of the period, $\tfrac{18}{5}$, solves $x^2 - 13y^2 = -1$ and its square $(18+5\sqrt{13})^2 = 649 + 180\sqrt{13}$ solves $+1$. In olympiad use, Pell supplies the infinite family in "show there are infinitely many $n$ such that ..." and the recursion $x_{n+1} = 2x_1x_n - x_{n-1}$ supplies the induction.

Step 1 — factor the top: $219=3\cdot73$, so $\left(\tfrac{219}{383}\right)=\left(\tfrac3{383}\right)\left(\tfrac{73}{383}\right)$.

Step 2 — $3$ and $383$ are both $\equiv3\pmod4$, so reciprocity flips the sign: $\left(\tfrac3{383}\right)=-\left(\tfrac{383}3\right)=-\left(\tfrac23\right)=-(-1)=1$.

Step 3 — $73\equiv1\pmod4$, so no sign: $\left(\tfrac{73}{383}\right)=\left(\tfrac{383}{73}\right)=\left(\tfrac{18}{73}\right)=\left(\tfrac2{73}\right)\left(\tfrac9{73}\right)=\left(\tfrac2{73}\right)=1$, since $73\equiv1\pmod8$.

Step 4 — so $\left(\tfrac{219}{383}\right)=1$: $219$ is a square mod $383$. (Euler's criterion confirms it: $219^{191}\equiv1\pmod{383}$.)

How to find it. Factor the top into primes, flip each prime symbol with reciprocity, reduce the new top modulo the new bottom, and repeat — a Euclid-like descent in which only the supplements for $-1$ and $2$ are ever evaluated directly.

Step 1 — compare exponents prime by prime. For a prime $p$, $v_p\left(\operatorname{lcm}(1,\dots,2n)\right)$ is the largest $k$ with $p^k\le2n$, namely $\lfloor\log_p2n\rfloor$.

Step 2 — by Kummer, $v_p\binom{2n}n$ is the number of carries when $n+n$ is added in base $p$.

Step 3 — a carry out of position $i$ produces a nonzero digit (or a new leading digit) in position $i+1$ of $2n$, so every carry happens at a position $i$ with $p^{i+1}\le2n$. There are at most $\lfloor\log_p2n\rfloor$ such positions.

Step 4 — so $v_p\binom{2n}n\le v_p(\operatorname{lcm})$ for every $p$, which is the claim. Example: $\binom{10}5=252=2^2\cdot3^2\cdot7$ divides $\operatorname{lcm}(1,\dots,10)=2520$.

How to find it. Divisibility between two integers is a prime-by-prime comparison of valuations. Kummer turns the binomial's valuation into a digit count, and the lcm's valuation is also a digit count — the number of base-$p$ digits of $2n$, minus one.

The product $\left(\tfrac23\right)\left(\tfrac25\right)$ is the Jacobi symbol, which obeys reciprocity but does not detect squares: $2$ is a non-residue both mod $3$ and mod $5$, and two failures multiply to $+1$. By the Chinese remainder theorem, $a$ is a square mod $15$ exactly when it is a square mod $3$ and mod $5$. The Jacobi symbol is safe for one thing: a value of $-1$ proves non-residuosity. A value of $+1$ proves nothing modulo a composite.

Multiplicativity reduces every evaluation to prime powers: $\tau(p^k) = k+1$, $\sigma(p^k) = \tfrac{p^{k+1}-1}{p-1}$, $\varphi(p^k) = p^k - p^{k-1}$, $\mu(p) = -1$, $\mu(p^k) = 0$ for $k\ge2$. It also lets you evaluate divisor sums by factoring: $\sum_{d\mid 60}\mu(d)d = (1-2)(1-3)(1-5) = -8$, no enumeration required.

The inversion is how you undo a divisor sum, and the identity $\sum_{d\mid n}\varphi(d) = n$ inverts to $\varphi(n) = \sum_{d\mid n}\mu(d)\tfrac nd$ — equivalently $\tfrac{\varphi(n)}{n} = \prod_{p\mid n}\left(1 - \tfrac1p\right)$, which is the inclusion–exclusion you would have written by hand. Counting necklaces, primitive roots of unity, and aperiodic strings all reduce to a Möbius sum.

Step 1 — every string of length $12$ is a repetition of a unique primitive block of some length $d\mid12$. With $P(d)$ the number of primitive strings of length $d$, this says $2^{12}=\sum_{d\mid12}P(d)$, and the same holds for every length: $2^n=\sum_{d\mid n}P(d)$.

Step 2 — Möbius inversion: $P(n)=\sum_{d\mid n}\mu(d)\,2^{n/d}$. For $n=12$ only $d=1,2,3,6$ contribute, with $\mu=1,-1,-1,1$: $P(12)=2^{12}-2^6-2^4+2^2=4096-64-16+4=4020$.

Step 3 — a primitive string has $12$ distinct rotations, all primitive, so the $4020$ strings fall into $\tfrac{4020}{12}=335$ necklaces.

How to find it. "Count the objects of exact size $n$" when you can easily count "objects of size dividing $n$" is always Möbius inversion. The divisibility of $4020$ by $12$ is a free sanity check.

Multiplicativity, $f(mn)=f(m)f(n)$, is only promised for coprime $m,n$, and $2,2$ are not coprime. The values on prime powers are independent data: $\tau(p^k)=k+1$, $\sigma(p^k)=1+p+\cdots+p^k$, $\varphi(p^k)=p^k-p^{k-1}$, $\mu(p^k)=0$ for $k\ge2$. Factor $n$ completely into prime powers first, evaluate on each, then multiply. (Functions like $n^s$ with $f(mn)=f(m)f(n)$ for all $m,n$ are called completely multiplicative; $\tau,\sigma,\varphi,\mu$ are not.)

Bertrand is a citation, not a computation: it instantly gives "there is a prime $p$ with $\tfrac n2 < p \le n$", which kills problems asking you to find a prime in a range or to show some product is not a perfect power. Small intervals are tight — $(5,10]$ holds only the prime $7$, and that is the last time a Bertrand interval holds just one — so a proof that leans on two primes in $(n,2n]$ must start at $n = 6$.

Count the factor $p$ in $1, 2, \dots, n$ by layers: $\left\lfloor n/p\right\rfloor$ of the numbers are divisible by $p$, and of those $\left\lfloor n/p^2\right\rfloor$ are divisible again, and so on. Each multiple of $p^k$ is counted once in each of the first $k$ layers, so it contributes exactly $k$ — which is its valuation. $\blacksquare$ Writing $n$ in base $p$ and summing the geometric series turns the sum into $\tfrac{n - s_p(n)}{p-1}$, the form that makes digit-sum problems immediate.

Only squarefree divisors contribute, so if $n$ has exactly $k \ge 1$ distinct prime factors the sum is $\sum_{j=0}^{k}\binom{k}{j}(-1)^j = (1-1)^k = 0$; for $n = 1$ the only divisor is $1$ and the sum is $1$. $\blacksquare$ Everything else about Möbius — the inversion formula, the totient product, inclusion–exclusion over prime divisors — is this identity applied inside a double sum.