Mode of remainders

For any possible remainder $0 \le r \le 999$ , the number $1000$ gives remainder $r$ when divided by $1 \le n \le 1000$ exactly when $n > r$ and $n$ divides $1000 - r$ . Thus the frequency $f_r$ of the remainder $r$ is equal to the number of divisors of $1000 - r$ which are greater than $r$ .

Now $1000 - 10 = 990 = 2 \times 3^2 \times 5 \times 11$ has $2 \times 3 \times 2 \times 2 = 24$ positive divisors. Of these, $1,2,3,5,6,9,10$ are less than or equal to $10$ . Thus we deduce that $f_{10} = 17$ . We want to determine whether there are any other integers $0 \le r \le 999$ with $f_r \ge 17$ . Note that $1000 = 2^3 \times 5^3$ has $4\times4=16$ positive divisors, and so $f_{0} = 16$ . Also, since $999 =3^3 \times 37$ , we have that $f_1 = 4\times2 - 1 = 7$ .

Suppose now that $r \ge 60$ . If $1 \le m \le 1000$ is such that $m > r$ and $m$ divides $1000 - r$ , then $\frac{1000-r}{m} \; < \; \frac{1000 - r}{r} \; = \; \frac{1000}{r} - 1 \; \le \; \frac{1000}{60} - 1 \; < \; 16$ Thus the integer $\frac{1000-r}{m}$ can take at most $15$ values, which means that there are at most $15$ possible values of $m$ . In other words $f_r \le 15$ .

If $2 \le r \le 59$ and $f_r \ge 17$ then (since $1$ divides $1000 - r$ ) we must have that $1000 - r$ has at least $18$ positive divisors. There are only four numbers $2 \le r \le 59$ such that $1000 - r$ has $18$ or more positive divisors: $10,20,28,40$ .

• Note that $980 = 2^2 \times 5 \times 7^2$ , $980$ has $18$ positive divisors, but at least two of them ( $1$ and $2$ ) are less than or equal to $20$ . Thus $f_{20} < 17$ . In fact, $f_{20} = 10$ .
• Note that $972 =2^2\times3^5$ , $972$ has $18$ positive divisors, but at least two of them ( $1$ and $2$ ) are less than or equal to $28$ . Thus $f_{28} < 17$ . In fact, $f_{28} = 9$ .
• Note that $960 = 2^6 \times 3 \times 5$ , $960$ has $28$ divisors, but a total of $16$ of them are less than or equal to $40$ . These $16$ divisors are $1,2,4,8,16,32,3,6,12,24,5,10,20,40,15,30$ . Thus $f_{40} = 12$ .

Thus the mode is $\boxed{10}$ .

---

Alternatively, the Mathematica command:

Sort[Tally[Table[Mod[1000, n], {n, 1, 1000}]], #1[[2]] > #2[[2]] &][[1]]

yields

{10,17}

giving the same answer!

solution using C++ solution using Wolfram Mathematica solution using Python 3