# $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. – Angina Seng Dec 22 '19 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. – WhatsUp Dec 22 '19 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 – J. W. Tanner Dec 22 '19 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$) – J. W. Tanner Dec 22 '19 at 1:00
• @WhatsUp: I still meant in conjuction with the argument that $16!$ is divisible by $125$ – J. W. Tanner Dec 22 '19 at 1:03
• Ah, I understand now. You mean to avoid $2\times 4$. – WhatsUp Dec 22 '19 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$$