p-adic 进赋值阶乘（勒让德公式）

Factorials can be put to many uses. Most of this, however, is used in probability, which we will not discuss in this topic. However, there are certain commonly tested aspects of pure-algebraic factorials that you should know.

Explanation:

$300!$ would essentially be $300*299*298*...*2*1$

We also know that $2*5=10$

Disregarding the extraneous zeros that may appear inside the final product, the number of zeros on the END of $300!$ will depend on how many $5$'s and $2$'s there are within the set ${300,299,298,...,2,1}$. Remember that since it takes a $5$ and $2$ to make a $10$ or one zero, and since there are less multiples of five up to $300$ than there are multiples of two, we can solve this problem by counting up all the $5$'s found from $1$ to $300$.

Let's start counting the multiples of five, $5, 10, 15, 20$, each of these yielding one $5$ apiece. $25$, however, yields two $5$'s (because $5*5=25$). We now observe that multiples of five yield one $5$ apiece, but multiples of $25$ yield two $5$'s apiece.

We can count up all the $5$'s found from $1$ to $100$, which would be one apiece from $5,10,15,20,30,35,40,45,55,60,65,70,80,85,90,95$, and two apiece from $25,50,75,100$, resulting in $16+8=24$ fives.

From $101$ to $200$ we have one $5$ apiece from $105,110,115,120,130,135,140,145,155,160,165,170,180,185,190,195$, two $5$'s apiece from $150,175,200$, and three $5$'s apiece from $125$ (since $5*5*5=125$), totaling $16+6+3=25$ fives.

Finally, from $201$ to $300$ we have one $5$ apiece from $205,210,215,220,230,235,240,245,255,260,265,270,280,285,290,295$, two $5$'s apiece from $225,275,300$ and three $5$'s apiece from $250$, totaling $16+6+3=25$ fives.

Add those up and we get $24+25+25=\boxed{74}$

There's another way to get this, for those of you who might've already understood this concept, which would be take all the multiples of $5$, $25$, and $125$ from $1$ to $300$ and sum them, which would be $60+12+2=\boxed{74}$

Legendre's Formula

Before I start, I assume that everyone looking this post understand what are floor function, Euclidean algorithm and number bases.

In some mathematics competition, you are required to do big operations with limited of time, as an example, what is the highest power of $k$ that divides $n!$ ? This is pretty popular and most students may get stumped when they see this type of problem. How do we tackle this type of problem?

We have one simple formula, that is Legendre's Formula. It states that

$e_p(n!)=\displaystyle\sum^{\infty}_{i=1}\Big\lfloor\frac{n}{p^i}\Big\rfloor=\frac{n-S_p(n)}{p-1}$

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

For proofs, see this link. Credits to AoPS.

Now we are going to move on to some examples to make you clear.

1. Find the highest power of 2 that divides 15!.

Solution. This is a direct application of Legendre's Formula, we have

$e_2(15!)=\displaystyle\sum^{\infty}_{i=1}\Big\lfloor\frac{15}{2^i}\Big\rfloor=\frac{15-S_2(15)}{2-1}$

You can either choose the middle of the equality or the rightmost of the equality to calculate. In fact, do one of them is enough.

$e_2(15!)=\Big\lfloor\frac{15}{2}\Big\rfloor+\Big\lfloor\frac{15}{2^2}\Big\rfloor+\Big\lfloor\frac{15}{2^3}\Big\rfloor+\Big\lfloor\frac{15}{2^4}\Big\rfloor+...=11$

OR

$e_2(15!)=\frac{15-S_2(15)}{2-1}$

Here, we need to change 15 into binary aka base 2. It is simple, use Euclidean algorithm.

$15=2(7)+1$

$7=2(3)+1$

$3=2(1)+1$

$1=2(0)+1$

Take the remainders, which are 1, 1, 1, 1. Read it from bottom to top, that is 15 in base 2! Therefore, $15=(1111)_2$, $S_2(15)=4$. Substitute back, we get our final answer which is 11.

(They lead to same answer, but this is not strong enough to prove the formula above. This is just to show you how do you tackle the similar problems in the future.)

1. Find the highest power of 10 that divides 23!.

(For the next problems, I will show the calculation in the middle part of equality.)

Analysis: When you see the question asks you to find the highest power of $y$ that divides $x!$ and $y$ is composite, take the largest prime factor of $y$. So, for this problem, the highest prime factor of 10 is 5. Set your $n=23$ and $p=5$ (Remember the formula above?).

Solution: $e_5(23!)=\Big\lfloor\frac{23}{5}\Big\rfloor+\Big\lfloor\frac{23}{5^2}\Big\rfloor+...=4$

1. Find the highest power of 27 that divides 27!.

Analysis: Notice that 27 is a perfect power of 3. Same as above, take the largest prime factor, which is 3 and set your $p$ as 3. Remember in the end of your solution you must divide it by 3 and take the integral part of your answer. As an example, if you get $8\frac{2}{3}$, then your answer should be 8.

[Notice that they ask for the highest power of 27, and $27^{\frac{2}{3}}=9$ (recall the multiplication of indices formula, $a^m\times a^n=a^{m+n}$)]

Solution: $e_3(27!)=\Big\lfloor\frac{27}{3}\Big\rfloor+\Big\lfloor\frac{27}{3^2}\Big\rfloor+\Big\lfloor\frac{27}{3^3}\Big\rfloor+\Big\lfloor\frac{27}{3^4}\Big\rfloor+...=13$

