janmr blog

Prime Factors of Factorial Numbers

Factorial numbers, , grow very fast with . In fact, according to Stirling's approximation. The prime factors of a factorial number, however, are all relatively small, and the complete factorization of is quite easy to obtain.

We will make use of the following fundamental theorem:

for a prime , then or .

(Here, means that divides .) This is called Euclid's First Theorem or [Euclid's Lemma](http://en.wikipedia.org/wiki/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 is a divisor of then must be a divisor of at least one of the numbers . This immediately implies

Every prime factor of is less than or equal to .

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

Let us introduce the notation as the number of times divides into . Put more precisely, if and only if is an integer while is not.

We now seek to determine for all primes . 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

42! = 1405006117752879898543142606244511569936384000000000

and as an example. How many of the numbers 1, 2, …, 42 are divisible by 3? Exactly 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 ? of them. Similarly, . And . So we have

This procedure is easily generalized and we have


This identity was found by the french mathematician Adrien-Marie Legendre (see also Aigner and Ziegler: 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 and are both primes and . Then and for all positive integers . Using this in equation (1) we get

for primes , with

and thus

What about for composite numbers ? Given the factorization of both and , this is easy to compute. But if, e.g., the multiplicity of all prime factors of are the same, then the relation (2) can be used. Consider for a positive integer . Since then

But if then we can use (2) and we have

For instance,


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