LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-01

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Prime valuations in the central binomial coefficient

Statement

Let $n \geq 1$ be a natural number and let $p$ be a prime. Then

$v_{p} (n!) = \sum_{k \geq 1} ⌊ \frac{n}{p^{k}} ⌋$

and

$v_{p} (\binom{2 n}{n}) = \sum_{k \geq 1} (⌊ \frac{2 n}{p^{k}} ⌋ - 2 ⌊ \frac{n}{p^{k}} ⌋) .$

Consequently:

if $n < p \leq 2 n$ , then $v_{p} (\binom{2 n}{n}) = 1$ ;
in general, $v_{p} (\binom{2 n}{n}) \leq \frac{\log (2 n)}{\log p} .$

Facts & Assumptions

Given: A natural number $n \geq 1$ and a prime $p$ .

[L1]

For every nonzero integer $a$ , the valuation $v_{p} (a)$ is additive on products and detects exactly the powers $p^{k}$ that divide $a$ ( $v_{p} (a b) = v_{p} (a) + v_{p} (b)$ for nonzero integers $a, b$ , and $v_{p} (a + b) \geq \min {v_{p} (a), v_{p} (b)}$ whenever $a$ , $b$ and $a + b$ are all nonzero, For a prime $p$ and a nonzero integer $a$ : $p^{v_{p} (a)} ∣ a$ and $p^{v_{p} (a) + 1} ∤ a$ ; $p^{k} ∣ a$ holds exactly for $k \leq v_{p} (a)$ ; $v_{p} (a) \geq 1$ exactly when $p ∣ a$ ; $v_{p} (1) = v_{p} (- 1) = 0$ ; and $v_{p} (p) = 1$ , The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ).

[L2]

The factorial satisfies $n! = 1 \cdot 2 \dots n$ and $(\binom{2 n}{n}) n! n! = (2 n)!$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ , $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ , The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Proof

technique · direct

1.1L1L2givenalgebra

By [L2] and repeated use of additivity from [L1], $v_{p} (n!) = \sum_{m = 1}^{n} v_{p} (m) .$ For a fixed integer $m$ , [L1] says that $v_{p} (m)$ is exactly the number of positive integers $k$ for which $p^{k} ∣ m$ . Summing over $m \leq n$ therefore counts, for each $k \geq 1$ , how many multiples of $p^{k}$ lie in ${1, \dots, n}$ . That number is $⌊ n / p^{k} ⌋$ , so $v_{p} (n!) = \sum_{k \geq 1} ⌊ \frac{n}{p^{k}} ⌋ .$

2.1L1L2step 1.1algebra

Applying [L1] and [L2] to $(\binom{2 n}{n}) n! n! = (2 n)!$ gives $v_{p} (\binom{2 n}{n}) = v_{p} ((2 n)!) - 2 v_{p} (n!) .$ Substituting the formula from step 1.1 twice yields $v_{p} (\binom{2 n}{n}) = \sum_{k \geq 1} (⌊ \frac{2 n}{p^{k}} ⌋ - 2 ⌊ \frac{n}{p^{k}} ⌋) .$

3.1step 2.1givenalgebra

Suppose $n < p \leq 2 n$ . Then $⌊ 2 n / p ⌋ = 1$ and $⌊ n / p ⌋ = 0$ . Also $p^{2} > 2 n$ , so every term with $k \geq 2$ vanishes in step 2.1. Hence $v_{p} (\binom{2 n}{n}) = 1.$

3.2step 2.1algebra

For arbitrary $p$ , each summand in step 2.1 is either $0$ or $1$ , because $2 ⌊ n / p^{k} ⌋ \leq ⌊ 2 n / p^{k} ⌋ \leq 2 ⌊ n / p^{k} ⌋ + 1$ . Therefore $v_{p} (\binom{2 n}{n})$ is at most the number of positive integers $k$ with $p^{k} \leq 2 n$ . If $p^{k} \leq 2 n$ , then $k \log p \leq \log (2 n)$ , so $k \leq \log (2 n) / \log p$ . This proves $v_{p} (\binom{2 n}{n}) \leq \frac{\log (2 n)}{\log p} .$

4.1step 1.1step 2.1step 3.1step 3.2∎

Steps 1.1, 2.1, 3.1, and 3.2 prove all claims.

Depends on

Used by

Factoring a central binomial coefficient to detect interval primes Example
Bertrand's postulate Theorem
Chebyshev's theta function has linear lower and upper bounds Theorem

Dependency tree · two levels

57 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 2 (standard reference, not scraped)