Finding last two non-zero digits of 2016!

1,039

Solution 1

Hints: I assume you are trying to find last two digits before the trailing zeroes. If you actually need the last two nonzero digits, then this method should also work (with small adjustments), albeit less effectively.

First hint:

You are trying to find the residue modulo $100$ of the number that remains after dividing by the maximal power of $10$.

Second hint:

Apply Chinese Remainder Theorem to deduce that it is enough to find the residue modulo $25$ (because the residue modulo $4$ will clearly be $0$).

Third hint:

Actually, it is enough to find the residues modulo $25$ of $24!$ and $16!$ divided by the largest powers of $10$ that divide them (or something of the sort, I haven't checked exactly), and then multiply appropriate powers of those residues.

Fourth hint:

To calculate those last residues, you can simplify the process a bit by working modulo $25$, but I can't think of any further simplification.

Solution 2

Let $k:=2016$. Write $k!=m5^n$ with $m\in\mathbb{Z}\backslash 5\mathbb{Z}$ so $n=102$. The prime factorisation of $M:=\frac{k!}{10^n}$ is here. Since $M\in\mathbb{Z}\backslash 5\mathbb{Z}$, the answer to your question is determined by $M$ modulo 100 (hereafter $\equiv$). Apparently the answer is 04, which we can prove by brute force (but I hope someone here knows a better way). Oh, wait; if that 0 in 04 is disallowed, we need to go to mod 1000 instead by much the same technique. A comment above noted that we get 704.

A few tricks speed it up. If $p$ is an odd prime dividing $M$, $p$ is co-prime to 100 so $p^{99}\equiv 1$ by Fermat's little theorem. For example, $3^{1004}\equiv 3^{14}\equiv 69$. The power-of-2 factor is harder, viz. $2^{1508}=2^{2^2\times 13\times 29}\equiv 12^{52} = 2^{104}$ (since $2^{29}\equiv 12,\,3^4\equiv 1$). Thus $2^{1508}\equiv (-8)^{8}=2^{24}\equiv 16$.

Share:
1,039

Related videos on Youtube

kornel19999999
Author by

kornel19999999

Updated on August 01, 2022

Comments

  • kornel19999999
    kornel19999999 over 1 year

    Find last two non-zero digits of 2016!

    I wasn't able to find anything which could help me. I need the method to solve it in the "mathematical" way, without computing the factorial itself.

    • MathematicsStudent1122
      MathematicsStudent1122 almost 8 years
      In order to improve your question, try providing more context! Also, clearly specify what sort of solution you would like; $2016!$ can be easily computed.
    • mrprottolo
      mrprottolo almost 8 years
      Since $2016!$ ends in $..704$, and then a string of zeros, is the answer $04$? or $74$?
    • kornel19999999
      kornel19999999 almost 8 years
      what difference does it make? In computing?
    • hmakholm left over Monica
      hmakholm left over Monica almost 8 years
      Where did you encounter this problem? Problems where the current year is treated like a mathematical integer are popular in contest mathematics (and rare otherwise), so if you pose such a problem without further explanation, people will tend to assume that you're participating in such a contest and seeking help with something it's your task to figure out on your own -- that is, cheating. (And given today's date that would almost certainly be a still ongoing contest).
    • mrprottolo
      mrprottolo almost 8 years
      @kornel1999 I don't know, it was to help clarify your question.
  • Erick Wong
    Erick Wong almost 8 years
    The third hint might require a little more care: the multiples of $5$ do contribute to the product, as do the multiples of $25$, $125$, $625$. This gives several more factorial-like terms to consider.
  • tomasz
    tomasz almost 8 years
    I don't think they exactly contribute, not directly, anyway: but they do take away the powers of $2$ (which are "sucked away" into powers of $10$), and that is the extent of their effect, as far as I can tell. Or do you have something else in mind?
  • Erick Wong
    Erick Wong almost 8 years
    I agree that $25$ doesn't contribute, but what about $75$?
  • Erick Wong
    Erick Wong almost 8 years
    Also, it's not obvious to me that $1\cdot 2\cdot \cdots \cdot 24$ is congruent to $26\cdot 27 \cdot \cdots \cdot 49$ mod $25$, after factoring out powers of $10$ (certainly they match before that, being both zero, but division by $5$ isn't well-defined... if there's an argument then it eludes me).
  • tomasz
    tomasz almost 8 years
    @ErickWong: Those are valid points. If you do come up with a better followup to second hint, feel free to edit or post your own answer. :)