HMMT February

Number theory Difficulty 5.0 AIME, harder Find the answer

For positive integers $a$ and $N$ , let $r(a, N) \in\{0,1, \ldots, N-1\}$ denote the remainder of $a$ when divided by $N$ . Determine the number of positive integers $n \leq 1000000$ for which $r(n, 1000)>r(n, 1001)$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Note that $0 \leq r(n, 1000) \leq 999$ and $0 \leq r(n, 1001) \leq 1000$ . Consider the $\binom{1000}{2}=499500$ ways to choose pairs $(i, j)$ such that $i>j$ . By the Chinese Remainder Theorem, there is exactly one $n$ such that $1 \leq n \leq 1000 \cdot 1001$ such that $n \equiv i(\bmod 1000)$ and $n \equiv j(\bmod 1001)$ . Finally, it is easy to check that none of the $n$ in the range 1000001 to 1001000 satisfy the condition, so the answer is exactly 499500.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.