In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!. It is named after Adrien-Marie Legendre. It is also sometimes known as de Polignac's formula, after Alphonse de Polignac.

Statement

edit

For any prime number p and any positive integer n, let   be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then

 

where   is the floor function. 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  , one has  . This reduces the infinite sum above to

 

where  .

Example

edit

For n = 6, one has  . The exponents   and   can be computed by Legendre's formula as follows:

 

Proof

edit

Since   is the product of the integers 1 through n, we obtain at least one factor of p in   for each multiple of p in  , of which there are  . Each multiple of   contributes an additional factor of p, each multiple of   contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for  .

Alternate form

edit

One may also reformulate Legendre's formula in terms of the base-p expansion of n. Let   denote the sum of the digits in the base-p expansion of n; then

 

For example, writing n = 6 in binary as 610 = 1102, we have that   and so

 

Similarly, writing 6 in ternary as 610 = 203, we have that   and so

 

Proof

edit

Write   in base p. Then  , and therefore

 

Applications

edit

Legendre's formula can be used to prove Kummer's theorem. As one special case, it can be used to prove that if n is a positive integer then 4 divides   if and only if n is not a power of 2.

It follows from Legendre's formula that the p-adic exponential function has radius of convergence  .

References

edit
  • Legendre, A. M. (1830), Théorie des Nombres, Paris: Firmin Didot Frères
  • Moll, Victor H. (2012), Numbers and Functions, American Mathematical Society, ISBN 978-0821887950, MR 2963308, page 77
  • Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.
edit