 Legendre's formula

For a nonnegative integer $n$ and a prime number $p$, the Legendre formula computes the prime exponent in a factorial without forming that huge product:Here $\lfloor x\rfloor$ is the floor function. The sum is finite: every term with $p^j>n$ is zero. When $n=0$, all terms vanish, agreeing with $0!=1$ and $v_p(1)=0$. The prime number hypothesis matters: a composite number does not give the same P-adic valuation or additive prime exponent. For example, the floor sum with $n=6,p=4$ is one, whereas $4^2$ divides $6!=720$.

Why count multiples repeatedly? Each multiple of $p$ in $1,\dots ,n$ contributes one factor of $p$; each multiple of $p^2$ contributes another; and so on. A factor $m$ with P-adic valuation $a$ occurs in exactly the first $a$ counts. Adding those contributions proves the formula.^[ref]

For the original example $n=50,p=3$,The five multiples $9,18,27,36,45$ each contribute a second factor of three. The factor $27$ contributes a third, so it appears in all three rows. Equivalently, among $1,\dots ,50$ there are eleven factors of P-adic valuation one, four of valuation two, and one of valuation three: $11+2\cdot 4+3\cdot 1=22$. Thus $3^{22}$ divides $50!$, while $3^{23}$ does not.

Repeated Euclidean division provides a practical evaluation: replace $q$ by $\lfloor q/p\rfloor$, starting from $q=n$, and add each new quotient until it is zero. This uses only the successive quotients $16,5,1,0$ for the example. The same calculation handles divisibility of binomial coefficients, where the P-adic valuations of the denominator factorials are subtracted.

Legendre's formula, also known as Legendre's theorems or Legendre's formula for finding the exponent of a prime \( p \) in the factorization of \( n! \) (n factorial), provides a way to determine how many times a prime number divides \( n! \).