AoPSWiki
Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!

Legendre's Formula

From AoPSWiki

Legendre's Formula states that

e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}

where p is a prime and e_p(n) is the exponent of p in the prime factorization of n and S_p(n) is the sum of the digits of n when written in base p.

Proof

Part 1

We could say that e_p(n!) is equal to the number of multiples of p less than n, or \lfloor \frac{n}{p}\rfloor. But the multiples of p^2 are only counted once, when they should be counted twice. So we need to add \lfloor \frac{n}{p^2}\rfloor on. But this only counts the multiples of p^3 twice, when we need to count them thrice. Therefore we must add a \lfloor \frac{n}{p^3}\rfloor on. We continue like this to get e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor. This makes sense, because the terms of this series tend to 0.

Part 2

Let the base p representation of n be e_xe_{x-1}e_{x-2}\dots e_0, where e_i is a digit for all 0\leq i\leq x. Therefore the base p representation of \lfloor \frac{n}{p^i}\rfloor is e_xe_{x-1}\dots e_{x-i}. Note that the infinite sum of these numbers (which is e_p(n!)) is

\sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1)=\sum_{j=1}^{x} e_j(\frac{p^j-1}{p-1})=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{...

=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1}=\frac{n-S_p(n)}{p-1}.

This article is a stub. Help us out by expanding it.

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Legendre%27s_Formula"
Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us