Find the last three non-zero digits of $2015!$ .

**
Notation
**
:
$!$
denotes the
factorial
notation. For example,
$8! = 1\times2\times3\times\cdots\times8$
.

The answer is 544.

**
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.

Is this the only way to solve this

Praful Jain
- 5 years ago

Log in to reply

Actually it is not so complex, I just used 3-4 concepts that are at the base of modular arithmetic. The rest is logical reasoning. The solution looks ugly because I had to explain what I thought in my mind to solve it. For the "mathematical" part there is not much to say. However I advise you to read something about Euler phi function and Chinese remainder theorem because there is where I learnt how to solve these kind of problems.

Alex Spagnoletti
- 5 years ago

Log in to reply

Thank you for the advice sir, I'll do so for my next solutions.

Alex Spagnoletti
- 5 years ago

I dont understand this complex mathematics

Praful Jain
- 5 years ago

Let’s define the function: A(n) which removes all trailing zeros from n. Example: A(120) = 12, A(1200003) = 1200003 and A(46900) = 469 and so on. We want to find (A(2015!)) mod 1000.

Let’s also define D(0) = 1 X 2 X 3 X 4 X 6 X 7 X 8 X 9, D(1) = 11 X 12 X 13 X 14 X 16 X 17 X 18 X 19, D(2) = 21 X 22 X 23 X 24 X 26 X 27 X 28 X 29, and in general: D(n) = (10n + 1) X (10n + 2) X (10n + 3) X (10n + 4) X (10n + 6) X (10n + 7) X (10n + 8) X (10n + 9) It can easily be shown that: D(n) mod 1000 = D(n mod 1000)

Since 2015! = 1 X 2 X 3 X 4 …. X 2011 X 2012 X 2013 X 2014 X 2015. Let’s separate the multiples of 5 together.

