Legendre's formula

From Wikipedia, the free encyclopedia
  (Redirected from De Polignac's formula)
Jump to: navigation, search

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 for 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 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 formula 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 .

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]

External links[edit]