So the highest power of 27 that divides 27! is $\Big\lfloor\frac{13}{3}\Big\rfloor=4$.

1. Find the highest power of 64 that divides 128!

Analysis: Follow all the steps as in problems 1,2 and 3, and this time you have to divide by 6 in the end. Do you see why?

Solution: $e_2(128!)=\Big\lfloor\frac{128}{2}\Big\rfloor+\Big\lfloor\frac{128}{2^2}\Big\rfloor+\Big\lfloor\frac{128}{2^3}\Big\rfloor+\Big\lfloor\frac{128}{2^4}\Big\rfloor+...=127$

So the highest power of 64 that divides 128! is simply $\Big\lfloor\frac{127}{6}\Big\rfloor=21$.

Time for some practices!!!

5)Find the maximum value of $n$ in $a^n|k!$ when

i) a=2, k=425

ii) a=6, k=253

iii) a=12, k=423

That's all. :)

Prime Factorization of Factorials

The reader should read this post for some introduction to floor functions and preliminary problems.

Let's start with a classic problem.

Find the number of zeros at the end of $2015!$

If you don't know what factorial is, read What is a factorial. Then, experiment with some small values of the factorials - $n!$ has no zeros for $n=0,1,2,3,4$, and $5!$ has a zero at the end for the first time. So, let's explore when a number has trailing zeros. This is kinda easy. A number has trailing zeros when it is divisible by $10$. More precisely, if $n$ is divisible by $10^k$, then it has $k$ trailing zeros. For example, $1300$ is divisible by $10^2$, and is has two trailing zeros. So, to find the number of trailing zeros of $n!$, we just need to find the maximum power $k$ for which $10^k$ divides $n!$. In other words, we should investigate the prime factorization of factorials.

$5!=2^3\cdot3^1\cdot5^1$ and $6!=2^4\cdot3^2\cdot5^1$. It is obvious that there are more $2$'s than $5$'s. Therefore, if we count the number of $5$ in $n!$, that will be the number of trailing zeros as well. Because each $5$ paired with a $2$ will give us a $10$, and the $2$'s not paired will be left alone. See the demonstration with $n=5,6$ and some other values. You will reach the same conclusion.

Now, we focus only on how to get the number of $5$'s in $n!$. First, ask yourself, when do we get a $5$? We don't get any in $1,2,3,4$, but in $5$. So, first there is a $5$ in $5!$. So, each number divisible by $5$ contributes some factors of $5$ in the factorization. Let's take $28!$ for example. We will get a $5$ from $5,10,15,20,25$ up to $28$. Each of them gives at least one $5$. So, the power of $5$ in $28!$ is $5$ at least. In short, this is actually the number of numbers divisible by $5$ which are less than or equal to $28$, which is in turn $\left\lfloor\frac{28}5\right\rfloor=5$.

But, there were some extra $5$'s. The extra $5$ actually comes from $25$, since it is divisible by $5^2$. Which means, each number divisible by $5^2$ will give an extra $5$. The number of such numbers is $\left\lfloor\frac{28}{25}\right\rfloor=1$. Thus, the maximum power of $5$ in $28!$ is $\left\lfloor\frac{28}5\right\rfloor+\left\lfloor\frac{28}{25}\right\rfloor=5+1=6$. We don't need to go see if any number is divisible by $5^3=125$ since $125>28$.

Similarly, for $143!$, it would be $\left\lfloor\frac{143}{5}\right\rfloor+\left\lfloor\frac{143}{5^2}\right\rfloor+\left\lfloor\frac{143}{5^3}\right\rfloor=28+5+1=34$. Therefore, the number of trailing zeros of $n!$ is \begin{eqnarray*} \left\lfloor\frac{n}{5^1}\right\rfloor+ \left\lfloor\frac{n}{5^2}\right\rfloor+\ldots+ \left\lfloor\frac{n}{5^k}\right\rfloor \end{eqnarray*} where $k$ is such that $5^k\le n<5^{k+1}$. For $n=143$, we had $k=3$, as $5^3\le 143<5^4$. However, it is equally correct to just write this as \begin{eqnarray*} \left\lfloor\frac{n}{5^1}\right\rfloor+ \left\lfloor\frac{n}{5^2}\right\rfloor+ \left\lfloor\frac{n}{5^3}\right\rfloor+\ldots\infty \end{eqnarray*} because the terms $\left\lfloor\frac{n}{5^i}\right\rfloor$ become zero for $i>k$. Using summation, this is $\sum\limits_{i\geq1}\left\lfloor\frac{n}{5^i}\right\rfloor$ or, $\sum\limits_{i=1}^k\left\lfloor\frac{n}{5^i}\right\rfloor$ where $k$ is the largest integer such that $5^k\leq n$ i.e. $5^k\leq n<5^{k+1}$. Using logarithms, we may write $k=\lfloor \log_5 n\rfloor$.

Certainly, the same process works for any prime $p$. The maximum power of $p$ in $n!$ is therefore \begin{eqnarray*} \left\lfloor\frac{n}{p^1}\right\rfloor+ \left\lfloor\frac{n}{p^2}\right\rfloor+ \left\lfloor\frac{n}{p^3}\right\rfloor+\ldots & = & \sum\limits_{i=1}^{\lfloor \log_p n \rfloor}\left\lfloor\frac{n}{p^i}\right\rfloor \end{eqnarray*} This is known as Legendre's theorem.