Misplaced Pages

Legendre's formula

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from De Polignac's formula) Number theory expression

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

For any prime number p and any positive integer n, let ν p ( n ) {\displaystyle \nu _{p}(n)} be the exponent of the largest power of p that divides n (that is, the p-adic valuation of n). Then

ν p ( n ! ) = ∑ i = 1 ∞ ⌊ n p i ⌋ , {\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ,}

where ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } 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 p i > n {\displaystyle p^{i}>n} , one has ⌊ n p i ⌋ = 0 {\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0} . This reduces the infinite sum above to

ν p ( n ! ) = ∑ i = 1 L ⌊ n p i ⌋ , {\displaystyle \nu _{p}(n!)=\sum _{i=1}^{L}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \,,}

where L = ⌊ log p ⁡ n ⌋ {\displaystyle L=\lfloor \log _{p}n\rfloor } .

Example

For n = 6, one has 6 ! = 720 = 2 4 ⋅ 3 2 ⋅ 5 1 {\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}} . The exponents ν 2 ( 6 ! ) = 4 , ν 3 ( 6 ! ) = 2 {\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2} and ν 5 ( 6 ! ) = 1 {\displaystyle \nu _{5}(6!)=1} can be computed by Legendre's formula as follows:

ν 2 ( 6 ! ) = ∑ i = 1 ∞ ⌊ 6 2 i ⌋ = ⌊ 6 2 ⌋ + ⌊ 6 4 ⌋ = 3 + 1 = 4 , ν 3 ( 6 ! ) = ∑ i = 1 ∞ ⌊ 6 3 i ⌋ = ⌊ 6 3 ⌋ = 2 , ν 5 ( 6 ! ) = ∑ i = 1 ∞ ⌊ 6 5 i ⌋ = ⌊ 6 5 ⌋ = 1. {\displaystyle {\begin{aligned}\nu _{2}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{2^{i}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor =3+1=4,\\\nu _{3}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{3^{i}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2,\\\nu _{5}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{5^{i}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1.\end{aligned}}}

Proof

Since n ! {\displaystyle n!} is the product of the integers 1 through n, we obtain at least one factor of p in n ! {\displaystyle n!} for each multiple of p in { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} , of which there are ⌊ n p ⌋ {\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor } . Each multiple of p 2 {\displaystyle p^{2}} contributes an additional factor of p, each multiple of p 3 {\displaystyle p^{3}} contributes yet another factor of p, etc. Adding up the number of these factors gives the infinite sum for ν p ( n ! ) {\displaystyle \nu _{p}(n!)} .

Alternate form

One may also reformulate Legendre's formula in terms of the base-p expansion of n. Let s p ( n ) {\displaystyle s_{p}(n)} denote the sum of the digits in the base-p expansion of n; then

ν p ( n ! ) = n − s p ( n ) p − 1 . {\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.}

For example, writing n = 6 in binary as 610 = 1102, we have that s 2 ( 6 ) = 1 + 1 + 0 = 2 {\displaystyle s_{2}(6)=1+1+0=2} and so

ν 2 ( 6 ! ) = 6 − 2 2 − 1 = 4. {\displaystyle \nu _{2}(6!)={\frac {6-2}{2-1}}=4.}

Similarly, writing 6 in ternary as 610 = 203, we have that s 3 ( 6 ) = 2 + 0 = 2 {\displaystyle s_{3}(6)=2+0=2} and so

ν 3 ( 6 ! ) = 6 − 2 3 − 1 = 2. {\displaystyle \nu _{3}(6!)={\frac {6-2}{3-1}}=2.}

Proof

Write n = n ℓ p ℓ + ⋯ + n 1 p + n 0 {\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}} in base p. Then ⌊ n p i ⌋ = n ℓ p ℓ − i + ⋯ + n i + 1 p + n i {\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}} , and therefore

ν p ( n ! ) = ∑ i = 1 ℓ ⌊ n p i ⌋ = ∑ i = 1 ℓ ( n ℓ p ℓ − i + ⋯ + n i + 1 p + n i ) = ∑ i = 1 ℓ ∑ j = i ℓ n j p j − i = ∑ j = 1 ℓ ∑ i = 1 j n j p j − i = ∑ j = 1 ℓ n j ⋅ p j − 1 p − 1 = ∑ j = 0 ℓ n j ⋅ p j − 1 p − 1 = 1 p − 1 ∑ j = 0 ℓ ( n j p j − n j ) = 1 p − 1 ( n − s p ( n ) ) . {\displaystyle {\begin{aligned}\nu _{p}(n!)&=\sum _{i=1}^{\ell }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \\&=\sum _{i=1}^{\ell }\left(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}\right)\\&=\sum _{i=1}^{\ell }\sum _{j=i}^{\ell }n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }\sum _{i=1}^{j}n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&=\sum _{j=0}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\sum _{j=0}^{\ell }\left(n_{j}p^{j}-n_{j}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right).\end{aligned}}}

Applications

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 ( 2 n n ) {\displaystyle {\binom {2n}{n}}} 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 p − 1 / ( p − 1 ) {\displaystyle p^{-1/(p-1)}} .

References

External links

Category: