Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 11G (Number Theory)

For a prime $p$ and a positive integer $N$, the P-adic valuation is

Because $p\ge k+2$, neither $(k+1)!$ nor $k!$ contains a factor $p$. On the other hand, $p\le 2k+1$, so $(2k+1)!$ contains a factor $p$; andso it contains no second factor $p$. ThereforeThis is the valuation of a near-central binomial coefficient.

It suffices first to prove the elementary primorial bound for positive integers $n$, by strong induction. The case $n=1$ is immediate.

If $n=2k$, every prime $p$ with $k<p\le 2k$ divides $\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$: the numerator $(2k)!$ contains $p$, whereas the two copies of $k!$ do not. Since these primes are distinct,The induction hypothesis and the binomial theorem give

If $n=2k+1$, part (b) shows that every prime $k+2\le p\le 2k+1$ divides $\left(\genfrac{}{}{0ex}{}{2k+1}{k+1}\right)$. HenceThe two central coefficients of $(1+1{)}^{2k+1}$ are equal, soand thereforeThis completes the induction. For real $X\ge 1$,

Every prime in $(\sqrt{X},X]$ is at least $\sqrt{X}$. Consequently the primorial satisfiesCombining this with part (c) and taking logarithms givessoFor $X\ge 2$, the inequality $\log X\le \sqrt{X}$ impliesThus the prime-counting upper bound from a primorial estimate yieldsWe may take $c=1+2\log 4$.