Find the last two non-zero digits of $70!$

Question

The question itself is quite straightforward, however, I am unable to get an exact answer to the problem. I have narrowed it down to four possibilities one from $\{18, 43, 68, 93\}$.

The approach

We begin by finding the number of zeros that are contained in $70!$. This is done as shown below:

$$ \sum_{n=1}^\infty \left\lfloor \frac{70}{5^n} \right\rfloor = 16 $$

And clearly

$$ \sum_{n=1}^\infty \left\lfloor \frac{70}{2^n} \right\rfloor > \sum_{n=1}^\infty \left\lfloor \frac{70}{5^n} \right\rfloor \qquad \qquad \text{(i)} $$

So therefore we define some integer $N$ such that:

$$ N = \frac{70!}{5^{16}2^{16}} $$

From here we will find the remainder of $N$ modulo $4$ and $25$ respectively so we can use the Chinese Remainder Theorem to finish the problem.

Verifying mod 4

From (i) it is clear that $N$ will enough spare twos to be divisible by $4$. This leads us to the conclusion that:

$$ N \equiv 0 \pmod 4 $$

Verifying mod 25

We can split this part of the problem into two parts. Define another integer $M$ such that $$ M = \frac{70!}{5^{21}} $$ This allows us to write: $$ \frac{1}{2^{16}} \cdot M = N $$

Finding 2^16 mod 25

Trivially, we can find that

$$ 2^{16} = 65536 \equiv 11 \pmod {25} $$

Finding M mod 25

This one is a little trickier. To do this, we will use the fact that:

$$ (5n+1)(5n+2)(5n+3)(5n+4) \equiv -1 \pmod {25} $$

Notice that we can group $M$ as follows: $$ \begin{align*} (1\cdot2\cdot3\cdot4)(6\cdot7\cdot8\cdot9)\cdots(66\cdot67\cdot68\cdot69) \ &\times \\ (1\cdot2\cdot3\cdot4)(6\cdot7\cdot8\cdot9)(11\cdot12\cdot13\cdot14) \ &\times \\ (1\cdot2) \end{align*} $$

Now, we can easily see:

$$ M \equiv (-1)^{12} \cdot (-1)^{3} \cdot {2} \equiv 23 \pmod {25} $$

Bringing it together

Now we have the following equation

$$ N \equiv \frac{M}{2^{16}} \equiv \frac{23}{11} \pmod {25} $$

This is where I got stuck.

From here I tried to write $$\frac{23 + 25k}{11} \pmod{25}$$ and this yields four possible solutions $\{18, 43, 68, 93\}$. Is there a way that I can find the correct solution and/or a better way to solve the problem?

Thanks!

Answer 1

Once you have residue $0\bmod4$ you are sure that the residue $\bmod100$ will be a multiple of $4$. So pick the solution out of your four that is a multiple of four.

There is also a minor error in your derivation. When you render

$M=[(1×2×3×4)(6×7×8×9)...(66×67×68×69)][(1×2×3×4)(6×7×8×9)(11×12×13×14)](1×2)$

you simplify this to $(-1)^{12}(-1)^3(2)\bmod 25$. But, properly, the first group has fourteen sets of four factors, so the first power of $-1$ should have exponent $14$.

Answer 2

From here we will find the remainder of $N$ modulo $4$ and $25$ respectively so we can use the Chinese Remainder Theorem to finish the problem.

$$ N \equiv 0 \pmod 4 $$

$$ N \equiv \frac{M}{2^{16}} \equiv \frac{23}{11} \pmod {25} $$

$$\color{red}{\text{THIS IS WHERE I GOT STUCK!}}$$

To simplify $\frac{23}{11} \pmod {25}$, you can compute the inverse of 11 mod 25, by solving the Diophantine equation $11 x - 25 q = 1$. This will give you $11^{-1} = 16 \pmod {25}$. Thus $N \equiv 23 \times 16 \equiv 18 \pmod{25} $.

Now you can apply your last planned step, which was to use the Chinese remainder theorem to go from $N \equiv 0 \pmod{4}, N \equiv 18 \pmod{25}$ to $N \equiv ?? \pmod{100}$.

But actually, since $100 = 25 \times 4$, we don't even need the heavy artillery here. Just list the 4 possibilities $\{18, 43, 68, 93\}$ and cross out the 3 which are not $\equiv 0 \pmod{4}$.

We end up with $N \equiv 68 \pmod{100}$.

My computer confirms that result: $$70! = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319\color{red}{68}0000000000000000$$