janmr blog

Factorial numbers, $n! = 1 \cdot 2 \cdots n$, grow very fast with $n$. In fact, $n! \sim \sqrt{2 \pi n} (n/e)^n$ according to Stirling's approximation. The prime factors of a factorial number, however, are all relatively small, and the complete factorization of $n!$ is quite easy to obtain.

We will make use of the following fundamental theorem:

$p \mid a b$ for a prime $p$, then $p \mid a$ or $p \mid b$.

(Here, $p \mid a$ means that $p$ divides $a$.) This is called Euclid's First Theorem or Euclid's Lemma. For most, it is intuitively clear, but a proof can be found in, e.g., Hardy and Wright: An Introduction to the Theory of Numbers.

An application of this theorem to factorial numbers is that if a prime $p$ is a divisor of $n!$ then $p$ must be a divisor of at least one of the numbers $1, 2, \ldots, n$. This immediately implies

Every prime factor of $n!$ is less than or equal to $n$.

Conversely, every prime number between 2 and $n$ must be a prime factor of $n!$.

Let us introduce the notation $d_a(b)$ as the number of times $a$ divides into $b$. Put more precisely, $d_a(b) = k$ if and only if $b/a^k$ is an integer while $b/a^{k+1}$ is not.

We now seek to determine $d_p(n!)$ for all primes $p \leq n$. From Euclid's First Theorem and the Fundamental Theorem of Arithmetic follows:

The trick here is not to consider the right-hand side term by term, but rather as a whole. Let us take

and $p=3$ as an example. How many of the numbers 1, 2, …, 42 are divisible by 3? Exactly $\lfloor 42/3 \rfloor = 14$ of them. But this is not the total count, because some of them are divisible by 3 multiple times. So how many are divisible by $3^2$? $\lfloor 42/3^2 \rfloor = 4$ of them. Similarly, $\lfloor 42/3^3 \rfloor = 1$. And $\lfloor 42/3^4 \rfloor = \lfloor 42/3^5 \rfloor = \ldots = 0$. So we have

This procedure is easily generalized and we have

This identity was found by the french mathematician Adrien-Marie Legendre (see also Proofs From The Book, page 8, where it is called Legendre's Theorem).

Doing this for all primes in our example, we get

Notice how the exponents do not increase as the prime numbers increase. This is true in general. Assume that $p$ and $q$ are both primes and $p < q$. Then $\log_p(n) \geq \log_q(n)$ and $n/p^k \geq n/q^k$ for all positive integers $k$. Using this in equation (1) we get

and thus

What about $d_k(n!)$ for composite numbers $k$? Given the factorization of both $n!$ and $k$, this is easy to compute. But if, e.g., the multiplicity of all prime factors of $k$ are the same, then the relation (2) can be used. Consider $d_{10}(m)$ for a positive integer $m$. Since $10 = 2 \cdot 5$ then

But if $m=n!$ then we can use (2) and we have

For instance,

so there are 9 trailing zeros in the decimal representation of 42!.