Valuation of Factorials

How many zeros does a colossal number like 100! end with? This simple-sounding question opens a door to a profound area of number theory: the valuation of factorials. At its core, it's a problem of counting the prime factors within a massive product, a task that naive approaches fail to solve correctly. This article bridges that knowledge gap by introducing a powerful and elegant method for determining the exact power of any prime within a factorial. In the upcoming chapters, we will first explore the "Principles and Mechanisms", unveiling Adrien-Marie Legendre's classic formula and a surprising alternative involving the digits of a number. Then, under "Applications and Interdisciplinary Connections", we will see how this single tool unlocks deep truths in combinatorics, abstract algebra, and even a strange form of calculus, demonstrating its fundamental importance across mathematics.

Imagine you have a colossal number, say, the factorial of 100, written as $100!$. This is the product of all integers from 1 to 100. If you were to write this number out, it would have 158 digits. A simple question we might ask is: how many zeros does this number end with? This is the same as asking: what is the highest power of 10 that divides $100!$? Since $10 = 2 \times 5$, this question boils down to finding the number of factors of 2 and 5 in the prime factorization of $100!$. The number of zeros will be limited by the prime that appears fewer times. In this journey, we will uncover a surprisingly elegant and powerful tool to answer this and far more general questions, a tool that connects the multiplicative world of divisibility to the simple act of writing numbers down.

Let's try to find the exponent of the prime $p=5$ in the prime factorization of $100!$. This exponent is called the ​​$p$-adic valuation​​ of $100!$, denoted $v_5(100!)$. A natural first guess might be to simply count how many numbers from 1 to 100 are multiples of 5. These are $5, 10, 15, \dots, 100$. There are $\lfloor \frac{100}{5} \rfloor = 20$ such numbers. So, is the answer 20?

Let's test this logic on a smaller scale. What is $v_3(9!)$? The multiples of 3 up to 9 are 3, 6, and 9. There are $\lfloor \frac{9}{3} \rfloor = 3$ of them. So, our guess would be 3. But let's look at the prime factorization of $9!$: $9! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 = 362,880 = 2^7 \times 3^4 \times 5^1 \times 7^1$. The actual exponent of 3 is 4, not 3! Our first guess was wrong.

The flaw in our reasoning is a subtle but crucial one. We are not trying to count the number of integers that are divisible by 3. We are trying to count the total number of factors of 3. The numbers 3 and 6 each contribute one factor of 3. But the number 9 is different; it's $3^2$, so it contributes two factors of 3. Our initial method only counted it once. We confused counting distinct items with summing their properties.

To fix this, we must be more systematic. The fear of "double counting" was a misapplication of the concept. Here, numbers divisible by higher powers of a prime must be counted multiple times because they contribute multiple factors.

The correct procedure, first formulated by the great mathematician Adrien-Marie Legendre, is as follows:

1. First, count all multiples of $p$ up to $n$. There are $\lfloor n/p \rfloor$ of them. Each contributes at least one factor of $p$.
2. Next, count all multiples of $p^2$. There are $\lfloor n/p^2 \rfloor$ of them. Each of these contributes at least two factors of $p$. Since we already accounted for their first factor in step 1, we now add this second contribution.
3. Then, count all multiples of $p^3$. There are $\lfloor n/p^3 \rfloor$ of them. We've already accounted for two of their factors (one in the $p$ count, one in the $p^2$ count), so we add this third contribution.
4. We continue this for all powers of $p$ less than or equal to $n$.

This process ensures that a number like $p^k$ is counted exactly $k$ times—once in the $\lfloor n/p \rfloor$ tally, once in the $\lfloor n/p^2 \rfloor$ tally, ..., and once in the $\lfloor n/p^k \rfloor$ tally. This correctly captures its contribution of $k$ factors. This leads to the famous ​​Legendre's formula​​:

The sum is technically infinite, but the terms become zero as soon as $p^k > n$. Let's try our examples again. For $v_3(9!)$: $v_3(9!) = \left\lfloor \frac{9}{3} \right\rfloor + \left\lfloor \frac{9}{9} \right\rfloor + \left\lfloor \frac{9}{27} \right\rfloor + \dots = 3 + 1 + 0 = 4$ This is the correct answer! Now, for our original problem of trailing zeros in $100!$: $v_5(100!) = \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{25} \right\rfloor + \left\lfloor \frac{100}{125} \right\rfloor + \dots = 20 + 4 + 0 = 24$ And for the prime 2: $v_2(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97$ The number of factors of $10=2 \times 5$ is limited by the smaller exponent, which is 24. So, $100!$ ends in exactly 24 zeros. The rounding down in the floor function is crucial. For instance, in calculating $v_5(24!)$, we find $v_5(24!) = \lfloor 24/5 \rfloor = 4$. The value stays at 4 until we reach $n=25$, where it jumps.

