# How do I find $999!$ (mod $1000$)?

I came across the following question in a list of number theory exercises

Find $999!$ (mod $1000$)

I have to admit that I have no idea where to start. My first instinct was to use Wilson's Theorem, but the issue is that $1000$ is not prime.

• Hint: $15!$ is divisible by $1000.$ – bof Sep 23 '16 at 6:53
• If that takes too much work, it is at least clear that $50!$ is divisible by $1000$. – Brian Tung Sep 23 '16 at 6:56
• Goodness I just thought of something simple that may work. $999!$ 'contains' inside it a '100' and a '10' inside it for sure. So whatever number we are left with is surely a multiple of $1000$. Hence the residue is $0$. Although a technique very much specific to this question, can somebody verify if this is valid? – Trogdor Sep 23 '16 at 7:08
• $999!$ is indeed divisible by $10!$ and by $100!$, but you need to show that it is also divisible by $10!\cdot100!$, which is a little less trivial (though not that difficult). In short, you can take every decomposition of $1000$ (except for $1\cdot1000$), and use it in order to prove that $1000$ divides $999!$. For example, $1000=500\cdot2$, and $999!$ is divisible by $502!$, which is equal to $500!\cdot501\cdot502$ and is therefore divisible by $500\cdot2$. In order to find the smallest factorial for which this holds, you need to use the prime factorization of $1000$. – barak manos Sep 23 '16 at 9:30

$1000=2\cdot2\cdot2\cdot5\cdot5\cdot5$

$2\cdot2\cdot2$ divides $2\cdot4\cdot6$ without remainder

$5\cdot5\cdot5$ divides $5\cdot10\cdot15$ without remainder

$2\cdot4\cdot6\cdot5\cdot10\cdot15$ divides $15!$ without remainder

$15!$ divides $999!$ without remainder

Therefore $1000$ divides $999!$ without remainder

What are you guys doing? Due to the fact that $500\times2 = 1000$ it follows trivially that $999!$ is congruent to $0 \space \text{(mod 1000)}$. Actually we know for certain that for every $x$ such that $x$ is lager than or equal to $500!$ it will always be the case that $x$ will be congruent to $0 \space \text{(mod 1000)}$.

Why? Because you can always rewrite the factorial as

$(500\times2)\times(\text{the remainding factors})$

thus,

$0\times(\text{the remainding factors}) = 0 \equiv 0 \space \text{(mod 1000)}$.

Short answer: $999!$ is a multiple of $10\cdot20\cdot30$.

For every occurrence of a multiple of 5 in the number you are building up to 999!, an additional zero becomes part of the ending sequence of digits of that number, never to leave again. Your question is tantamount to asking what the final three digits of 999! are. The first factorial to end in three zeroes, then and forevermore, is 15! . So, all following factorials will have the three zeroes. So, 000.