2015! = (1 X 2 X 3 X 4 X 6 X 7 X 8 X 9) X (11 X 12 X 13 X 14 X 16 X 17 X 18 X 19) X … X (2001 X 2002 X 2003 X 2004 X 2006 X 2007 X 2008 X 2009) X (2011 X 2012 X 2013 X 2014 X (5 X 10 X 15 X 20 X 25 X 30 X … X 2000 X 2005 X 2010 X 2015)

2015! = D(0) X D(1) X D(2) X … D(200) X (2011 X 2012 X 2013 X 2014) X (5 X 10 X 15 X 20 X 25 X 30 X … X 2000 X 2005 X 2010 X 2015)

2015! = D(0) X D(1) X D(2) X … D(200) X (2011 X 2012 X 2013 X 2014) X 5^403 X (1 X 2 X 3 X 4 X 5 X … 403)

2015! = D(0) X D(1) X D(2) X … D(200) X (2011 X 2012 X 2013 X 2014) X 5^403 X 403! (1)

In the same way, we can develop 403! 403! = D(0) X D(1) X D(2) X … D(39) X (401 X 402 X 403) X 5^80 X 80! (2)

In the same way, we can develop 80! 80! = D(0) X D(1) X D(2) X … D(7) X 5^16 X 16! (3)

In the same way, we can develop 16! 16! = D(0) X (11 X 12 X 13 X 14 X 16) X 5^3 X 3! (4)

From 1, 2, 3, 4 we get:

2015! = (D(0) X D(1) X D(2) X … D(200)) X (D(0) X D(1) X D(2) X … D(39)) X (D(0) X D(1) X D(2) X … D(7)) X D(0) X 5^502 X (2011 X 2012 X 2013 X 2014) X (401 X 402 X 403) X (11 X 12 X 13 X 14 X 16) X 6 (5)

Let us define E(n) = D(n) mod 1000 E(n) = ((10n + 1) X (10n + 2) X (10n + 3) X (10n + 4) X (10n + 6) X (10n + 7) X (10n + 8) X (10n + 9)) mod 1000 E(n) = ((10n + 1) X (10n + 9) X (10n + 2) X (10n + 8) X (10n + 3) X (10n + 7) X (10n + 4) X (10n + 6)) mod 1000 E(n) = ((100n2 + 100n + 9) X (100n2 + 100n + 16) X (100n2 + 100n + 21) X (100n2 + 100n + 24)) mod 1000 E(n) = ((100n2 + 100n + 9) X (100n2 + 100n + 16)) mod 1000 X ((100n2 + 100n + 21) X (100n2 + 100n + 24) mod 1000) mod 1000 E(n) = ((500n2 + 500n + 144) mod 1000 X ((500n2 + 500n + 504) mod 1000) mod 1000 E(n) = 144 X 504 mod 1000 = 576 (6)

From 5 and 6: A(2015!) mod 1000 = A((576 ^ (201 + 40 + 8 + 1) mod 1000 X 5^502 X (2011 X 2012 X 2013 X 2014) X (401 X 402 X 403) X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

A(2015!) mod 1000 = A((576 ^ 250) mod 1000 X 5^502 mod 1000 X (2011 X 2012 X 2013 X 2014) mod 1000 X (401 X 402 X 403) mod 1000 X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

A(2015!) mod 1000 = A(376 X 5^502 mod 1000 X (11 X 12 X 13 X 14) mod 1000 X (401 X 402 X 403) mod 1000 X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

A(2015!) mod 1000 = A(376 X 5^502 X 24 X (406) X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

It can be easily shown that if n is a multiple of 8 then : (376 X n) mod 1000 = n mod 1000

A(2015!) mod 1000 = A(5^502 X 24 X 406 X 6 X (11 X 12 X 13 X 14 X 16)) mod 1000

A(2015!) mod 1000 = A(5^502 X 464 X 11 X 12 X 13 X 14 X 16) mod 1000

A(2015!) mod 1000 = A(5^502 X 104 X 12 X 13 X 14 X 16) mod 1000

A(2015!) mod 1000 = A(5^502 X 248 X 13 X 14 X 16) mod 1000

A(2015!) mod 1000 = A(5^502 X 224 X 14 X 16) mod 1000

A(2015!) mod 1000 = A(5^502 X 136 X 16) mod 1000

A(2015!) mod 1000 = A(5^502 X 136 X 16) mod 1000

A(2015!) mod 1000 = A(5^502 X 176) mod 1000 (11)

Since 2^100 mod 1000 = 376 Then 2^600 mod 1000 = 376

In 11:
A(2015!) mod 1000 = A(5^502 X 176 X 2^600) mod 1000

A(2015!) mod 1000 = A(10^502 X 176 X 2^98) mod 1000

A(2015!) mod 1000 = (176 X 2^98) mod 1000

Since 2^80 mod 1000 = 176, 2^10 mod 1000 = 24, 2^8 mod 1000 = 256,

2^98 mod 1000 = (176 X 24 X 256) mod 1000 = 344
A(2015!) mod 1000 = (176 X 344) mod 1000 = 544

1 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

Relevant wiki: Factorials Problem Solving - IntermediateFirst we can find the number of trailing zeros of $2015!$ . Which is 502. $\lfloor \dfrac{2015}{5}\rfloor + \lfloor \dfrac{2015}{25}\rfloor + \lfloor \dfrac{2015}{125}\rfloor + \lfloor \dfrac{2015}{625}\rfloor = 502$ . Now Let $M$ be $\dfrac{2015!}{5^{502}}$ and $N$ be $\dfrac{M}{2^{502}}$ .We want to find $N \pmod{1000}$ .

Let's start with $M \pmod {1000}$ which can be reduced to the separated calculus of $M \pmod 8$ and $M \pmod {125}$ thanks to Chinese Remainder Theorem.

We can notice that $\dfrac{2015!}{5^{502}}=1\times2\times3\times4\times1\times6\times7\times8\times9\times2\times11\times12\times13\times\ldots$

So $M \pmod 8$ is obviusly $\equiv 0$ so now we have to find $M \pmod {125}$ .

There is a nice pattern in that, $1\times2\times3\times4 \equiv 6\times7\times8\times9 \equiv \ldots \equiv 24 \pmod{125}$ . So we have $24^{403}$ (there are 403 repetition), now we can notice that we have the same pattern repeted for those factors which are in the form $5k$ . So There are $24^{80}\times 401\times402\times403$ <--the last 3 terms are "extra" so we have to count them apart.

Now there is the same pattern for those terms $5^2k$ so there is $24^{16}$ , then for those terms $5^3k$ there is $24^{3}$ and at the end we have $1\times2\times3\times16$ which is the last pattern with 3 factor of the form $5^4k$ and the last factor $=16$ . How rewriting everything we have $24^{403}\times24^{80}\times24^{16}\times24^{3}\times31\times6\times16$ using properties of powers $24^{502}\times31\times6\times16$ and we have to calculate it $\pmod{125}$ and using $\phi(125)=100$ that is equal to $24^2\times101$ that can be easily calculate and it is $51\pmod{125}$ . Applying CRT we have $\begin{cases} M \equiv 0 \pmod 8 \\ M \equiv 51 \pmod{125} \end{cases}$ . So $M\equiv 176 \pmod{1000}$ .

About $2^{502}$ It is thanks to $\phi$ $\equiv 4 \pmod {125}$ and applying CRT to calculate last 3 digits we have $\begin{cases} 2^{502} \equiv 0 \pmod 8 \\ 2^{502} \equiv 4 \pmod{125} \end{cases}$ . So it is $504$ .

Now $\dfrac{M}{2^{502}}$ can be rewritten as $\dfrac{176}{504} \pmod{1000}$ . Applying another time CRT we have $\begin{cases} \dfrac{176}{504} \equiv 0 \pmod 8 \\ \dfrac{176}{504} \equiv \dfrac{51}{4} \pmod{125} \end{cases}$

For the second one we can multiply by 4 obtaining $4X \equiv 51 \pmod{125}$ . the $inv_{125}(4)=94$ <--we can obtain it solving an easy diophantine $4j-125k=1$ .

$94\times4X \equiv 94\times51 \pmod{125} \implies X\equiv 44 \pmod{125}$

Last thing is to solve this CRT system:

$\begin{cases} X \equiv 0 \pmod 8 \\ X \equiv44 \pmod{125} \end{cases}$ .

And the solution is $X\equiv 544 \pmod{1000}$