0
$\begingroup$

So I have a question where it says to find the last non zero digit of $20!$

I proceeded in the following way:

Found the prime factorization of $20!$ by calculation the greatest powers of $2,3,5,7,11,13,17,19$ in $20!$ using the following formula....for 2....as follows...

$$\left[\frac{20}{2}\right]+\left[\frac{20}{4}\right]+\left[\frac{20}{8}\right]+\left[\frac{20}{16}\right] = 18$$ and did the same for 3,5,7,9,11,13,17,19

This turned out to be $$20! = 2^{18}\times3^8\times5^4\times7^2\times11\times13\times17\times19$$

From here, multiplying in my head with just the unit digits gave me the answer that is, 4.

Is there any way to do it easier? I was able to do this as 20 is relatively small and it would have a max prime of 19, but what if, for example, the question was asked to find the last non zero digit in $77!$? Then this wouldn't be possible.

Any help would be appreciable

$\endgroup$
  • $\begingroup$ @lulu I want to be able to do it without that formula $\endgroup$ – Techie5879 Aug 27 '19 at 14:01
  • 1
    $\begingroup$ Why? That sort of recursion is the natural way to solve this sort of problem. $\endgroup$ – lulu Aug 27 '19 at 14:02
  • $\begingroup$ @lulu Oh ... didn't know that...just didn't find that formula elsewhere so was wondering how it works, just another thing to remember I guess $\endgroup$ – Techie5879 Aug 27 '19 at 14:04
  • $\begingroup$ I wouldn't bother memorizing it, as the question itself is so artificial. I certainly don't remember the formula, just that there is such a formula and that it is easily looked up when needed. $\endgroup$ – lulu Aug 27 '19 at 14:05
  • 1
    $\begingroup$ Last non Zero digit in 50! can you try to read this, I think it can help you $\endgroup$ – tommaso faustini Aug 27 '19 at 14:09
3
$\begingroup$

Here is how I would do it for $77!$:

  • First we have to find the greatest power of $0$ which divides $77!$. Denoting, for each prime number $p$, $v_p(n)$ the exponent of $p$ in the prime decomposition of $n$, we determine $v_2(77!)$ and $v_5(77!)$ with Legendre's formula: $$v_p(n)=\sum_{k\ge 1}\biggl\lfloor\frac{n}{p^k}\biggr\rfloor\qquad\text{(this sum is actually finite)}.$$ We find $\;v_2(77!)=73,\quad v_5(77!)=18$, so we nee to find the last digit of $\;\dfrac{77!}{10^{18}}$.
  • We also need the $p$-valuation of $77!$ for all primes $p<77$ such that $p\not\equiv 1\bmod 10$, i.e. $p\in\{3,7,13,17,19,23,29,37,43,47,53,59,67,73\}$ This is not so long as this list might suggest: $$\begin{array}{c} p =\\[1ex]v_p(77!) \end{array}\enspace\begin{array}{*{14}|} 3 &7& 13&17&19&23&29&37&43&47&53&59&67&73 \\[1ex] \hline 35 & 12 & 5 & 4 & 4 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline \end{array}$$ so \begin{align} \frac{77!}{10^{18}}&\equiv 2^{55}\, 3^{35}\,7^{12}\,13^{5}\,17^4\,19^4\,23^3\,29^2\,37^2\,43\,47\,53\,59\, 67\,73 \\ &\equiv 2^{55}\, 3^{60}\,7^{20}\quad\text{because }13,23,43,53,63\equiv 3,\enspace 19,29,59\equiv 9 \\ &\hspace{5em}\text{ and }\; 17, 37, 47, 67 \equiv 7\bmod 10\\ &\equiv 2^{55}\, 3^{40} \hspace{1.5em}\text{since }3\cdot 7\equiv 1\bmod 10 \\ &\equiv 2^3 \hspace{3.27em}\text{because }2^ k\equiv 2^{k\bmod4}\;(k\ge 1) \text{ and } 3^4\equiv 1 \bmod 10 \\&\equiv\color{red} 8 \bmod 10. \end{align}
