Try splitting the number

How many positive integers n n have the property that when 1,000,063 is divided by n n , the remainder is 63?


The answer is 37.

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.

2 solutions

1,000,063 = 1 0 6 10^6 + 63,

So if 1,000,063 number divided by other number(n) to get remainder =63,

The number should be multiple of 1 0 6 10^6 and must be greater than 63,

So as 1 0 6 10^6 = 2 6 2^6 . 5 6 5^6 ,

So number of divisors for 1 0 6 10^6 = 7(7) = 49.

now we have to exclude 1 , 2 , 4 , 5 , 8 , 16 , 32 , 10 , 20 , 25 , 40 , 50 1,2,4,5,8,16,32,10,20,25,40,50 (since they are greater than 63),

So we get total number of values of n = 49 - 12 = 37.

Nice solution. It makes it so simple in understanding the problem. Thank you for posting it.

Sathvik Acharya - 4 years ago

I thought the answer was 49. What I didn't realize was that there were twelve exclusions.

Rajdeep Ghosh - 4 years ago
Chew-Seong Cheong
May 20, 2017

1000063 63 ( m o d n ) 1000000 0 ( m o d n ) \begin{aligned} 1000063 & \equiv 63 \pmod {n} \\ \implies 1000000 & \equiv 0 \pmod {n} \end{aligned}

This means 1000000 1000000 is divisible by n n or n n is a factor of 1000000 1000000 . Since 1000000 = 2 6 5 6 1000000 = 2^6 5^6 , there are ( 6 + 1 ) ( 6 + 1 ) = 49 (6+1)(6+1) = 49 factors.

Out of these 49 factors, 1000063 m o d = { 63 n if n < 63 63 if n > 63 1000063 \mod = \begin{cases} 63-n & \text{if }n < 63 \\ 63 & \text{if }n > 63 \end{cases} .

Since factors smaller than 63 are 1, 2, 4, 8, 16, 32, and 5, 10, 20, 25, 40, 50, a total of 12. Therefore, the number of n n that gives a remainder of 63 is 49 12 = 37 49-12=\boxed{37} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...