We show that the smallest possible $a$ works. Let $n= \lfloor \sqrt p \rfloor$. If $n^2+1=p$, then we set $a=p-(n-1)^2=n^2+1-n^2+2n-1=2n$ and $b=p-1^2=n^2$. This works, because surely $p$ is odd, so $2|n$ giving $a=2n|n^2=b$. In all other cases we can set $a=p-n^2>1$. There are three cases: a) $n^2+n > p$: Then we set $c=n^2+n-p>0$. Additionally $n^2 < p$ gives $c=n^2-p+n<n$. b) $n^2+n=p$: this implies $n|p$, impossible. c) $n^2+n < p$: Then we set $c=p-n^2-n>0$. Additionally $p < (n+1)^2$ gives $c=p-n^2-n=p-(n+1)^2+n+1<n+1$. If $c=n$, then we would have $n=p-n^2-n$ giving $n|p$, impossible. So again $c<n$. In all possible cases, we now set $b=p-c^2$ and get $b=p-c^2 \equiv p- (\pm n)^2 \equiv p-n^2 \equiv 0 \mod (p-n^2)$, being the result.

Let $[\sqrt p]=k$. Now let $p=k^{2}+x$ where $x\leq 2k+1$.Hence $x \in S$. Now consider the number $|k-x|$.So $|k-x|<\sqrt p$. Now let $b=p^{2}-|k-x|^{2}$. We see that $x|b$.Hence we are done. Excuse me for my bad english.