6
$\begingroup$

I'm looking for a fast method. I just multiplied all the numbers together modulo ten and divided by $5^{12}$ and $2^{12}$ modulo 10, which gave me $2$.

$\endgroup$
9
$\begingroup$

Here is a fast method to determine the last non-zero digit of $n!$.

Let the base $5$ representation of $n \in\mathbb{Z}^+$ be $\overline{a_{m}a_{m-1} \ldots a_{0}}_{5}$.

Prove that the last non-zero digit of $n!$ is $\equiv 2^{\sum\limits_{i=0}^{m}ia_{i}} \times \prod\limits_{i=0}^{m}a_{i}! \pmod{10}$.

This was a question I set for some quiz in the past, and can easily be done by induction. I leave this as an exercise.

This is fast in general since $a_i!$ is small and exploiting $2^{4k+1} \equiv 2 \pmod{10}$.


Applying this to $n=50$, $50=200_5$, so the last non-zero digit of $50!$ is $$\equiv 2^{0(0)+1(0)+2(2)}(2!0!0!) \equiv 2 \pmod{10}$$


Let's apply this to $n=2013$: $2013=31023_5$ so the last non-zero digit of $2013!$ is $$\equiv 2^{0(3)+1(2)+2(0)+3(1)+4(3)}3!1!0!2!3! \equiv 2^{17}(72) \equiv 2(2) \equiv 4 \pmod{10}$$


Motivation

Well I guess I should provide some motivation. Some of this will already be in the comments. The motivation will actually be quite close to a full proof, but I've left out the more boring/easy/straightforward parts.

We may easily determine the last digit of the product of all the non-multiples of $5$ which are $\leq n$, i.e.

$$\prod_{1 \leq k \leq n, 5 \nmid k}{k}$$

by using the fact that $(5i+1)(5i+2)(5i+3)(5i+4) \equiv 4 \pmod{10}$. We get $4^j(a_0!)$ where $n=5j+a_0$.

Intuitively, each power of $5$ sort of "removes a power of $2$" from this product, since they combine to form a power of $10$. So let's start with accounting for the multiples of $5$, and worry about multiples of $25, 125, \ldots$ later if need be.

For convenience, define $f(m)$ to be the last non-zero digit of $m$. By virtue of the fact that $n!$ is even for $n>1$, we may write at least for $n>1$

\begin{align} f(n!) \equiv f(6^jn!) & \equiv f(6^j\prod_{1 \leq k \leq n, 5 \nmid k}{k}\prod_{1 \leq k \leq j}{5k}) \pmod{10} \\ & \equiv f\left(30^j\left(\prod_{1 \leq k \leq n, 5 \nmid k}{k}\right)j!\right) \pmod{10} \\ & \equiv f(3^j[4^j(a_0!)]j!) \pmod{10} \\ & \equiv 2^ja_0!f(j!) \pmod{10} \end{align}

Already we can see that it is worthwile to consider the base $5$ expansion of $n$, and the term $\prod_{i=0}^{m}{a_i!}$ in the formula is apparent. What's left is to look at the product of the $2^j$ terms and express it in terms of $a_i$, and to prove the formula we get by strong induction.

$\endgroup$
  • $\begingroup$ Very nice, but without further explanation it comes off as a bit too clever. How did you discover this crazy formula? $\endgroup$ – dfeuer Nov 16 '13 at 23:22
  • $\begingroup$ @dfeuer Start with a recurrence relation for the last non-zero digit of $n!$, relating the last non-zero digit of $n!$ to the last non-zero digit of $\lfloor \frac{n}{5} \rfloor!$. It isn't too hard from there to guess what the formula should be, and then to use the recurrence to prove the formula by induction. $\endgroup$ – Ivan Loh Nov 16 '13 at 23:30
  • $\begingroup$ And why would I think to relate the last non-zero digits like that? $\endgroup$ – dfeuer Nov 16 '13 at 23:33
  • 1
    $\begingroup$ @dfeuer note that $(5i+1)(5i+2)(5i+3)(5i+4) \equiv 4 \pmod{10}$ so we can group all the non-multiples of $5$ and determine their product $\pmod{10}$. Then we just need to account for the powers of $5$ which will sort of "remove" powers of $2$ in your product. $\endgroup$ – Ivan Loh Nov 16 '13 at 23:36
  • 1
    $\begingroup$ The issue is a common one, I think. Someone figures something out and proudly displays the proof, but throws out the hardest and most instructive part—the figuring out. I've surely been guilty of this myself. There's always a strong temptation to "clean up" a proof, getting rid of anything not logically necessary but making everyone wonder how you got there. $\endgroup$ – dfeuer Nov 16 '13 at 23:50
4
$\begingroup$

You have correctly figured that $5^{12}$ is the highest power of $5$ that divides $50!$. Similarly, $\lfloor\frac{50}{2}\rfloor+\lfloor\frac{50}{4}\rfloor+\lfloor\frac{50}{8}\rfloor+\lfloor\frac{50}{16}\rfloor+\lfloor\frac{50}{32}\rfloor=25+12+6+3+1=47$, so $2^{47}$ is the highest power of $2$ that divides $50!$. We can similarly figure out the other highest powers of primes dividing $50!$: $\lfloor\frac{50}{3}\rfloor+\lfloor\frac{50}{9}\rfloor+\lfloor\frac{50}{27}\rfloor=16+5+1=22$, and $\lfloor\frac{50}{7}\rfloor+\lfloor\frac{50}{49}\rfloor=7+1=8$, and so forth, so in fact $$50!=2^{47}\cdot3^{22}\cdot5^{12}\cdot7^{8}\cdot11^{4}\cdot13^{3}\cdot17^{2}\cdot19^2\cdot23^2\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47.$$ Clearly, the number ends in exactly $12$ zeroes, so the desired digit is $50!/10^{12}\bmod10$, or $$2^{35}\cdot3^{22}\cdot7^{8}\cdot1^{4}\cdot3^{3}\cdot7^{2}\cdot9^2\cdot3^2\cdot9\cdot1\cdot7\cdot1\cdot3\cdot7\bmod10,$$ which is not too hard to compute using identities like $3^4=9^2\equiv1\bmod10$, $3\cdot7\equiv1\bmod10$. (It might not be super elegant, but I don't think there is a much quicker method.)

$\endgroup$
  • $\begingroup$ $25+12+6+3+1=47,$ right? $\endgroup$ – lab bhattacharjee Nov 17 '13 at 5:58
  • $\begingroup$ @labbhattacharjee. Indeed. Thanks. $\endgroup$ – Harald Hanche-Olsen Nov 17 '13 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.