Hunt For The Last 3

Find the last three digits of the number

3 × 7 × 11 × 15 × × 2003. 3 \times 7 \times 11 \times 15 \times \cdots \times 2003.


The answer is 875.

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.

3 solutions

Discussions for this problem are now closed

Pi Han Goh
May 13, 2014

Chinese Remainder Theorem should do the trick.

Because 15 , 35 , 55 15,35,55 are some of the terms being multiplied. Then the expression is divisible by 5 3 5^3 .

Consider modulo 8 8 , we have 3 1 3 1 1 3 3 ( 3 ) 250 3 3 250 3 ( 3 2 ) 125 3 3 \cdot -1 \cdot 3 \cdot -1 \cdot \ldots \cdot -1 \cdot 3 \equiv 3 \cdot (-3)^{250} \equiv 3 \cdot 3^{250} \equiv 3 \cdot (3^2)^{125} \equiv 3 .

So the last three digits satisfy the linear congruence x 0 ( m o d 125 ) , x 3 ( m o d 8 ) x \equiv 0 \pmod{125}, x \equiv 3 \pmod{8} , which gives 875 \boxed{875}

I think it should be 3 X -1 X 3 X 3 as you have taken 5 common from 15

Varun Vijay - 7 years, 1 month ago

I don't get which series it was. Was it a series of odd numbers? then why 9 is not in the series and if it is the series of prime numbers then why 15 is in the series??

vivek sedani - 7 years ago

The picture with Chinese writings too give an uncanny clue about the answer. :)

Krishna Ar - 7 years ago

Can you hunt for the 9 digits in the image? Number 8 is white an in the lower right corner.

Calvin Lin Staff - 7 years ago

I just realised 0.o

Joshua Ong - 7 years ago

Any one plz explain me clearly I cant understand

Chandru Athiyappan - 7 years ago

When it says they want to find the last 3 digits, it means m o d 1000 \bmod {1000}

You can read up what Chinese Remainder Theorem here

The prime factorization of 1000 1000 is 2 3 × 5 3 2^3 \times 5^3 , with 2 3 = 8 , 5 3 = 125 2^3 = 8, 5^3 = 125

Apply the properties of modular arithmetic:

( x 1 x 2 x 3 x n ) m o d M ( ( x 1 m o d M ) ( x 2 m o d M ) ( x 3 m o d M ) ( x n m o d M ) ) m o d M ( x_1 \cdot x_2 \cdot x_3 \cdot \ldots \cdot x_n ) \bmod{M} \equiv \left ( (x_1 \bmod {M}) \cdot (x_2 \bmod {M}) \cdot (x_3 \bmod {M}) \cdot \ldots \cdot (x_n \bmod {M}) \right ) \bmod {M}

Note that the remainder when divided by 8 8 for 3 , 7 , 11 , 15 , , 2003 3,7,11,15,\ldots,2003 yields 3 , 7 , 3 , 7 , , 3 3,7,3,7, \ldots, 3 respectively

Because 7 1 m o d 8 7 \equiv -1 \bmod{8} , we can rewrite them as 3 , 1 , 3 , 1 , , 3 3,-1,3,-1, \ldots, 3 . With 250 250 of 1 -1 's and 251 251 of 3 3 's. So the remainder of the expression when divided by 8 8 is simply ( 1 ) 250 3 251 1 3 3 250 3 ( 3 2 ) 125 3 ( 9 m o d 8 ) 125 3 1 3 (-1)^{250} \cdot 3^{251} \equiv 1 \cdot 3 \cdot 3^{250} \equiv 3 \cdot (3^2)^{125} \equiv 3 \cdot (9 \bmod 8)^{125} \equiv 3 \cdot 1 \equiv 3

And it's explained above why the expression is divisible by 5 3 = 125 5^3=125 , so the expression satisfy the linear congruences x 3 ( m o d 8 ) x \equiv 3 \pmod{8} and x 0 ( m o d 125 ) x \equiv 0 \pmod{125} , which gives the answer 875 875

Pi Han Goh - 7 years ago

Thanks you very much

Chandru Athiyappan - 7 years ago

i didnt get it can u please brief me about the method

Allaka Surya Prakash - 7 years ago

What is Chinese remainder theorem explain in detail

Navin Kumar - 7 years ago
Sunil Pradhan
May 19, 2014

the series 3, 7, 11, 15, 19 is repeated. Last number is 2003 find total numbers in the series

Tn = a + (n – 1)d

= 2003 = 3 + (n – 1) × 4 gives n = 665.6

i.e (3, 7, 11, 15, 19) repeated for 665 tins and last digit is 3

so to find Last 3 digits of (3 × 7 × 11 × 15 × 19)^665 × 3

(3 × 7 × 11 × 15 × 19)^3 gives last 3 digits as 625 and 625^n always gives last 3 digits as 625

so required answer is last 3 digits of 625 × 3 = 1875 i.e. 875

Ng Fung
May 19, 2014

Can anyone give me another much simplified solution as I have zero knowledge on mod/Chinese Remainder Theorem

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...