Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mod100 of n! (nonzero)

  1. Feb 5, 2012 #1
    so I know how to get the 0s in n!, but how do I find the first 2 nonzero terms?
    Is there a shortcut?
    thanks :)
  2. jcsd
  3. Feb 5, 2012 #2


    User Avatar
    Science Advisor

    do you mean the 2 right-most non-zero digits?

    if so, that is not mod 100, unless you only have 2 "trailing 0's".

    it WILL be mod 10k for some k, but n! grows very quickly, and so unless n is between 10 and 14 (inclusive), k is not 2.
  4. Feb 5, 2012 #3
    hehe... that's why I said '2' first *nonzero* terms to n!
  5. Feb 5, 2012 #4


    User Avatar
    Science Advisor

    i understood what i thought you meant. but, realize the convention in english, is to parse left-to-right, so the first 2 digits of 5687 are 5 and 6, not 7 and 8.

    i don't think there is a general formula for all n, usually, finding the right-most non-zero digits of n! requires a fair amount of work (finding the number of 0's at the end is not so bad, you can count occurences of factors of 5 (since we get 5 even numbers for every 2 multiples of 5, the factors of 5 will be the limiting factor, here)).

    do you have a specific n! in mind?
  6. Feb 5, 2012 #5
    <random number generator> hmm, let's go with 109!
    and yeah my english sux :P also, that's interesting! hmm, so if I actually did mean the 'first' 2 digits of n!, that seems... way more work(?!) hehe, lemme try that out
  7. Feb 5, 2012 #6
    To find the last 2 non-zero digits before all the zeros at the end.

    factor n!, wich is easy, because it has [n/p] + [n/p^2] + [n/p^3] + ... factors of p.

    (where [x] is the largest integer, smaller or equal to x)

    remove all factors of 5, and an equal number of factors of 2, now multiply what is left together modulo 100, so you never have to multiply numbers with more than 2 digits.
  8. Feb 5, 2012 #7
    yuh... i knew that:)
    it's easy to say that.. but how do you 'multiply the numbers' when there are some 100s of them.. then simply modulo100 it :(
  9. Feb 6, 2012 #8


    User Avatar
    Science Advisor

    There are quite a lot of results in number theory that help you do these kinds of problems and also problems that are useful for doing this for really really large numbers (this kind of thing is common in cryptographic applications).
  10. Feb 6, 2012 #9
    ummm so like from this problem http://www.artofproblemsolving.com/Wiki/index.php/2010_AMC_10A_Problems/Problem_24 [Broken]
    I don't understand it from the M=(1*2*3*4)(6*7*8*9)...*(86*87*88*89).......................blabla
    yup :( enlightenments?
    Last edited by a moderator: May 5, 2017
  11. Feb 6, 2012 #10
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook