How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? [duplicate]

Solution 1:

The number of zeros at the end of $N!$ is given by $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ where $\left \lfloor \frac{x}{y} \right \rfloor$ is the greatest integer $\leq \frac{x}{y}$.

To make it clear, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ where $\alpha_i \in \mathbb{N}$.

Note that $\alpha_5 < \alpha_2$, $\forall N$. (Why?)

The number of zeros at the end of $N!$ is the highest power of $10$ dividing $N!$

If $10^{\alpha}$ divides $N!$ and since $10 = 2 \times 5$, $2^{\alpha} | N!$ and $5^{\alpha} | N!$. Further since $\alpha_5 < \alpha_2$, the highest power of $10$ dividing $N!$ is the highest power of $5$ dividing $N!$ which is $\alpha_5$.

So you will find that for $N \leq 24$, the number of zeros will be less than or equal to 4. However when $N$ hits $25$ you will get 2 additional zeros courtesy $25$ since $25 \times 2^2 = 100$. Hence, there will be a jump when you go from $24$ to $25$.

EDIT:

Note that there will be

1. A jump of $1$ zero going from $(N-1)!$ to $N!$ if $5 || N$

2. A jump of $2$ zero going from $(N-1)!$ to $N!$ if $5^2 || N$

3. A jump of $3$ zero going from $(N-1)!$ to $N!$ if $5^3 || N$ and in general

4. A jump of $k$ zero going from $(N-1)!$ to $N!$ if $5^k || N$

where $a || b$ means $a$ divides $b$ and gcd($a,\frac{b}{a}$) = 1

EDIT

Largest power of a prime dividing $N!$

In general, the highest power of a prime $p$ dividing $N!$ is given by

$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

The first term appears since you want to count the number of terms less than $N$ and are multiples of $p$ and each of these contribute one $p$ to $N!$. But then when you have multiples of $p^2$ you are not multiplying just one $p$ but you are multiplying two of these primes $p$ to the product. So you now count the number of multiple of $p^2$ less than $N$ and add them. This is captured by the second term $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$. Repeat this to account for higher powers of $p$ less than $N$.

In case of the current example, the largest prime dividing $10$ is $5$. Hence, the largest power of $10$ dividing $N!$ is the same as the largest power of $5$ dividing $N!$.

Largest power of a prime dividing other related products

In general, if we want to find the highest power of a prime $p$ dividing numbers like $\displaystyle 1 \times 3 \times 5 \times \cdots (2N-1)$, $\displaystyle P(N,r)$, $\displaystyle \binom{N}{r}$, the key is to write them in terms of factorials.

For instance, $$\displaystyle 1 \times 3 \times 5 \times \cdots (2N-1) = \frac{(2N)!}{2^N N!}.$$ Hence, the largest power of a prime, $p>2$, dividing $\displaystyle 1 \times 3 \times 5 \times \cdots (2N-1)$ is given by $s_p((2N)!) - s_p(N!)$, where $s_p(N!)$ is defined above. If $p = 2$, then the answer is $s_p((2N)!) - s_p(N!) - N$.

Similarly, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle P(N,r)$ is given by $s_p((N)!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.

Similarly, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle C(N,r)$ is given by $s_p((N)!) - s_p(r!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.

Solution 2:

To answer that, you have to find the jump point from 4 to 6 zeros. The first is at 5!, the second at 10!, the third at 15!, and the forth at 20!. The next point is at 25!. What happens there is, you're multiplying by 5*5, which will multiply with 2 even numbers, and add 2 more zeros.

Solution 3:

HINT $\: $ The power of a prime $\rm\:p\:$ dividing $\rm\ n!\:$ jumps from $\rm\: p-1\:$ for $\rm\: n = p^2-1\:$ to $\rm\: p+1\: $ for $\rm\: n = p^2\:$ since their are $\rm\:p-1\:$ naturals $\rm < p^2\ $ divisible by $\rm\:p\:,\:$ viz. $\rm\ p,\ 2\:p,\:\cdots\:,\: (p-1)\:p\:.\ $ Now put $\rm\ p = 5\:.$