$\endgroup$
  • $\begingroup$ I've finally found out! A typo on screen made me write a second $37$ in the table of valuations (between $59$ and $67$), so I obtained $7^{21}$ instead of $7^{20}$, and there remains really $3^{40}$ after simplification, and the latter is $1\bmod 10$. $\endgroup$ – Bernard Aug 27 '19 at 22:10
  • $\begingroup$ Thank you for having pointed the error! $\endgroup$ – Bernard Aug 27 '19 at 22:11
  • $\begingroup$ This is basically what I did, but thanks any way! $\endgroup$ – Techie5879 Oct 9 '19 at 18:56
  • $\begingroup$ How did you find $4$? $\endgroup$ – Bernard Oct 9 '19 at 19:04
  • $\begingroup$ So I did it in this way....$2^{18}\times5^4 = 10^4 \times 2^{14}$ So last digit from here is as effective as last digit from $2^{14}$, which is 4. Last digit of $3^{8}$ is 1. Last digit from $7^2$ = 9. Last digit from $11 \times 13 \times 17 \times 19 \equiv$ last digit of $1 \times 3 \times 7 \times 9 \equiv 9$. So, the final last digit would be equivalent to last digit in $4 \times 1 \times 9 \times 9 \equiv 4$. $\endgroup$ – Techie5879 Oct 9 '19 at 19:17
0
$\begingroup$

Once you get the exponent on each prime factor, aggregate them to cut down on the multiplication you need VC to do.

  • Subtract the exponent on $5$ from the exponent on $2$, here $18-4=14$. Since $14$ is a two more than a multiple of $4$ use a factor of $2^2=4$.

  • Now add the exponents on all primes ending in $3$ and subtract those on all primes ending in $7\equiv3^{-1}\bmod 10$. Thus $(8+1)-(2+1)=6$. This is again two more than a multiple of $4$, take this factor as $3^2=9$.

  • Add up exponents on all primes ending in $9$. If even, you just have a factor if $1$ so nothing, if odd use a factor of $9$. Here the latter applies.

  • Multiply your factors getting $4×9×9=14\color{blue}{4}$ where the units digit of this product is your answer.

$\endgroup$
0
$\begingroup$

Well, I just answered a very similar question.

What is the last non-zero digit of $(\dots((2018\underset{! \text{ occurs }1009\text{ times}}{\underbrace{!)!)!\dots)!}}$?

Meanwhile, there is a much MUCH simpler way to do this than in the answers already given. In particular, to find the last nonzero digit of $N!$; $N$ large, there is no need to factor $N$ besides knowing $N$ mod 40 that is. First, note the following: Let $N$ be an multiple of 10 i.e., $N=10k$. Then the last nonzero digit of $N!$ is

a) $3 \cdot 4 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \equiv _{10} $ 8 if $k \equiv_4 1$;

b) $8^2$ mod 10 which is 4 if $k \equiv_4 2$;

c) $8^3$ mod 10 which is 2 if $k \equiv_4 3$; and

d) $8^4$ mod 10 which is 6 if $k \equiv_4 0$.

Now let $N$ be of the form $10k+i$ where $i \equiv_{10} N$; $i$ nonzero. Then from the above the last nonzero digit of $N!$ is

(a$'$) $(8 \times $ the last nonzero digit of $(\prod_{j=1}^i j)) \mod 10$ if $k \equiv_4 1$;

(b$'$) $(4 \times $ the last nonzero digit of $(\prod_{j=1}^i j)) \mod 10$ if $k \equiv_4 2$;

(c$'$) $(2 \times $ the last nonzero digit of $(\prod_{j=1}^i j)) \mod 10$ if $k \equiv_4 3$;

(d$'$) $(6 \times $ the last nonzero digit of $(\prod_{j=1}^i j)) \mod 10$ if $k \equiv_4 4$.

So from (b) above the last nonzerto digit of $20!$ is 4. From (c$'$) the last nonzero digit of $77!$ is $2 \times (3 \cdot 4 \cdot 6 \cdot 7)$ $\mod 10$ which is 8.

Note that [almost] NO factoring is needed here.

$\endgroup$
0
$\begingroup$

I don't think 77! is much harder,tedious maybe, all primes greater than 38 have exponent 1, all primes less than that but greater than 25 have exponent 2. then between that and 19 have exponent 3, between that and 15 have exponent 4, that and 12 have exponent 5. between that and 11 have exponent 6, 7 and 11, 5 and 15, 3 and 25, 2 and 38. so we get (mostly exclusive of end points) :$$77!=2^{38}×3^{25}×5^{15}×7^{11}×{11}^7×13^5×17^4×19^4×23^3×29^2×31^2×37^2×41×43×47×53×59×61×67×71×73$$ really, this is not quite right but that's because I didn't think of prime powers that only play with exponents on the primes below the sqrt of the number under factorial.

once you account for 19 multiples of 4, 9 multiples of 8, 4 multiples of 16,2 multiples of 32, 1 multiple of 64, 8 multiples of 9, 2 multiples of 27, 3 multiples of 25, and 1 multiple of 49, it all works out.

That was quick( okay didn't time). only ones that aren't a long division away where less than than 11. large would be 400+ at least. $$(7!)(9!)^7$$ only leaves with values divisible by 2 and 5 to deal with before it's last non-zero digit is the same.

$\endgroup$

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