$25! \pmod {78125}$

Question

$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!

Answer 1

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$.

Answer 2

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.$$

Answer 3

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}$.

Answer 4

$25! = 2^a3^b5^c7^d11^e13^f....*23^z$ for some powers.

To get the powers you factor out the multiples of each prime. As there are $5$ multiples $5$ so that accounts for $5$ powers. Then there is $1$ multiple of $25$. As we have factored out $5$ from this already this accounts for one more power of $5$ (not two).

So..

$25! = 2^{12+6+3+1=22}3^{8+2=10}5^{5+1=6}7^311^2*13*17*19*23$

And $ 78125 = 5^7$$

So $25! \equiv 5^6(2^{22}3^{10}7^311^2*13*17*19*23) \equiv 5^6K \mod 5^7$

So $K \equiv 2^{22}3^{10}7^311^2*13*17*19*23 \mod 5 $

$\equiv 4^{11}*9^5*2^3*1^2*3*7*(-1)*3\equiv -1*-1*3*3*2*-1*3 = 1\mod 5$

So $25! \equiv 5^6= 15625\mod 78125$

....

($5*10*15*20*25=5^5(1*2*3*4*5)=5^6*(1*2*3*4)$ accounts for the six powers of $5$. In general, for the power of prime $p$ you do $[\frac np] + [\frac n{p^2}] + [\frac n{p^3}]+... $ etc. It think you counted the $25$ as two powers of $5$ when is should only have counted once. THe thing is you already factored out one power of $5$ when you counted the multiples of $5$. Each time you count the multiples of $5$ etc. you factor $5$ from the multiples of $5^k$ so by the time you get to counting the multiples of $5^k$ you have already factored $5^{k-1}$ so you only count a multiple of $5^k$ as contributing one factor of $5$; not $k$.)

Specifically= $25! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25$

$=2^{12} * 1*1*3*2*5*3*7*4*9*5*11*6*13*7*15*8*17*9*19*10*21*11*23*12*25$

$=2^{12}*2^6* 1*1*3*1*5*3*7*2*9*5*11*3*13*7*15*4*17*9*19*5*21*11*23*6*25$

$=2^{12}*2^6*2^3* 1*1*3*1*5*3*7*1*9*5*11*3*13*7*15*2*17*9*19*5*21*11*23*3*25$

$=2^{12}*2^6*2^3*2^1 *1*1*3*1*5*3*7*1*9*5*11*3*13*7*15*1*17*9*19*5*21*11*23*3*25$

$=2^{22} *3*5*3*7*9*5*11*3*13*7*15*17*9*19*5*21*11*23*3*25$

$=2^{22}3^8 * 1*5*1*7*3*5*11*1*13*7*5*17*3*19*5*7*11*23*1*25$

$=2^{22}3^83^2 * 1*5*1*7*1*5*11*1*13*7*5*17*1*19*5*7*11*23*1*25$

$=2^{22}3^{10} * 5*7*5*11*13*7*5*17*19*5*7*11*23*25$

$=2^{22}3^{10}5^5* 1*7*1*11*13*7*1*17*19*1*7*11*23*5$

$=2^{22}3^{10}5^55^1* 1*7*1*11*13*7*1*17*19*1*7*11*23*1$

$=2^{22}3^{10}5^6* 7*11*13*7*17*19*7*11*23$

$=2^{22}3^{10}5^67^3*11*13*17*19*11*23$

$=2^{22}3^{10}5^67^3*11^2 *13*17*19*23$