9
$\begingroup$

Find the last non zero digit of 28!.

It is very hard to multiply and find the last nonzero digit. I just wanna know that, is there any easy technique to solve this type of problem?

$\endgroup$
  • 2
    $\begingroup$ Consider factors of $10$ separately (you can ignore them). Build factors of $10$ by pairing a factor of $5$ with a factor of $2$. If you pair say the factor $5$ from $15$ and a factor $2$ from $12$, that leaves you with the factors $3$ and $6$ that you cannot discard. Multiply the remaining factors modulo $10$ (that means you need only remember the last digit of each partial product). $\endgroup$ – Daniel Fischer Sep 10 '14 at 21:14
  • $\begingroup$ @DanielFischer This approach can be improved by noticing that there will always be more factors of 2 than factors of 5. So one can increase a counter when encountering a 2 and decreasing it when encountering a 5. And since the last digit of $2^1$ and $2^5$ is the same, the counter can be reduced mod 4. $\endgroup$ – kasperd Sep 11 '14 at 10:33
12
$\begingroup$

Note that $$5\times 10\times 15\times 20\times 25=5\times(2\cdot 5)\times (3\cdot 5)\times (2^2\cdot 5)\times 5^2=2^3\cdot 3\cdot 5^6$$ and that $$10^6=2^6\cdot 5^6=\frac{8\cdot 5\cdot 10\cdot 15\cdot 20\cdot 25}{3}=8\cdot 5\cdot 10\cdot 5\cdot 20\cdot 25.$$

So, in mod $10$, we have $$\begin{align}\frac{28!}{10^6}&\equiv 1\cdot 2\cdot 3\cdot 4\cdot 6\cdot 7\cdot 9\cdot 1\cdot 2\cdot 3\cdot 4\cdot 3\cdot 6\cdot 7\cdot 8\cdot 9\cdot 1\cdot 2\cdot 3\cdot 4\cdot 6\cdot 7\cdot 8\\&\equiv (1\cdot 2\cdot 3\cdot 4\cdot 6\cdot 7)^3\cdot 3\cdot 8^2\cdot 9^2\\&\equiv \{1\cdot 2\cdot 3\cdot 4\cdot (-4)\cdot (-3)\}^3 \cdot 3\cdot 4\cdot 1\\&\equiv 2\cdot 2\\&\equiv 4.\end{align}$$

$\endgroup$
  • $\begingroup$ Nice solution. You dropped the ! from $28!/10^6$, but it won't let me make a one-character edit. $\endgroup$ – Bungo Sep 10 '14 at 21:56
  • $\begingroup$ @Bungo: Thanks:) $\endgroup$ – mathlove Sep 10 '14 at 21:57
  • 7
    $\begingroup$ @Bungo in cases of need you can add an HTML <!-- comment --> explaining why your too-short edit really is good, and then it won't be a too-short edit anymore :) $\endgroup$ – hobbs Sep 11 '14 at 0:58
  • $\begingroup$ @hobbs: Thanks for the tip! $\endgroup$ – Bungo Sep 11 '14 at 1:08
5
$\begingroup$

Here is a technique:

  1. Factor all numbers $1,\dots,28$ as a product of twos, fives and other numbers. (Other numbers meaning numbers not divisable by 2 or 5.)
  2. Calculate the number of fives and remove them, and also remove an equal number of twos. (Each zero at the end is due to a factor of $10=5\times2$, and there are always more twos than fives.)
  3. For the remaining factors (including the remaining twos), calculate them modulo 10 (simply remove tens) and multiply them. You can also make any other changes modulo 10, like turning a $9$ into $-1$.
  4. The last digit of this product will be the last nonzero digit of $28!$

Example in the case of $11!$:

  1. $1=1$, $2=2$, $3=3$, $4=2^2$, $5=5$, $6=2\times3$, $7=7$, $8=2^3$, $9=9$, $10=2\times5$, $11=11$.
  2. There are two fives.
  3. The remaining factors are $1$, $2$ (6 times), $3$ (twice), $7$, $9$ and $11$.
  4. The product is $1\times2^6\times3^2\times(-3)\times(-1)\times1=2^63^3=1728$. The last nonzero digit of $11!$ is thus 8. (Check: $11!=39916800$.)

This technique is not optimal, but it works. Once you figure out why and how it works, you can probably find a way to make it more efficient if you want to do such calculations again. Note that in the last step it suffices to calculate the product modulo 10, so you can throw away unnecessary tens and hundreds.

$\endgroup$
2
$\begingroup$