Let's think of $v_p(n!)$ as a function of $n$. How does it behave? It's a non-decreasing function, since we are always adding non-negative terms as $n$ increases. Specifically, the change from $n-1$ to $n$ is simply: $v_p(n!) - v_p((n-1)!) = v_p\left(\frac{n!}{(n-1)!}\right) = v_p(n)$ This gives us a wonderful picture of our function. It is a ​​step function​​. It stays flat for a while, and then it jumps. When does it jump? It jumps precisely when $n$ is a multiple of $p$, because that's when $v_p(n)$ is greater than 0. And what is the height of the jump? The height of the jump at $n$ is exactly $v_p(n)$. So at $n=p$, it jumps by 1. At $n=2p$, it jumps by 1. But at $n=p^2$, it jumps by 2!

This step-like behavior reveals a hidden rhythm. The function $v_p(n!)$ remains constant for all integers between two consecutive multiples of $p$. For example, if we find that $v_p((kp)!) = m$, then for all integers $j$ from $1$ to $p-1$, the number $kp+j$ is not divisible by $p$, so $v_p(kp+j)=0$. This means the valuation of the factorial stays constant: $v_p((kp+j)!) = m$. The value only changes again at the next multiple of $p$, namely $p(k+1)$. Thus, the set of all integers $n$ for which $v_p(n!)$ has a specific value $m$ is always an interval of length $p$.

You might think that this clever counting trick is the end of the story. But mathematics has a way of revealing astonishing connections in the most unexpected places. It turns out there is a completely different-looking formula for $v_p(n!)$ that has nothing to do with floor functions or infinite sums. Instead, it has to do with how you write the number $n$ in base $p$.

Let $s_p(n)$ be the sum of the digits of $n$ when written in base $p$. For example, if $p=3$ and $n=17$, we write $17 = 1 \cdot 3^2 + 2 \cdot 3^1 + 2 \cdot 3^0$, so $17$ is $(122)_3$ in base 3. The sum of its digits is $s_3(17) = 1+2+2=5$. The second formula for the $p$-adic valuation is:

This is a piece of pure magic. How on earth could a question about the multiplicative structure of a factorial (divisibility) be answered by a simple additive property of its digits in a different number system? Let's check it for $v_3(9!)$. Here $n=9$, $p=3$. In base 3, $9$ is $(100)_3$. The sum of digits is $s_3(9) = 1+0+0=1$. The formula gives: $v_3(9!) = \frac{9 - s_3(9)}{3-1} = \frac{9-1}{2} = 4$ It works! And for $v_5(100!)$, we have $100 = 4 \cdot 5^2 + 0 \cdot 5^1 + 0 \cdot 5^0$, so $100 = (400)_5$. Then $s_5(100)=4$. The formula gives: $v_5(100!) = \frac{100 - s_5(100)}{5-1} = \frac{100-4}{4} = \frac{96}{4} = 24$ It works again. The two formulas, one involving a sum of floor functions and the other involving digits, are one and the same. The proof of their equivalence is itself a thing of beauty; by writing $n$ in its base-$p$ expansion and substituting it into the floor-sum formula, the expression can be algebraically rearranged, term by term, until it transforms precisely into the digit-sum formula. It's a testament to the deep, unifying structure of numbers.

