Two numbers $x$ and $y$ are chosen at random from the numbers $1,2,3,4,\ldots,2004$. The probability that $x^3+y^3$ is divisible by $3$ is? 
Two numbers $x$ and $y$ are chosen at random from the numbers $1,2,3,4,\ldots,2004$. The probability that $x^3+y^3$ is divisible by $3$ is?

The correct answer is $\dfrac13$ while mine is $\dfrac{445}{2003}$
My attempt:
For $x^3+y^3$ to be divisible by $3$, EITHER both $x$ and $y$ should be a multiple of $3$ OR one of them should leave remainder $1$ when divided by $3$ and the other should leave remainder $2$.
Therefore, $$\text{no. of ways} = \frac{668 \times 667 + 668\times 668}{2004\times 2003} = \frac{445}{2003}$$ 
 A: With replacement
As you basically note $x^3+y^3 \equiv x+y \pmod 3$, which follows from Fermat's Little Theorem.
We note that $2004 \equiv 0 \pmod 3$, so there's exactly $2004/3=668$ numbers equivalent to $i \pmod 3$, for all $i \in \{0,1,2\}$.
So, no matter what $x$ value is randomly chosen, there are $2004/3$ out of $2004$ (i.e., $1/3$ probability) of randomly choosing an $y$ value for which $y \equiv -x \pmod 3$.
We can do this like the method in the question:
$$
\frac{\overbrace{668 \times 668}^{x \equiv 0, y \equiv 0} + \overbrace{668 \times 668}^{x \equiv 1, y \equiv 2} + \overbrace{668 \times 668}^{x \equiv 2, y \equiv 1}}{2004^2}=\frac{1}{3}.
$$
Without replacement
If $x$ and $y$ are drawn without replacement, i.e., we assume $x \neq y$, then there's two distinctions: (a) when $x \equiv 0 \pmod 3$, there are $2004/3-1$ distinct $y$ values for which $x+y \equiv 0 \pmod 3$, and (b) there are $2004 \times 2003$ ordered pairs $(x,y)$, which also gives the probability:
$$
\frac{\overbrace{668 \times 667}^{x \equiv 0, y \equiv 0} + \overbrace{668 \times 668}^{x \equiv 1, y \equiv 2} + \overbrace{668 \times 668}^{x \equiv 2, y \equiv 1}}{2004 \times 2003}=\frac{1}{3}.
$$
To interpret this using the first method I mention, we have $1/3$ probability of any given value of $x \pmod 3$, and given a value of $x \pmod 3$, we have probability of either $667/2003$ (when $x \equiv 0 \pmod 3$) or $668/2003$ (when $x \not\equiv 0 \pmod 3$) of randomly choosing $y \equiv -x \pmod 3$.  Since these are mutually exclusive events, we get the probability
$$
\overbrace{\frac{1}{3} \times \frac{667}{2003}}^{x \equiv 0, y \equiv 0}+\overbrace{\frac{1}{3} \times \frac{668}{2003}}^{x \equiv 1, y \equiv 2}+\overbrace{\frac{1}{3} \times \frac{668}{2003}}^{x \equiv 2, y \equiv 1}=\frac{1}{3}.
$$
The given answer seems to assume that $x \neq y$, which is this second case.  However, the main problem is that it doesn't account for both cases $(x,y) \equiv (-1,1) \pmod 3$ and $(x,y) \equiv (1,-1) \pmod 3$.
A: It is immediate  (by using arithmetic progression) to get that there are equally $668$ numbers of residues $0,1,2$ modulo $3$. We have
$$(3n)^3+(3n)^3\equiv 0\pmod3\\(3n)^3+(3n+1)^3\equiv 1\pmod3\\(3n)^3+(3n+2)^3\equiv 2\pmod3\\(3n+1)^3+(3n+1)^3\equiv 2\pmod3\\(3n+1)^3+(3n+2)^3\equiv 0\pmod3$$
It follows$$\binom{668}{2}+668^2=669002\space\space\text{favorable cases.}\\\binom{2004}{2}=2007006\space\space\text{possibilities}$$
Thus the probability is $$\frac{669002}{2007006}=\frac13$$
