$25! \pmod {78125}$ $25! \pmod{78125}$ is a problem I'm working on.
Since $78125$ looked very divisible by $5$, I checked, and found that $78125 = 5^7$.
Then I thought, if there are seven factors 5 in $25!$, then $25! \equiv 0 \mod 78125$, but I only found $25$ to be divisible by 5 six times, so I don't think that got me anywhere.
Am I even on the right track here?
Thanks in advance for any help!
 A: We can utilize the fact that if $a_1 n \equiv a_2 n \pmod{N}$, then $a_1 \equiv a_2 \pmod{\frac{N}{\gcd(n, N)}}$. In particular, we can write $25! \equiv k \cdot 5^6 \pmod{5^7}$, and $k = (1 \cdot 2 \cdot 3 \cdot 4)^5 \cdot (1 \cdot 2 \cdot 3 \cdot 4)$. We can compute $k$ mod $5$ with the aforementioned property to get $k \equiv 24^6 \equiv 1 \pmod{5}$.
Note $k$ must be either $0, 1, 2, 3, 4$ because there are only $5$ multiples of $5^6$ in $5^7$.
A: If $\frac{25!}{5^6}\equiv k \pmod{5}$, then $5\mid\frac{25!}{5^6}-k$, i.e. $5^7\mid 25!-k\cdot 5^6$ so $25!\equiv k\cdot 5^6 \pmod{5^7}$. What remains is to find $k$.
For that, note $\frac{25!}{5^6}=(1\cdot 2 \cdot 3 \cdot 4) \cdot (6
\cdot 7 \cdot 8 \cdot 9) \cdot (11 \cdot 12 \cdot 13 \cdot 14) \cdot (16 \cdot 17 \cdot 18 \cdot 19) \cdot (21 \cdot 22 \cdot 23 \cdot 24)\cdot(\frac55 \cdot \frac{10}{5} \cdot \frac{15}{5} \cdot \frac{20}{5})\equiv (4!)^6\equiv (-1)^6=1 \pmod 5$ , so $k=1$.
That gives us the answer: $25!\equiv 5^6 \pmod {5^7}$.
A: You  have Legendre's formula:

Let $p$ be a prime number, and denote, for any natural number $x$, $v_p(x)$ the $p$-valuation of $x$. Then
  $$v_p(n!)=\sum_{k\ge 1}\biggl\lfloor\frac n{p^k}\biggr\rfloor.$$
  (The sum is actually finite since $p^k>n!$ for some  $k$).

So in the present case, we obtain
$$v_5(25!)=\frac{25}5+\frac{25}{25}=6.$$