The digit-sum formula offers a new perspective. Let's return to our functional view and ask what happens when we go from $n$ to $n+1$. The change in valuation is $v_p(n+1)$. Using the digit-sum formula, this change is: $v_p((n+1)!) - v_p(n!) = \frac{(n+1) - s_p(n+1)}{p-1} - \frac{n - s_p(n)}{p-1} = \frac{1 - (s_p(n+1) - s_p(n))}{p-1}$ So, $v_p(n+1)$ is determined by the change in the sum of digits! What determines this change? It's the number of ​​carries​​ that occur when you add 1 to $n$ in base $p$. If the last digit of $n$ is not $p-1$, adding 1 just increments that digit, and $s_p(n+1) - s_p(n) = 1$. But if the last $t$ digits of $n$ are all $p-1$, adding 1 creates a cascade of $t$ carries. These $t$ digits become 0, and the $(t+1)$-th digit is incremented. This leads to a beautiful identity: $s_p(n+1) - s_p(n) = 1 - (p-1)t$ where $t$ is the number of carries. But what is $t$? It's exactly the number of factors of $p$ in $n+1$, which is $v_p(n+1)$! So, $s_p(n+1) - s_p(n) = 1 - (p-1)v_p(n+1)$. Plugging this back into our expression for the change in valuation gives: $\frac{1 - (1 - (p-1)v_p(n+1))}{p-1} = \frac{(p-1)v_p(n+1)}{p-1} = v_p(n+1)$ Everything is perfectly consistent. The arithmetic of carries in base $p$ is inextricably linked to the prime divisibility of factorials.

A crucial question arises: what is so special about the base $p$ being a prime number? Can we create an analogous formula for a composite base, like $b=10$?

Let's try to mimic Legendre's formula for $b=6$ and find $v_6(10!)$. The proposed formula would be $\sum \lfloor 10/6^k \rfloor = \lfloor 10/6 \rfloor = 1$. But this is wrong. We know $v_2(10!) = 8$ and $v_3(10!) = 4$. Since $6=2 \times 3$, an integer is divisible by $6$ if it is divisible by both 2 and 3. In $10!$, we have eight factors of 2 and four factors of 3. We can form at most four pairs of (2, 3), so we can form four factors of 6. Thus, $v_6(10!) = 4$.

The simple counting formula fails for composite bases because the valuation function $v_b$ is not additive. For a prime $p$, we have the essential property $v_p(xy) = v_p(x) + v_p(y)$, which lets us convert the valuation of a product ($n!$) into a sum of valuations. For a composite $b$, this fails spectacularly. For instance, $v_6(2)=0$ and $v_6(3)=0$, but $v_6(2 \times 3) = v_6(6) = 1$. The additivity property is the exclusive domain of prime numbers.

To handle a composite base $b$ with prime factorization $b = p_1^{e_1} p_2^{e_2} \cdots$, the true exponent $v_b(n!)$ is determined by the "bottleneck" prime. For each prime factor $p_i$, we have $v_{p_i}(n!)$ available factors. Since we need $e_i$ of them to make one factor of $p_i^{e_i}$, the number of $b$'s we can form is limited by the minimum of these ratios: $v_b(n!) = \min_{i} \left\lfloor \frac{v_{p_i}(n!)}{e_i} \right\rfloor$ This highlights the fundamental role of primes as the indivisible, multiplicative building blocks of integers.

Legendre's formula is a powerful tool for the product $n!$. What if we consider a sum, like $n!+\ell$? The beautiful, predictable world of factorials suddenly becomes much wilder. There is no simple counting formula for the valuation of a sum. The behavior is governed by the ​​non-archimedean property​​ of valuations: $v_p(x+y) \ge \min\{v_p(x), v_p(y)\}$ Equality holds if the valuations are different. For example, for $n \ge p$, we have $v_p(n!) \ge 1$. For any integer $\ell$ between 1 and $p-1$, we have $v_p(\ell)=0$. Because the valuations are different, we get $v_p(n!+\ell) = \min\{v_p(n!), 0\} = 0$.

But if the valuations are equal, $v_p(x)=v_p(y)$, anything can happen! The valuation of the sum depends on whether the leading terms cancel out modulo $p$. Consider $p=5$ and $n=5$. We have $5! = 120$. The valuation is $v_5(120) = v_5(24 \times 5) = 1$. Now let's add $\ell=5$. Here, $v_5(5)=1$, so the valuations are equal. The sum is $120+5=125=5^3$. The valuation has jumped to $v_5(125)=3$. Compare this with adding $\ell=10$, where $v_5(10)=1$. The sum is $120+10=130$, and $v_5(130)=1$. The valuation of a sum is a delicate affair, sensitive to the specific numbers involved, unlike the robust, universal formula for products.

