If we have $2$ numbers $x$ and $y$ such that $x\equiv y \equiv 0 \text{ or } 2\mod 4$, then $x$ and $y$ must be different colors. Thus, since there are $25$ numbers in each residue class, $n$ must be at least $25$. It is easy to see that $25$ is possible if we use a unique color for each pair of numbers $4k-2$ and $4k$ where $k$ is a positive integer less than or equal to $25$, and then select $2$ distinct colors that have already been used, one to color all the numbers $ x \equiv 1 \mod 4$ and one to color all the numbers $x \equiv 3 \mod 4$.