Find the last non zero digit of 1 0 0 ! .
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.
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 ! is the same for the last non-zero digit of the number
⌊ 5 N ⌋ ! × 2 ⌊ 5 N ⌋ × ( N m o d 5 ) !
Using the formula of last non zero digit in N !
[ 5 N ] ! ∗ 2 [ 5 N ] ∗ R e m [ 5 N ] !
R e m denotes the remainder when N is divided by 5
when there is no remainder [ 5 N ] ! ∗ 2 [ 5 N ]
We get that the last non zero digit is 4 .
Like many people has pointed out. A simple counterexample N = 1 0 0 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 ) the p-adic order of non-negative integer n , where p is a prime. Using De-Polignac's formula , we get that,
ν 5 ( 1 0 0 ! ) = 2 4 and ν 2 ( 1 0 0 ! ) = 9 7 > 2 4
Let X = 1 0 2 4 1 0 0 ! . Then, the value we're looking for is X m o d 1 0 because dividing 1 0 0 ! by 1 0 2 4 in X clears out all the trailing zeros of 1 0 0 ! .
Now, comes the use of Wilson's Theorem . Note that 5 is a prime and as such, we have 4 ! ≡ − 1 ( m o d 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 +
Now, using the results obtained till now, we have,
X ≡ 0 ( m o d 2 ) X ≡ 1 0 2 4 ( − 1 ) 2 0 ⋅ 5 2 0 ⋅ 2 0 ! ≡ 1 0 2 4 ( − 1 ) 2 5 ⋅ 5 2 4 ≡ − 2 − 2 4 ( m o d 5 )
Using the Extended Euclidean Algorithm , we compute 2 − 1 ( m o d 5 ) . This value exists since g cd ( 2 , 5 ) = 1 and the existence of this inverse is guaranteed by Bezout's Lemma . Now, let z ≡ 2 − 1 ( m o d 5 ) . Then,
z ≡ 2 − 1 ( m o d 5 ) ⟹ 2 z ≡ 1 ( m o d 5 ) ⟹ z ≡ 3 ( m o d 5 )
Now, we form the following congruence system using the results obtained till now:
X ≡ { 0 ( m o d 2 ) − z 2 4 ≡ − 3 2 4 ≡ − ( − 1 ) 1 2 ≡ − 1 ⟹ X ≡ { 0 ( m o d 2 ) − 1 ( m o d 5 )
Using the Chinese Remainder Theorem , we have,
X ≡ 0 + ( − 1 ) ⋅ z ⋅ 2 ≡ − 6 ≡ 4 ( m o d 1 0 )
∴ X m o d 1 0 = 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 . For example, it fails for N = 0 , 1 , 2 , 3 , 4 .
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
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 .
Woah! Chinese Remainder theorem finishes it. Nice @Prasun Biswas
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.
Log in to reply
@Prasun Biswas – I appreciate your work. You have elegantly used various theorems and lemmas to prove it. Thats just awesome!
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.
Log in to reply
@Prasun Biswas – BTW thanks for sharing this with us. :)
You can make your work neater if you do this:
By De Polignac: there's v 5 ( 1 0 0 ! ) = 2 4 , then consider modulo 5 :
5 2 4 1 0 0 ! ≡ ≡ ≡ 1 0 0 ! ( 5 ) × ( 1 × 2 × 3 × 4 ) × ( 6 × 7 × 8 × 9 ) × ( 1 1 × 1 2 × 1 3 × 1 4 ) × … × ( 9 6 × 9 7 × 9 8 × 9 9 ) 4 ! 2 0 × 5 2 0 × 2 0 ! 5 2 0 × 2 0 !
So we want 1 0 2 4 1 0 0 ! ≡ 2 2 4 5 2 0 ⋅ 2 0 ! ≡ …
You skipped a lot of steps (that are crucial in simplification) in X ≡ 1 0 2 4 ( − 1 ) 2 0 ⋅ 5 2 0 ⋅ 2 0 ! ≡ 1 0 2 4 ( − 1 ) 2 5 ⋅ 5 2 4 ≡ − 2 − 2 4 ( m o d 5 ) .
Log in to reply
I still don't get this part of your comment:
5 2 4 1 0 0 ! ≡ 5 2 0 × 2 0 ! ( m o d 5 )
I presume that you meant this:
1 0 0 ! ≡ 5 2 0 × 2 0 ! ≡ − 5 2 4 ( m o d 5 ) ⟹ 5 2 4 1 0 0 ! ≡ − 1 ( m o d 5 ) ⟹ 1 0 2 4 1 0 0 ! ≡ − 2 − 2 4 ( m o d 5 )
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
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 ) .
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
No Extended Euclidean Algorithm and CRT required.
Let z ≡ − 2 − 2 4 ( m o d 5 ) ⇒ 2 2 4 z ≡ − 1 ≡ 4 ⇒ 2 2 2 z ≡ 1 , by Fermat's Little Theorem
2 2 2 m o d 4 z ≡ 1 ⇒ 4 z ≡ 1 ≡ − 4 ⇒ z ≡ − 1 ≡ 4 ( m o d 5 ) . With z ≡ 0 ( m o d 2 ) , we can easily show that z ≡ 4 ( m o d 1 0 ) .
Log in to reply
Well how is the formula derived?
P.s. Can you show the working? According to what you gave above this is what I got 2 0 ∗ 2 2 0 [ 1 0 0 ] how is this 4 ???
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.
Will you please elaborate ?
@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 [ 5 N ] ∗ 2 [ 5 N ] [ N ] . KIndly Check it out. Thanks.
can u tell me how r u getting the last digit as 4 from the above formula.
2 0 ∗ 2 2 0 [ 1 0 0 ] = 2 0 9 7 1 5 2 0 0 0 . Plz reply @Nihar Mahajan @Prasun Biswas
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.
Sorry everyone.I wrote [N] wrongly and also missed the factorial sign in the first step. I wanted to write [ 5 N ] ! ∗ 2 [ 5 N ] ∗ R e m [ 5 N ] ! .I think this formula is correct.I apologize to every members of brilliant.Please forgive me
Very effective but not clear to me. Can you explain ?
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.
Problem Loading...
Note Loading...
Set Loading...
Group the numbers as such:
× × ⋅ ⋅ ⋅ × 1 0 0 ! ( 1 0 ) × ( 1 × 2 × 3 × … × 9 ) ( 1 1 × 1 2 × 1 3 × … × 1 9 ) ( 2 1 × 2 2 × 2 3 × … × 2 9 ) ( 9 1 × 9 2 × 9 3 × … × 9 9 )
Note the multifactorial notation.
Take modulo 1 0 for all the brackets:
= = = = 1 0 0 ! ( 1 0 ) × ( 9 ! ) 1 0 ( 1 0 0 × 9 0 × … × 1 0 ) × ( 9 ! ) 1 0 1 0 1 0 × 1 0 ! × ( 9 ! ) 1 0 1 0 1 1 × 9 ! × ( 9 ! ) 1 0 1 0 1 1 × ( 9 ! ) 1 1
Since we are only considering the last non-zero digit of 1 0 0 ! , we can ignore 1 0 1 1 . So we are left to find the last non-zero digit of ( 9 ! ) 1 1 .
9 ! = = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 ( 5 × 2 ) × 2 7 × 3 2 × 7
Take away all factors of 5 × 2 = 1 0 and we are finally left with a last digit that is non-zero.
We are left to compute ( 2 7 ⋅ 3 2 ⋅ 7 ) 1 1 ( m o d 1 0 ) .
Since we are only considering the very last number, we can reduce the powers by modular 4 .
( 2 7 ⋅ 3 2 ⋅ 7 ) 1 1 ≡ ≡ ≡ ≡ ≡ ( 2 7 m o d 4 ⋅ 3 2 ⋅ 7 ) 1 1 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