Part $a)$: Replace $2018$ by $n$, and solve for general case. Consider the sets, $S_1=\{a^2:0\leq a\leq p-1\}$, and $S_2=\{-n-b^2:0\leq b\leq p-1\}$ (as subsets of $\mathbb{Z}_p$). Clearly, $|S_1|=|S_2|=\frac{p+1}{2}$. Hence, if they are disjoint, then $p\geq |S_1\cup S_2|=|S_1|+|S_2|=p+1$, a contradiction. Thus, they must have a common member, that is, there exists $a,b,n_0$ such that, $a^2\equiv n_0\equiv -n-b^2\pmod{p}$, and thus, $a^2+b^2+n\equiv 0\pmod{p}$. Part $b)$: Check quickly that if $p=2$, then $a=b=1$ works, also if $p=1009$ then $p\equiv 1\pmod{4}$, hence, $b^2\equiv -1\pmod{p}$ is solvable, and thus taking $a=1$ and $b$ such that $b^2\equiv -1\pmod{p}$ shows existence of such guys. We now continue the discussion from above. We have established that $|S_1\cap S_2|\geq 1$. Next, let us investigate when $0\in S_1\cap S_2$. Note that, $0\in S_2 \iff b^2\equiv -n\pmod{p}$ is solvable. In particular, if $-n$ is not a quadratic residue in modulo $p$, the element in the intersection will clearly not be $0$, hence there exists $a,b$ such that $p\nmid a,b$ and $p\mid a^2+b^2+2018$. The only case remaining is to study what happens when $-2018$ is a quadratic residue in modulo $p$, and $(p,2018)=1$. I have a partial result that if $2$ is a quadratic residue, then one can obtain $-1009$ is also quadratic residue, thus by taking $a^2\equiv b^2\equiv -1009\pmod{p}$, we can conclude. There also primes $p=3$ such that one must have either $a$ or $b$ to be divisible by $3$. Would be happy if one can finish my argument. Edit: Here is the final line, using Assassino9931's suggestion. We have already proven that for primes $p$ where $-2018$ is not is a quadratic residue, how to handle the case. Now for $p=5$, observe that $a,b\equiv 1\pmod{5}$ shows that the job can be done. Hence, assume $p\neq 5$, in particular, $5$ has an inverse in modulo $p$. Using the Pythagorean triple, $(3,4,5)$ we have that $(3\cdot 5^{-1})^2 +(4\cdot 5^{-1})^2 \equiv 1\pmod{p}$. Now let $n_0$ be such that $n_0^2\equiv -2018 \pmod{p}$. We conclude, by taking $a\equiv 3\cdot 5^{-1}\cdot n_0\pmod{p}$, and $b\equiv 4\cdot 5^{-1}\cdot n_0\pmod{p}$ (clearly, $p\in \{2,3,5,1009\}$ are excluded, hence, $a,b\not\equiv 0\pmod{p}$). Hence, except $p=3$, the job can be done for every prime $p$.

I was stuck on b) and I found out that $p=3$ is the only number for which one of $a$ and $b$ is divisible by 3, but I couldn't prove it as well.

Just write x^2 = (3mx)^2 + (4mx)^2 where m is the inverse of 5 mod p; be sure to check the prime divisors of 2018, as well as p = 2, 3 separately.