Legendre’s Formula: A Mathematical Breakthrough
Area of Math: Number Theory.
Legendre’s formula (also called De Polignac’s formula) is a remarkable achievement in mathematics that has stood the test of time. First introduced by the French mathematician Adrien-Marie Legendre in the late 18th century, it remains a widely-used tool in number theory and calculus.
This formula is used to calculate the ‘p-adic valuation’ of the factorial, which means, the exponent of the greatest power of a prime p that divides n!, and its discovery had a significant impact on the study of prime numbers. In this article, we will explore the Legendre’s formula as we delve into its intricacies and uncover its significance in the world of mathematics.
The formula
Legendre’s formula is an expression for the exponent of the greatest power of a prime p that divides n!, the factorial. For any prime number p and any positive integer n, let v_p(n) be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then Legendre’s formula states that:
While the sum on the right side is an infinite sum, for any particular values of n and p it has only finitely many nonzero terms: for every i large enough that p^i>n, one has
This reduces the infinite sum above to a finite sum.
For example, for n = 29 and p = 2, we have:
This means that given an integer 29 and a prime number 2, the largest power of 2 such that it divides 29! is 2²⁵.
To prove Legendre’s formula, note that n! is the product of the integers 1 through n. We obtain at least one factor of p in n! for each multiple of p in {1,2,…,n}, of which there are
Each multiple of p² contributes an additional factor of p, each multiple of p³ contributes yet another factor of p, and so on. Adding up the number of these factors gives the infinite sum on the right side of Legendre’s formula.
Proof
Intuition: Consider n = pk + r for some k. Then n! = (pk + r)! is surely divisible by p at least k times. But this has counted each multiple of p less than n only once. But if n > p² then we have to count twice for each multiple of p² less than n and so on.
___
Shorter Proof: p divides n! for every multiple of p less than n. There are
such multiples.
Then it divides n! once more for every multiple of p² less than n. There are
such divisors etc. Let p^d | n! and d be the highest exponent for which it is true. Then
where the sum in fact has only a finite number of terms. (Since p can divide n only finitely times.)
___
Proof: To prove Legendre’s formula, we need to show that the exponent of a prime p in the prime factorization of n! is the sum of the exponents of p in the prime factorization of each of the numbers 1,2,…,n. For any positive integer n and prime number p, let v_p(n) be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then Legendre’s formula states that:
To prove this formula, we can observe that the number of multiples of p among the numbers 1,2,…,n is
Each multiple of p² contributes an additional factor of p, each multiple of p³ contributes yet another factor of p, and so on. Adding up the number of these factors gives the infinite sum on the right side of Legendre’s formula.
Another way to prove Legendre’s formula is to use the fact that the p-adic valuation of a product is the sum of the p-adic valuations of the factors. Since n! = 1⋅2⋅…⋅n, the exponent of p in the prime factorization of n! is the sum of the exponents of p in the prime factorization of each of the numbers 1,2,…,n. This gives the same formula as above.
Therefore, Legendre’s formula is proved by showing that the exponent of a prime p in the prime factorization of n! is the sum of the exponents of p in the prime factorization of each of the numbers 1,2,…,n.
Proof by induction
To prove Legendre’s formula, we need to show that the exponent of a prime p in the prime factorization of n! is the sum of the exponents of p in the prime factorization of each of the numbers 1,2,…,n. For any positive integer n and prime number p, let v_p(n) be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then Legendre’s formula states that:
To prove this formula, we can observe that the number of multiples of p among the numbers 1,2,…,n is
Each multiple of p² contributes an additional factor of p, each multiple of p³ contributes yet another factor of p, and so on. Adding up the number of these factors gives the infinite sum on the right side of Legendre’s formula. To make this argument rigorous, we can use mathematical induction.
The base case is n = 1, where the formula holds trivially.
For the induction step, assume that the formula holds for some positive integer n. We need to show that it also holds for n+1. Let
Then the number of multiples of p among the numbers 1,2,…,n+1 is k+1 if n+1 is a multiple of p, and k otherwise.
By the induction hypothesis, the exponent of p in the prime factorization of n! is
If n+1 is not a multiple of p, then the exponent of p in the prime factorization of (n+1)! is the same as the exponent of p in the prime factorization of n!. If n+1 is a multiple of p, then the exponent of p in the prime factorization of (n+1)! is one more than the exponent of p in the prime factorization of n!. Therefore, the exponent of p in the prime factorization of (n+1)! is:
This completes the induction step, and hence the proof of the Legendre’s formula.
Application
Legendre’s formula is useful in number theory and has many applications, including in the proof of the Prime Number Theorem (PNT). Legendre’s formula is actively used for prime factorization of binomial coefficients and Catalan numbers. The formula can also be used to compute the prime factorization of factorials by computing the exponents of each prime factor.
In conclusion, Legendre’s formula is a remarkable mathematical achievement that has stood the test of time. It has proven to be an invaluable tool in number theory and has inspired many other mathematical discoveries. From its humble beginnings as a formula for approximating prime numbers, it has become a cornerstone of modern mathematics. Whether you’re a mathematician, a student, or simply someone with an appreciation for the beauty of numbers, Legendre’s formula is a testament to the power of human curiosity and ingenuity.
References
Preliminaries Chapter, Section 0.2, Exercise 8 in Abstract Algebra, 3rd Edition by David S. Dummit, Richard M. Foote.
