Last Digit Fever continues

Find the last non zero digit of 100 ! \large\color{#3D99F6}{100!} .

2 4 8 9 6 1

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Pi Han Goh
Apr 25, 2015

Group the numbers as such:

100 ! ( 10 ) × ( 1 × 2 × 3 × × 9 ) × ( 11 × 12 × 13 × × 19 ) × ( 21 × 22 × 23 × × 29 ) × ( 91 × 92 × 93 × × 99 ) \begin{aligned} && 100!^{(10)} \times (1 \times 2 \times 3 \times \ldots \times 9) \\ & \times & (11 \times 12 \times 13 \times \ldots \times 19) \\ & \times & (21 \times 22 \times 23 \times \ldots \times 29) \\ & \cdot & \\ & \cdot & \\ & \cdot & \\ & \times & (91 \times 92 \times 93 \times \ldots \times 99) \\ \end{aligned}

Note the multifactorial notation.

Take modulo 10 10 for all the brackets:

100 ! ( 10 ) × ( 9 ! ) 10 = ( 100 × 90 × × 10 ) × ( 9 ! ) 10 = 1 0 10 × 10 ! × ( 9 ! ) 10 = 1 0 11 × 9 ! × ( 9 ! ) 10 = 1 0 11 × ( 9 ! ) 11 \begin{aligned} && 100!^{(10)} \times (9!)^{10} \\ &=& \bigg ( 100 \times 90 \times \ldots \times 10 \bigg) \times (9!)^{10} \\ &=& 10^{10} \times 10! \times (9!)^{10} \\ &=& 10^{11} \times 9! \times (9!)^{10} \\ &=& 10^{11} \times (9!)^{11} \\ \end{aligned}

Since we are only considering the last non-zero digit of 100 ! 100! , we can ignore 1 0 11 10^{11} . So we are left to find the last non-zero digit of ( 9 ! ) 11 (9!)^{11} .

9 ! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 = ( 5 × 2 ) × 2 7 × 3 2 × 7 \begin{aligned} 9! &=& 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \\ &=& (5 \times 2) \times 2^7 \times 3^2 \times 7 \\ \end{aligned}

Take away all factors of 5 × 2 = 10 5 \times 2 = 10 and we are finally left with a last digit that is non-zero.

We are left to compute ( 2 7 3 2 7 ) 11 ( m o d 10 ) (2^7 \cdot 3^2 \cdot 7)^{11} \pmod{10} .

Since we are only considering the very last number, we can reduce the powers by modular 4 4 .

( 2 7 3 2 7 ) 11 ( 2 7 m o d 4 3 2 7 ) 11 m o d 4 ( 2 3 3 2 3 ) 3 ( 2 3 3 3 ) 3 6 ( 3 3 ) m o d 4 6 1 4 \begin{aligned} (2^7 \cdot 3^2 \cdot 7)^{11} & \equiv & (2^{7 \bmod \ 4} \cdot 3^2 \cdot 7)^{11 \bmod \ 4} \\ & \equiv & (2^3 \cdot 3^2 \cdot -3)^3 \\ & \equiv & -(2^3 \cdot 3^3)^3 \\ & \equiv & -6^{(3\cdot 3) \bmod \ 4} \\ & \equiv & -6^{1} \equiv \boxed{4} \\ \end{aligned}

Note that from this article , the correct formula, which Kalpok Guha interpreted wrongly is:

The generalized formula to for the last non-zero digit of N ! N! is the same for the last non-zero digit of the number

N 5 ! × 2 N 5 × ( N m o d 5 ) ! \left \lfloor \frac N 5 \right \rfloor ! \times 2^{\left \lfloor \frac N 5 \right \rfloor} \times (N \bmod \ 5 )!

Pi Han Goh - 6 years, 1 month ago

Log in to reply

Thank you for the link ¨ \ddot \smile

Tanishq Varshney - 6 years, 1 month ago
Kalpok Guha
Apr 25, 2015

Using the formula of last non zero digit in N ! N!

[ N 5 ] ! 2 [ N 5 ] R e m [ N 5 ] ! [\frac{N}{5}]!*2^{[\frac{N}{5}]}*Rem^{[\frac{N}{5}]!}

R e m Rem denotes the remainder when N N is divided by 5 5

when there is no remainder [ N 5 ] ! 2 [ N 5 ] [\frac{N}{5}]!*2^{[\frac{N}{5}]}

We get that the last non zero digit is 4 4 .

Moderator note:

Like many people has pointed out. A simple counterexample N = 100 N=100 shows that it's wrong.

I'm never good at remembering complex NT formulas, so I use a systematic process.


This problem requires 4 tools: Wilson's Theorem, Chinese Remainder Theorem, De-Polignac's formula and last but not the least, Extended Euclidean Algorithm for computation of modular inverse.

Denote by ν p ( n ) \nu_p(n) the p-adic order of non-negative integer n n , where p p is a prime. Using De-Polignac's formula , we get that,

ν 5 ( 100 ! ) = 24 and ν 2 ( 100 ! ) = 97 > 24 \nu_5(100!)=24\quad\textrm{and}\quad\nu_2(100!)=97\gt 24

Let X = 100 ! 1 0 24 \mathcal{X}=\dfrac{100!}{10^{24}} . Then, the value we're looking for is X m o d 10 \mathcal{X}\bmod 10 because dividing 100 ! 100! by 1 0 24 10^{24} in X \mathcal{X} clears out all the trailing zeros of 100 ! 100! .

Now, comes the use of Wilson's Theorem . Note that 5 5 is a prime and as such, we have 4 ! 1 ( m o d 5 ) 4!\equiv -1\pmod{5} . Now, extending this congruence relationship gives us,

( 5 n 1 ) ( 5 n 2 ) ( 5 n 3 ) ( 5 n 4 ) 1 ( m o d 5 ) n Z + (5n-1)(5n-2)(5n-3)(5n-4)\equiv -1\pmod{5}~\forall~n\in\Bbb{Z^+}

Now, using the results obtained till now, we have,

X 0 ( m o d 2 ) X ( 1 ) 20 5 20 20 ! 1 0 24 ( 1 ) 25 5 24 1 0 24 2 24 ( m o d 5 ) \mathcal{X}\equiv 0\pmod2\\~\\ \mathcal{X}\equiv\frac{(-1)^{20}\cdot 5^{20}\cdot 20!}{10^{24}}\equiv \frac{(-1)^{25}\cdot 5^{24}}{10^{24}}\equiv -2^{-24}\pmod5

Using the Extended Euclidean Algorithm , we compute 2 1 ( m o d 5 ) 2^{-1}\pmod5 . This value exists since gcd ( 2 , 5 ) = 1 \gcd(2,5)=1 and the existence of this inverse is guaranteed by Bezout's Lemma . Now, let z 2 1 ( m o d 5 ) z\equiv 2^{-1}\pmod5 . Then,

z 2 1 ( m o d 5 ) 2 z 1 ( m o d 5 ) z 3 ( m o d 5 ) z\equiv 2^{-1}\pmod{5}\implies 2z\equiv 1\pmod{5}\implies z\equiv 3\pmod5

Now, we form the following congruence system using the results obtained till now:

X { 0 ( m o d 2 ) z 24 3 24 ( 1 ) 12 1 X { 0 ( m o d 2 ) 1 ( m o d 5 ) \mathcal{X}\equiv\begin{cases}0\pmod2\\ -z^{24}\equiv -3^{24}\equiv -(-1)^{12}\equiv -1\end{cases}\implies \mathcal{X}\equiv\begin{cases}0\pmod2\\ -1\pmod5\end{cases}

Using the Chinese Remainder Theorem , we have,

X 0 + ( 1 ) z 2 6 4 ( m o d 10 ) \mathcal{X}\equiv 0+(-1)\cdot z\cdot 2\equiv -6\equiv 4\pmod{10}

X m o d 10 = 4 \therefore\quad\mathcal{X}\bmod 10=4


Note to the problem poster:

Are you sure that the formula you stated is correct? Because, from my point of view, it fails to several values of N N . For example, it fails for N = 0 , 1 , 2 , 3 , 4 N=0,1,2,3,4 .

Prasun Biswas - 6 years, 1 month ago

Log in to reply

That^^, Would be too Long for a Problem which Can be Formed By a formula XD. Even I don't remember These Formulae but, This is a bit too long XD.

No offence @Prasun Biswas

Mehul Arora - 6 years, 1 month ago

Log in to reply

None taken, but I strictly encourage finding the value using a systematic process instead of using a ready-made formula. Even then, the formula seems false to me because it fails for N = 0 , 1 , 2 , 3 , 4 N=0,1,2,3,4 .

Prasun Biswas - 6 years, 1 month ago

Woah! Chinese Remainder theorem finishes it. Nice @Prasun Biswas

Nihar Mahajan - 6 years, 1 month ago

Log in to reply

I tried to keep it as simple as possible. Notify me if you don't understand some particular detail. I hope people would be able to follow the calculations done.

Prasun Biswas - 6 years, 1 month ago

Log in to reply

@Prasun Biswas I appreciate your work. You have elegantly used various theorems and lemmas to prove it. Thats just awesome!

Nihar Mahajan - 6 years, 1 month ago

Log in to reply

@Nihar Mahajan This isn't awesome in any way. This is a pretty standard process used for finding last non-zero digit of any large factorial.

Prasun Biswas - 6 years, 1 month ago

Log in to reply

@Prasun Biswas BTW thanks for sharing this with us. :)

Nihar Mahajan - 6 years, 1 month ago

Log in to reply

@Nihar Mahajan Mention not. :)

Prasun Biswas - 6 years, 1 month ago

You can make your work neater if you do this:

By De Polignac: there's v 5 ( 100 ! ) = 24 v_{5}(100!) = 24 , then consider modulo 5 5 :

100 ! 5 24 100 ! ( 5 ) × ( 1 × 2 × 3 × 4 ) × ( 6 × 7 × 8 × 9 ) × ( 11 × 12 × 13 × 14 ) × × ( 96 × 97 × 98 × 99 ) 4 ! 20 × 5 20 × 20 ! 5 20 × 20 ! \begin{aligned} \frac {100!}{5^{24}} &\equiv & 100!^{(5)} \times (1 \times 2 \times 3 \times 4) \\ &&\times (6 \times 7 \times 8 \times 9) \\ && \times (11 \times 12 \times 13 \times 14) \\ && \times \ldots \\ && \times (96 \times 97 \times 98 \times 99) \\ &\equiv & 4!^{20} \times 5^{20} \times 20! \\ &\equiv & 5^{20} \times 20! \\ \end{aligned}

So we want 100 ! 1 0 24 5 20 20 ! 2 24 \frac {100!}{10^{24}} \equiv \frac {5^{20} \cdot 20!}{2^{24}} \equiv \ldots

You skipped a lot of steps (that are crucial in simplification) in X ( 1 ) 20 5 20 20 ! 1 0 24 ( 1 ) 25 5 24 1 0 24 2 24 ( m o d 5 ) \mathcal{X}\equiv\frac{(-1)^{20}\cdot 5^{20}\cdot 20!}{10^{24}}\equiv \frac{(-1)^{25}\cdot 5^{24}}{10^{24}}\equiv -2^{-24}\pmod5 .

Pi Han Goh - 6 years, 1 month ago

Log in to reply

I still don't get this part of your comment:

100 ! 5 24 5 20 × 20 ! ( m o d 5 ) \frac{100!}{5^{24}}\equiv 5^{20}\times 20!\pmod{5}


I presume that you meant this:

100 ! 5 20 × 20 ! 5 24 ( m o d 5 ) 100 ! 5 24 1 ( m o d 5 ) 100 ! 1 0 24 2 24 ( m o d 5 ) 100!\equiv 5^{20}\times 20!\equiv -5^{24}\pmod5 \implies \frac{100!}{5^{24}}\equiv -1\pmod5\\ \implies \frac{100!}{10^{24}}\equiv -2^{-24}\pmod5

Right?

And by the way, I was thinking of showing those steps but I thought it was trivial since I already mentioned the result (extension by Wilson's Theorem) before I did that work. You know how lazy I can be. :P

Also, thanks for reminding me of the multifactorial notation. I had forgotten about that. :P

Prasun Biswas - 6 years, 1 month ago

Log in to reply

@Prasun Biswas Ah, yes! Small typo. Thanks. Oh, there's no need to bring up Wilson's Theorem, when you can easily show that 4 ! 1 ( m o d 5 ) 4! \equiv -1 \pmod 5 .

Pi Han Goh - 6 years, 1 month ago

Log in to reply

@Pi Han Goh Funny thing is that I initially thought you were using the rising factorial notation. I later realized that it was the multifactorial notation.

And btw, come to fb or the chat in Math SE. Why you no active on social sites? :3

Prasun Biswas - 6 years, 1 month ago

No Extended Euclidean Algorithm and CRT required.

Let z 2 24 ( m o d 5 ) 2 24 z 1 4 2 22 z 1 z \equiv -2^{-24} \pmod 5 \Rightarrow 2^{24} z \equiv -1 \equiv 4 \Rightarrow 2^{22}z \equiv 1 , by Fermat's Little Theorem

2 22 m o d 4 z 1 4 z 1 4 z 1 4 ( m o d 5 ) 2^{22 \bmod \ 4 }z \equiv 1 \Rightarrow 4z \equiv 1 \equiv -4 \Rightarrow z \equiv -1 \equiv 4 \pmod 5 . With z 0 ( m o d 2 ) z \equiv 0 \pmod 2 , we can easily show that z 4 ( m o d 10 ) z \equiv 4 \pmod {10} .

Pi Han Goh - 6 years, 1 month ago

Log in to reply

Minor typo:

2 22 m o d 4 z 1 z 4 ( m o d 5 ) 2^{22~\bmod~\color{#D61F06}{4}}z\equiv 1\implies z\equiv 4\pmod5

Prasun Biswas - 6 years, 1 month ago

Log in to reply

@Prasun Biswas FIXED. thanks.

Pi Han Goh - 6 years, 1 month ago

Well how is the formula derived?

P.s. Can you show the working? According to what you gave above this is what I got 20 2 20 [ 100 ] 20* 2^{20} [100] how is this 4 4 ???

Sualeh Asif - 6 years, 1 month ago

Log in to reply

@Sualeh Asif , Actually, I think he meant that the Last Digit of N! Is the Last digit of the formula above. Actually, THAT Comes out to be 4. I have tagged him To make sure that he checks his formula out.

Mehul Arora - 6 years, 1 month ago

Will you please elaborate ?

Rishabh Tripathi - 6 years, 1 month ago

@Kalpok Guha ,I am not Sure Whether This Formula exists. If It does, Kindly Tell me the derivation and The Proof of it. And, I think that you meant That,

The last non Zero Digit of N! is the Last digit of [ N 5 ] 2 [ N 5 ] [ N ] [\frac{N}{5}]*2^{[\frac{N}{5}]}[N] . KIndly Check it out. Thanks.

Mehul Arora - 6 years, 1 month ago

can u tell me how r u getting the last digit as 4 from the above formula.

20 2 20 [ 100 ] 20*2^{20} [100] = 2097152000 2097152000 . Plz reply @Nihar Mahajan @Prasun Biswas

Tanishq Varshney - 6 years, 1 month ago

Log in to reply

The formula stated is wrong. See the comment on @Pi Han Goh 's solution for the corrected one and the link to the source.

Prasun Biswas - 6 years, 1 month ago

Sorry everyone.I wrote [N] wrongly and also missed the factorial sign in the first step. I wanted to write [ N 5 ] ! 2 [ N 5 ] R e m [ N 5 ] ! [\frac{N}{5}]!*2^{[\frac{N}{5}]}*Rem^{[\frac{N}{5}]!} .I think this formula is correct.I apologize to every members of brilliant.Please forgive me

Kalpok Guha - 6 years, 1 month ago

10 ! = 3628800 10! = 3628800

last non-zero digit is 8

8 1 0 = 1073741824 8^10 = 1073741824

So 4 must be the last non-zero digit of 100 ! 100!

Very effective but not clear to me. Can you explain ?

Eliott Collin - 6 years ago
Shyam Sundar
Apr 29, 2015

10! = 3628800. Thus, the last non-zero number for 10! is 8. As a natural progression, last non-zero digit for: 20! = 8x8 = 64 ---> Last digit is 4 (8 times 8 because the last non-zero digit of10! is going to get multiplied with 1, 2,3..... 9 successively) 30! = 8x4 = 32 ----> Last digit is 2 40! = 8x2 = 16 ----> Last digit is 6 50! = 8 x 6 = 48 ----> Last digit is 8 From 60! onwards, the pattern 4, 2, 6 and 8 is going to get repeated endlessly as we move up the base by a factor of 10 incrementally. Thus, the last digit for 100! is 4.

Actually the last non-zero digit of 30! is 8. For 40! it is 2 and for 50! it is 2 again.

Martin Papanek - 6 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...