# Thread: Remainder Problem

1. ## Remainder Problem

I am stuck on this problem, I am trying to work out the largest possible remainder when 2015 is divided 1 or 2 or 3 ...up to 1000.
In other words, when 2015 is divided by 2 , it has a remainder 1, when divided by 5 its remainder is 0, when divided by 1000, its remainder is 15.
Which positive integer between 1 and 1000 gives the largest remainder and what is it?
I have tried pattern searching, prime factorising but no luck..

2. ## Re: Remainder Problem

2015 / 672 = 2 remainder 671

3. ## Re: Remainder Problem

how did you decide on 672?

4. ## Re: Remainder Problem

$2015 \div 1008= 1 \, \text{remainder} \, 1007$

I'd be very surprised if you can find a greater remainder.

Oops, up to 1000.

5. ## Re: Remainder Problem

Originally Posted by rodders
how did you decide on 672?
ceiling(2015 / 2) = 1008 (Archie's)
ceiling(2015 / 3) = 672 (mine)
ceiling(2015 / 4) = 504 ...next

YOKAY?

6. ## Re: Remainder Problem

Let $r_n$ denote the remainder when $2015$ is divided by $n$

Obviously $0\leq r_n\leq n-1$

The equation

$2015=n\left(\frac{2016}{n}-1\right)+(n-1)$

shows that

if $n$ is a divisor of $2016$ then $r_n=n-1$

Now $672$ is the largest divisor of $2016$ that is less than $1000$

and $r_{672}=671$

The proof is not complete. We need to check a few things.

7. ## Re: Remainder Problem

Here's a slight generalization of the original problem. At least this generalization can not be verified by a simple computer program. Maybe "watson" could prove it.