# $16!$ without calculator

Scrolling through old discrete mathematics exams I have came across this "choose correct answer" question:

$$16!$$ is:

• a). $$20 \; 922 \; 789 \; 888 \; 000$$
• b). $$18 \; 122 \; 471 \; 235 \; 500$$
• c). $$17 \; 223 \; 258 \; 843 \; 600$$

Would you show me how your thinking process of solving this problem would look like?

The ultimate goal is to find the correct answer; how you get to it does not matter, except that you have to invest only a reasonable amount of time, and calculators or other devices are not allowed.

• As b is more divisible by $5$ then by $2$ then that's the obvious wrong answer. As c is not divisible by $5^3$ that's the lsightly less obvious wrong answer. Dec 22, 2019 at 2:57

$$16!$$ is divisible by $$125$$ since it's divisible by $$5\times10\times15$$, and by $$8$$, since it's divisible by $$2\times4$$.

Therefore, $$16!$$ must be a multiple of $$1000$$, and the only acceptable choice is a).

• Also doable by summing digits. Dec 22, 2019 at 0:47
• yes, @WhatsUp, by summing digits, it is seen that only choice a) is divisible by $9$; you could post that as an alternative answer Dec 22, 2019 at 0:49
• By the way, I could also have argued that $16!$ is divisible by $8$ since it's divisible by $8$ (or $16$) Dec 22, 2019 at 1:00
• @WhatsUp: I still meant in conjuction with the argument that $16!$ is divisible by $125$ Dec 22, 2019 at 1:03
• Ah, I understand now. You mean to avoid $2\times 4$. Dec 22, 2019 at 1:05

Since $$16!$$ is divisible by $$9$$, the sum of its digits must also be divisible by $$9$$. $$20\ 922\ 789\ 888\ 000 \to 63$$ $$18\ 122\ 471\ 235\ 500 \to 41$$ $$17\ 223\ 258\ 843\ 600 \to 51$$ Only answer a) is divisible by $$9$$.

We could also have looked for divisibility by $$11$$ with alternate sum of the digits. $$20\ 922\ 789\ 888\ 000 \to 11$$ $$18\ 122\ 471\ 235\ 500 \to -5$$ $$17\ 223\ 258\ 843\ 600 \to -7$$ Only answer a) is divisible by $$11$$.

\begin{align}16!&=1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12\times13\times14\times15\times16 \\&=(2\times5\times10)\times3\times4\times6\times7\times8\times9\times11\times12\times13\times14\times15\times16 \\&=100\times(3\times4\times6\times7\times8\times9\times11\times12\times13\times14\times15\times16)\end{align} So the final answer will have $$2$$ zeros at the end. If you want the first digit after the zeros, you can multiply the remaining numbers modulo $$10$$.

\begin{align}&3\times4\times6\times7\times8\times9\times11\times12\times13\times14\times15\times16 \pmod {10} \\&= 3\times4\times6\times7\times8\times9\times1\times2\times3\times4\times5\times6 \pmod {10} \\&= 2\times6\times7\times8\times9\times2\times3\times4\times5\times6 \pmod {10} \\&= 2\times7\times8\times9\times2\times3\times4\times5\times6 \pmod {10} \\&= 4\times8\times9\times2\times3\times4\times5\times6 \pmod {10} \\&= 2\times9\times2\times3\times4\times5\times6 \pmod {10} \\&= 8\times2\times3\times4\times5\times6 \pmod {10} \\&= 6 \times3\times4\times5\times6 \pmod {10} \\&= 8\times4\times5\times6 \pmod {10} \\&= 2\times5\times6 \pmod {10} \\&= 60 \pmod {10} \\&= 0 \pmod {10} \end{align}

So the last 3 digits of $$16!$$ are $$000$$ and the answer must be a).

Update: Due to the down-votes I took the time to carefully explain the method here.

Note: If you remember your times tables you can actually do the work written out below in your head using your fingers to keep track of where you are at (yes, you don't have 16 fingers but it's still doable).

Moreover, if you observe that the OP's answers b) and c) both have two leading zeroes, you can stop after the third calculation with the $$\text{*}$$ indicator below, saving you one last calculation.

Working in $$\Bbb N \to \{0, 1,2,3, \dots\}$$.

Any integer $$a \ge 1$$ has a $$\text{base-}10$$ representation,

$$\tag 1 a = \displaystyle{\sum_{k=0}^n a_k 10^k} \text{ with } a_k \in \{0, 1,2,3,4,5,6,7,8,9\} \text{ and } a_n \gt 0$$

We define $$\rho: \Bbb N^{\gt 0} \to \{1,2,3,4,5,6,7,8,9\}$$ as follows:

$$\quad \rho(n) = \text{the smallest } k \text{ such that } a_k \ne 0 \text{ in (1)}$$

For the OP numbers we have

$$\quad \rho(20 \; 922 \; 789 \; 888 \; 000) = 8$$

$$\quad \rho(18 \; 122 \; 471 \; 235 \; 500) = 5$$

$$\quad \rho(17 \; 223 \; 258 \; 843 \; 600) = 6$$

Proposition: $$\rho(ab) = \rho\big(\rho(a)\rho(b)\big)$$.

Calculations

$$\rho(1!) = 1$$
$$\rho(2!) = 2$$
$$\rho(3!) = 6$$
$$\rho(4!) = 4$$
$$\rho(5!) = 2$$ *
$$\rho(6!) = 2$$
$$\rho(7!) = 4$$
$$\rho(8!) = 2$$
$$\rho(9!) = 8$$
$$\rho(10!) = 8$$ *
$$\rho(11!) = 8$$
$$\rho(12!) = 6$$
$$\rho(13!) = 8$$
$$\rho(14!) = 2$$
$$\rho(15!) = 3$$ *
$$\rho(16!) = 8$$