The study of the valuation of factorials, born from a simple question, has led us to deep insights into the structure of numbers. This tool is not just a mathematical curiosity; it is the key that unlocks profound theorems in number theory and combinatorics, such as predicting the divisibility of binomial coefficients $\binom{n}{k}$ by primes. For example, using the same base-p digit logic, one can determine that $\binom{123}{56} \equiv \binom{2}{1}\binom{3}{1}\binom{4}{0} \equiv 6 \pmod 7$, because $123=(234)_7$ and $56=(110)_7$. The simple act of counting prime factors has given us a lens to see the hidden architecture of the integers.

Now that we have acquainted ourselves with the machinery of Legendre's formula and the concept of $p$-adic valuation, you might be wondering, "What is all this for?" It is a fair question. A formula, no matter how elegant, is like a beautifully crafted key. Its true value is not in its own form, but in the doors it unlocks. And Legendre's formula, as it turns out, is a master key that opens doors to some of the most fascinating rooms in the house of mathematics. It reveals deep connections between counting, number structure, abstract algebra, and even a strange and wonderful form of calculus. Let's take a tour.

We learn in school that the binomial coefficient $\binom{n}{k}$ counts the number of ways to choose $k$ items from a set of $n$. Its definition, $\frac{n!}{k!(n-k)!}$, involves a fraction, yet the answer is always a whole number. Why? You might say it's because of the combinatorial interpretation, which is true, but that feels a little like magic. Can we prove it algebraically, from the fraction itself?

Legendre's formula gives us a direct and powerful way. To show that $\binom{n}{k}$ is an integer, we just need to show that for any prime $p$, the total power of $p$ in the numerator's prime factorization ($n!$) is greater than or equal to the total power of $p$ in the denominator's factorization ($k!(n-k)!$). In our language, this means we must show that $v_p(\binom{n}{k}) = v_p(n!) - v_p(k!) - v_p((n-k)!)$ is always non-negative.

Using Legendre's formula, this becomes:

A fundamental property of the floor function is that for any two real numbers $x$ and $y$, $\lfloor x+y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$. If we let $x = k/p^i$ and $y = (n-k)/p^i$, we see that each term in our sum, $\lfloor n/p^i \rfloor - \lfloor k/p^i \rfloor - \lfloor (n-k)/p^i \rfloor$, must be either $0$ or $1$. Since all terms are non-negative, their sum, $v_p(\binom{n}{k})$, must also be non-negative. And there it is—no magic, just pure arithmetic. The fraction always simplifies to an integer.

This is just the beginning. The formula tells us not just that the valuation is non-negative, but exactly what it is. And here lies one of the most beautiful results in elementary number theory, Kummer's Theorem. It states that the value of $v_p(\binom{n}{k})$ is simply the number of 'carries' you perform when adding the numbers $k$ and $n-k$ in base $p$.

Think about that! An abstract question about prime divisibility of a factorial ratio is answered by doing grade-school arithmetic in a different number base. For instance, to find the power of 2 dividing the central binomial coefficient $\binom{62}{31}$, you could calculate the valuations of $62!$ and $31!$, or you could simply add $31$ and $31$ in binary and count the carries. It's a stunning link between the abstract world of number theory and the concrete act of calculation.

This connection, as explored in problems like, gives us a profound insight. When is $\binom{n}{k}$ not divisible by $p$? This is equivalent to asking when $v_p(\binom{n}{k}) = 0$. By Kummer's Theorem, this happens when there are zero carries in the base-$p$ addition of $k$ and $n-k$. This "no-carries" condition means that for each digit position, the sum of the digits of $k$ and $n-k$ must be less than $p$. This, in turn, is only possible if for every digit position $i$, the base-$p$ digit $k_i$ is less than or equal to the corresponding digit $n_i$. This powerful result, a corollary of Kummer's theorem, is part of a broader picture painted by Lucas's Theorem, which compares the values of $\binom{n}{k}$ and the product of $\binom{n_i}{k_i}$ modulo $p$. Valuation tells us about divisibility (a 'zero'), while modular arithmetic tells us about the remainder (a 'digit').

So far, we've looked at individual coefficients. What happens if we zoom out and look at a whole family of them? For a fixed $n$, what can we say about the divisibility of $\binom{n}{k}$ on average, as $k$ varies from $0$ to $n$? This question pushes us from number theory into the realm of probability and statistics.

