A nice application of the Chinese Remainder Theorem Claim: A set $ C$ is good iff there exists a prime number $ p$ such that for each remainder $ i=\overline{0,p-1}$ modulo $ p$, there exist $ 2$ different numbers in $ C$, both congruent to $ i\pmod p$. Proof: Assume firstly that such a prime number $ p$ exists for a set $ C$. Let $ a_i,b_i\in C$, $ i=\overline{0,p-1}$ such that $ a_i\neq b_i$ and $ a_i\equiv b_i\equiv i\pmod p$. Then for any integer $ k\equiv s\pmod p$, the numbers $ A=a_{-s}$ and $ B=b_{-s}$ (indices taken modulo $ p$) satisfy $ p|\gcd(k+A,k+B)$, proving that $ C$ is good. For the other direction, suppose we have a good set $ C$ and no such prime $ p$ exists. Let $ a-b=d$ be the greatest difference of two numbers from $ C$. Let $ 2=p_1<p_2<\ldots<p_t\le d<p_{t+1}<\ldots$ be the sequence of prime numbers. According to our assumpion for each $ i=\overline{1,t}$, there exists a remainder $ r_i$ upon $ p_i$ which is met at most one time among the numbers in $ C$. By the Chinese Remainder Theorem, the system of simultaneous equations $ x\equiv -r_i\pmod p_i$, for $ i=\overline{1,t}$ admits an integer solution (actually, infinitely many). Let $ k$ be a solution. Because $ C$ is a good set, there exist $ a\neq b\in C$ such that $ g=\gcd(k+a,k+b)\neq1$. Let $ q$ be a prime number dividing $ g$. Then $ q\le g\le d$ so $ q=p_j$, for some $ j=\overline{1,t}$. Then $ k\equiv-r_j\pmod q$. Because $ q|k+a$ and $ q|k+b$, we must have $ a\equiv b\equiv r_j\pmod q$. This is a contradiction to the choice of $ r_j$. Back to the problem: Since $ C$ is a good set, according to our claim, there exists a prime number $ p$ and pairwise different numbers $ a_0,\ldots,a_{p-1},b_0,\ldots,b_{p-1}$ such that $ a_i\equiv b_i\pmod p$. The sum $ S$ of these numbers is congruent to $ 2(0+1+\ldots+p-1)=(p-1)p\equiv0\pmod p$. It is clear that $ p<2003$. Because $ 2003$ is a prime number, $ 2003\neq S$, which means that $ C$ has at least one more element (which complete(s) the sum $ S$ till $ 2003$). Since the set $ C'=\{a_0,a_1,\ldots,a_{p-1},b_0,b_1,\ldots,b_{p-1}\}$ is good, any element of $ c\in C\setminus C'$ can be removed so that $ C-\{c\}$ is a good set.