# De Polignac's Formula

Jump to: navigation, search

## Theorem

Let $n!$ be the factorial of $n$.

Let $p$ be a prime number.

Then $p^\mu$ is a divisor of $n!$, and $p^{\mu + 1}$ is not, where:

$\displaystyle \mu = \sum_{k \mathop > 0} \floor{\frac n {p^k} }$

where $\left \lfloor{\cdot}\right \rfloor$ denotes the floor function.

### Technique

When calculating $\mu$, the easiest way to calculate the next term is simply to divide the previous term by $p$ and discard the remainder:

$\floor {\dfrac n {p^{k + 1} } } = \floor {\floor {\dfrac n {p^k} } / p}$

## Proof

Note that although the summation given in the statement of the theorem is given as an infinite sum, in fact it terminates after a finite number of terms (because when $p^k > n$ we have $0 < n/p^k < 1$).

From Number of Multiples less than Given Number, we have that $\floor{\dfrac n {p^k} }$ is the number of integers $m$ such that $0 < m \le n$ which are multiples of $p^k$.

We look more closely at $n!$:

$n! = 1 \times 2 \times \ldots \times \paren {n - 1} \times n$

We see that any integer $m$ such that $0 < m \le n$ which is divisible by $p^j$ and not $p^{j + 1}$ must be counted exactly $j$ times.

That is:

once in $\floor {\dfrac n p}$
once in $\floor {\dfrac n {p^2} }$

$\ldots$

once in $\floor {\dfrac n {p^j} }$

And that is all the occurrences of $p$ as a factor of $n!$.

Thus:

$\mu = \floor {\dfrac n p} + \floor {\dfrac n {p^2} } + \dotsb + \floor {\dfrac n {p^j} }$

Hence the result.

$\blacksquare$

## Examples

### Prime Factors of $1000!$

The prime decomposition of $1000!$ is given as:

 $\displaystyle 1000!$ $=$ $\displaystyle 2^{994} \times 3^{498} \times 5^{249} \times 7^{164} \times 11^{98} \times 13^{81} \times 17^{61} \times 19^{54} \times 23^{44} \times 29^{35} \times 31^{33} \times 37^{27}$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 41^{24} \times 43^{23} \times 47^{21} \times 53^{18} \times 59^{16} \times 61^{16} \times 67^{14} \times 71^{14} \times 73^{13} \times 79^{13} \times 83^{12} \times 89^{11}$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 97^{10} \times 101^9 \times 103^9 \times 107^9 \times 109^9 \times 113^8 \times 127^7 \times 131^7 \times 137^7 \times 139^7 \times 149^6 \times 151^6$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 157^6 \times 163^6 \times 167^5 \times 173^5 \times 179^5 \times 181^5 \times 191^5 \times 193^5 \times 197^5 \times 199^5 \times 211^4 \times 223^4$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 227^4 \times 229^4 \times 233^4 \times 239^4 \times 241^4 \times 251^3 \times 257^3 \times 263^3 \times 269^3 \times 271^3 \times 277^3 \times 281^3$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 283^3 \times 293^3 \times 307^3 \times 311^3 \times 313^3 \times 317^3 \times 331^3 \times 337^2 \times 347^2 \times 349^2 \times 353^2 \times 359^2$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 367^2 \times 373^2 \times 379^2 \times 383^2 \times 389^2 \times 397^2 \times 401^2 \times 409^2 \times 419^2 \times 421^2 \times 431^2 \times 433^2$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 439^2 \times 443^2 \times 449^2 \times 457^2 \times 461^2 \times 463^2 \times 467^2 \times 479^2 \times 487^2 \times 491^2 \times 499^2 \times 503$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 509 \times 521 \times 523 \times 541 \times 547 \times 557 \times 563 \times 569 \times 571 \times 577 \times 587 \times 593$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 599 \times 601 \times 607 \times 613 \times 617 \times 619 \times 631 \times 641 \times 643 \times 647 \times 653 \times 659$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 661 \times 673 \times 677 \times 683 \times 691 \times 701 \times 709 \times 719 \times 727 \times 733 \times 739 \times 743$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 751 \times 757 \times 761 \times 769 \times 773 \times 787 \times 797 \times 809 \times 811 \times 821 \times 823 \times 827$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 829 \times 839 \times 853 \times 857 \times 859 \times 863 \times 877 \times 881 \times 883 \times 887 \times 907 \times 911$ $\displaystyle$  $\, \displaystyle \times \,$ $\displaystyle 919 \times 929 \times 937 \times 941 \times 947 \times 953 \times 967 \times 971 \times 977 \times 983 \times 991 \times 997$

### Multiplicity of $2$ in $1000!$

The prime factor $2$ appears in $1000!$ to the power of $994$.

That is:

$2^{994} \mathrel \backslash 1000!$

but:

$2^{995} \nmid 1000!$

### Multiplicity of $3$ in $1000!$

The prime factor $3$ appears in $1000!$ to the power of $498$.

That is:

$3^{498} \divides 1000!$

but:

$3^{499} \nmid 1000!$

### Multiplicity of $5$ in $1000!$

The prime factor $5$ appears in $1000!$ to the power of $249$.

That is:

$5^{249} \divides 1000!$

but:

$5^{250} \nmid 1000!$

### Multiplicity of $7$ in $1000!$

The prime factor $7$ appears in $1000!$ to the power of $164$.

That is:

$7^{164} \mathrel \backslash 1000!$

but:

$7^{165} \nmid 1000!$

### Multiplicity of $11$ in $1000!$

The prime factor $11$ appears in $1000!$ to the power of $98$.

That is:

$11^{98} \divides 1000!$

but:

$11^{99} \nmid 1000!$

### Multiplicity of $13$ in $1000!$

The prime factor $13$ appears in $1000!$ to the power of $81$.

That is:

$13^{81} \mathrel \backslash 1000!$

but:

$13^{82} \nmid 1000!$

### Multiplicity of $2$ in $720!$

The prime factor $2$ appears in $720!$ to the power of $716$.

That is:

$2^{716} \divides 720!$

but:

$2^{717} \nmid 720!$

### Multiplicity of $3$ in $720!$

The prime factor $3$ appears in $720!$ to the power of $356$.

That is:

$3^{356} \divides 720!$

but:

$3^{357} \nmid 720!$

### Multiplicity of $5$ in $720!$

The prime factor $5$ appears in $720!$ to the power of $178$.

That is:

$5^{178} \divides 720!$

but:

$5^{179} \nmid 720!$

### Prime Factors of $20!$

The prime decomposition of $20!$ is given as:

$20! = 2^{18} \times 3^8 \times 5^4 \times 7^2 \times 11 \times 13 \times 17 \times 19$

## Also known as

De Polignac's Formula is also known as Legendre's Formula for Adrien-Marie Legendre.

## Source of Name

This entry was named for Alphonse Armand Charles Georges Marie de Polignac.