Library / /26 of 68

, 2017

Number theory Difficulty 5.0 AIME, harder Prove it United States

Problem:
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)$

Solution

Solution:
Answer: 499500
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 \pmod{1000}$ and $n \equiv j \pmod{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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.