We can ask for the expected value of the $p$-adic valuation, $E[v_p(\binom{n}{K})]$, where $K$ is a random variable chosen uniformly from $\{0, 1, \dots, n\}$. Using Legendre's formula, one can derive a precise, albeit complex, closed-form expression for this expectation. Similarly, one can pose more structured questions, such as finding the average $p$-adic valuation for the family of coefficients $\binom{p^m}{k}$. The ability to answer such questions demonstrates that the properties of prime divisibility are not entirely random; they follow deep statistical patterns, and Legendre's formula is our tool to uncover them.

The $p$-adic valuation is more than just a counting device; it is a fundamental measuring tool that can define entire algebraic structures. Consider the set of all rational numbers whose denominators are not divisible by a prime $p$. This set, denoted $\mathbb{Z}_{(p)}$, forms a special type of ring called a "localization" of the integers.

Remarkably, this ring is a Euclidean domain, a very well-behaved algebraic structure where we have a division algorithm, much like with ordinary integers. What is the "size" function that makes this work? It is precisely the $p$-adic valuation, $v_p$. An element is "small" in this world if it is divisible by a high power of $p$. This means that within $\mathbb{Z}_{(p)}$, the ideals (the most important substructures of a ring) take on a very simple form: they are all generated by powers of $p$. Finding a generator for an ideal generated by several elements simply reduces to finding the minimum of their $p$-adic valuations. Our factorial valuation formula, therefore, becomes a tool for navigating the structure of these abstract algebraic rings.

Perhaps the most profound application of the valuation of factorials is in the field of $p$-adic analysis. By using the $p$-adic absolute value $|x|_p = p^{-v_p(x)}$, we can complete the rational numbers to form the field of $p$-adic numbers, $\mathbb{Q}_p$. This is a complete metric space, just like the real numbers, but its geometry is bizarre. Here, the triangle inequality is replaced by the stronger "ultrametric" inequality: $|x+y|_p \le \max(|x|_p, |y|_p)$. One consequence is that in the $p$-adic world, all triangles are isosceles!

In this strange new world, we can still ask about calculus—about functions defined by power series, like the exponential function $\exp(x) = \sum_{n=0}^\infty \frac{x^n}{n!}$. In the real numbers, determining the radius of convergence requires careful tests. In $\mathbb{Q}_p$, the rule is much simpler: a series converges if and only if its terms go to zero.

So, for the $p$-adic exponential series to converge, we need $|x^n/n!|_p \to 0$ as $n \to \infty$. This is equivalent to needing $v_p(x^n/n!) \to \infty$, or $n v_p(x) - v_p(n!) \to \infty$. To find the condition on $v_p(x)$, we must understand the growth rate of $v_p(n!)$. And this is where Legendre's formula comes to the forefront. A direct consequence of the formula is that for large $n$, $v_p(n!) \approx \frac{n}{p-1}$. The convergence condition for $\exp(x)$ thus becomes $v_p(x) > \frac{1}{p-1}$.

This single inequality, born from Legendre's work, has startling consequences.

• For any prime $p \ge 3$, we have $p-1 > 1$, so the condition $v_p(x) > \frac{1}{p-1}$ is satisfied if $v_p(x) \ge 1$. This means $\exp(x)$ converges for any $x$ that is a multiple of $p$.
• However, for $p=2$, the condition becomes $v_2(x) > \frac{1}{2-1} = 1$. Since the valuation must be an integer, this means we need $v_2(x) \ge 2$. The 2-adic exponential function converges only for multiples of 4, not for all multiples of 2!

This subtle but crucial difference between the prime 2 and all other primes is a direct consequence of the growth rate of the valuation of factorials. Our simple counting formula dictates the very domain of existence for one of the most fundamental functions in analysis. This same logic helps determine the convergence for other series, like those involving powers of valuations themselves or the $p$-adic logarithm, whose convergence behavior is different because its denominators involve $v_p(n)$, which grows much more slowly than $v_p(n!)$.

Once convergence is established, we can perform calculations that would seem like nonsense in the real world, such as computing $\exp(p)$ modulo $p^2$ and finding it is a well-defined integer in $\mathbb{Z}_p$.

From proving that a simple choice is an integer, to defining the rules of a new calculus, Legendre's formula is a thread that weaves together disparate fields of mathematics. It reminds us that sometimes, the most profound insights are found by simply asking, with persistent curiosity, "How many times does this prime divide that factorial?" The answers can, and do, change the way we see the universe of numbers.