Perhaps a small reduction in the calculations in other answers. First, we use the standard technique for finding the power of a prime which divides a factorial: $$\Bigl\lfloor\frac{28}{5}\Bigr\rfloor+\Bigl\lfloor\frac{28}{25}\Bigr\rfloor =5+1=6$$ so $5^6$ is a factor of $28!$ (and $5^7$ is not), and likewise $$\Bigl\lfloor\frac{28}{2}\Bigr\rfloor+\Bigl\lfloor\frac{28}{4}\Bigr\rfloor +\Bigl\lfloor\frac{28}{8}\Bigr\rfloor +\Bigl\lfloor\frac{28}{16}\Bigr\rfloor=14+7+3+1=25\ ,$$ so $2^{25}$ is a fcator of $28!$. Therefore $28!$ ends with $6$ zeros and we need the last digit of $28!/10^6$. Simplifying modulo $10$, we have $$2^\equiv2^5\equiv2^9\equiv2^{13}\equiv2^{17}\ ,\quad 3^4\equiv1\ ,\quad 7^4\equiv1\ ,\quad 9^2\equiv1\ ;$$ cancelling $2$s and $5$s and reducing the resuts modulo $10$ gives $$\eqalign{28!/10^6 &\equiv2^{19}1.1.3.1.1.3.7.1.9.1.1.3.3.7.3.1.7.9.9.1.1.1.3.3.1.3.7.7\cr &\equiv2^3.3^8.7^5.9^3\cr &\equiv8.1.7.9\cr &\equiv4\ .\cr}$$

$\endgroup$
1
$\begingroup$

Here is a general technique that calculates the digit in question in polylog time. The technique is applied to $28!$ at the end since that is the specific question here. I apply it to $1000!$ to emphasize that it can be used for much larger numbers.


The idea is to extract all powers of $5$ and $2$ from $n!$, and write it as $10^A2^BC$ with $C$ odd and not a multiple of $5$. Then $A$ is the number of trailing zeros. And whatever $2^BC$ is modulo 10 is the preceding digit. To that end, these two reduction formulas are useful. They use $$n\underset{2}{!}=1\cdot3\cdot5\cdots(\text{last odd number}\leq n)$$ and $$n\underset{5}{!}=1\cdot3\cdot7\cdot9\cdot11\cdot13\cdot17\cdots(\text{last such number}\leq n)$$ and the reduction rules (which are easy to verify) are $$\begin{align} n! &= n\underset{2}{!} \times \left\lfloor\frac{n}{2}\right\rfloor! \times 2^{ \left\lfloor\frac{n}{2}\right\rfloor}\\ n\underset{2}{!} &= n\underset{5}{!} \times \left(2\left\lfloor\frac{n+5}{10}\right\rfloor-1\right)\underset{2}{!} \times 5^{\left\lfloor\frac{n+5}{10}\right\rfloor}\hspace{2pc}n\geq5 \end{align}$$ The first of these is something you may have seen before. The second is the result of trying to find a similar formula that excludes multiples of $5$. A number of the form $n\underset{5}{!}$ is only important to us mod $10$, and $n\underset{5}{!}\equiv (1\times3\times7\times9)^{\left\lfloor\frac{n}{10}\right\rfloor}\times\epsilon\equiv 9^{\left\lfloor\frac{n}{10}\right\rfloor}\times\epsilon$, where $\epsilon$ is either $1$, $3$ or $9$ depending on $n$ the last digit of $n$. These two reduction rules together with the modular reduction of $n\underset{5}{!}$ cut the size of $n$ in half, and repeated application will bring the size of $n$ down fairly fast. We have:

\begin{align} 1000!&\equiv1000\underset{2}{!}\times500!\times2^{500}\\ &\equiv1000\underset{5}{!}\times199\underset{2}{!}\times5^{100}\times500!\times2^{500}\\ &\equiv9^{100}\times500!\times199\underset{2}{!}\times2^{500}\times5^{100} \\ &\equiv500!\times199\underset{2}{!}\times2^{500}\times5^{100}\\ & \text{...note we've cut the largest number in play from 1000 to 500...}\\ & \text{...repeated factorial and modular reductions...}\\ &\equiv 2^{994}\times5^{249}\\ &\equiv10^{249}\times2^{741}\\ &\equiv10^{249}\times2^1 \end{align}

So there are $249$ zeros, and the preceding digit is a $2$ (in $1000!$).


Applied to $28!$:

\begin{align} 28! &\equiv28\underset{2}{!}\times14!\times2^{14}\\ &\equiv\left(28\underset{5}{!}\times5\underset{2}{!}\times5^3\right)\times14!\times2^{14}\\ &\equiv9^2\times5\underset{2}{!}\times5^3\times14!\times2^{14}\\ &\equiv10^3\times2^{11}\times5\underset{2}{!}\times14!\\ &\equiv10^3\times2^{11}\times15\times14!\\ &\equiv10^4\times2^{10}\times3\times14!\\ &\equiv10^4\times2^{10}\times3\times\left(14\underset{2}{!}\times7!\times2^7\right)\\ &\equiv10^4\times2^{17}\times3\times14\underset{2}{!}\times7!\\ &\equiv10^4\times2^{17}\times3\times\left(14\underset{5}{!}\times1\underset{2}{!}\times5^1\right)\times7!\\ &\equiv10^5\times2^{16}\times3\times14\underset{5}{!}\times7!\\ &\equiv10^5\times2^{16}\times3\times\left(9\times3\right)\times7!\\ &\equiv10^5\times2^{16}\times7!\\ &\equiv10^5\times2^{16}\times5040\\ &\equiv10^6\times2^{16}\times504\\ &\equiv10^6\times2^{16}\times4\\ &\equiv10^6\times2^{18}&2^{a+4n}\equiv2^a\text{ for }a\geq1\\ &\equiv10^6\times2^{2}\\ &\equiv10^6\times4\\ \end{align}

So $28!$ ends with six $0$s and it's first nonzero digit (from the right) is a $4$.

$\endgroup$

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.