1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modulus Application Problem I think

  1. Feb 19, 2012 #1
    Hey all,
    I've been wondering about a few questions that seem to turn up a lot in math competitions—namely, what are the last 2 nonzero digits of some number x!. I've seen it a lot, and I'm wondering how one would go about solving that?
    I believe that one can use some modulus techniques to solve the problem, but I'm not well versed in those at all, so if someone could explain it to me, it would be greatly appreciated. Thank you!
     
  2. jcsd
  3. Feb 20, 2012 #2

    chiro

    User Avatar
    Science Advisor

    Hey Thundagere.

    The easiest may to think about this is to think about the modulus of a number.

    For this particular problem you want to find x! (MOD 100) since this will give you the remainder after you divide x! by 100 which is basically the last two digits.

    There is a whole area dedicated to things like this that relate to number theory in the way of congruence arithmetic and diophantine equations if you are interested in exploring more.
     
  4. Feb 20, 2012 #3
    But what about when it comes to something like 100!? Since every 5 and 2 make 10, every number 5 and above is going to add a 0. In that event, there are so many 0s that this wouldn't work to find the nonzero last digits. Is there another solution for that?
    Modular arithmetic definitely looks interesting. :)
     
  5. Feb 20, 2012 #4

    chiro

    User Avatar
    Science Advisor

    Once you get past a certain number, you don't have to worry about calculating anything since it doesn't change the first two decimal places.

    As an example calculate 5! vs 6! and 10! vs 11! and take note of what happens in terms of what values actually change.
     
  6. Feb 20, 2012 #5
    for the number of ending zeros in a factorial, its n/5 +n/25 +n/125 etc.
    for 100!, this would be 20 +4 = 24.
     
  7. Feb 20, 2012 #6
    ah... your question was about non-zero values, i apologize.
    unfortunately, i see no good way to approach this problem other than doing the factorial, dividing by the number of zeros, and taking mod 100.
     
  8. Feb 21, 2012 #7
    Hmmm....I think with these formulas, I can probably reason it out. At any rate, modular arithmetic is looking to be quite an interesting area to study next. Thanks!
     
  9. Feb 22, 2012 #8
    Just an update for anyone with similar question:
    I found a way to do it, however, it tends to get a tad tedious. Basically, using a method mentioned earlier, I listed out all the prime factors up to that number (using 15 as an example)
    15!
    2, 3, 5, 7, 11, 13

    Then I use the method mentioned, of 15/2 + 15/4 ... for all the numbers. This enables me to find the prime factorization.

    2^11 * 3^6 * 5^3 * 11 * 13

    I know that it's the 5 and 2 that makes the 0s. So I remove the three 5s and 3 of the 2s.

    2^8 * 3^6 * 11 * 13

    Now, it's a fairly simple matter to find the last few digits. One knows that 4 power eight will follow the 2, 4, 6, 8 ending digit pattern, so using simliar logic, the ending digits (the last few, anyhow) will be

    8 * 9 * 1 * 3
    Which ends up being
    216.
    Thus the last few digits are 216. I'm fairly certain I got it right. Thanks to everyone who helped me in this!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modulus Application Problem I think
Loading...