Let be a prime and . Find a formula for the largest power of which divides .
Before attacking this problem, we prove the following lemma.
Lemma: Let . The number of multiples of which are less than or equal to is .
Proof: Note first that is precisely the quotient part returned by the Euclidean algorithm on and , since if where , then , so . Then we have for precisely .
Now for the main problem. Our goal is to find a formula that gives the largest power of which divides ; equivalently, to find the number of times appears in the factorization of . Note that there will be one factor for each multiple of less than – that is, . This does not account for all of the factors, though; multiples of contribute one more each, for a total of . We can continue for higher powers of ; for each we count an additional factors. Note that every factor is counted. Moreover, no factor is counted more than once. Thus, the highest power of which divides is , where . Note that for sufficiently large , , so that the summation indeed converges.