For the last couple of days I have been trying to find a non brute-force method of solving the following equation where $a$ and $b$ are known integers. $$ (a+x^2) \bmod (b-x) = 0 \quad \text{such that $0\le x < b-1$} $$
Example: $$ (603+x^2) \bmod (622-x) =0 \quad \text{such that $0\le x < 621$} $$ The solution is $x=173$
My attempts to find an answer or even a similar solved question have not been successful. My knowledge of discrete mathematics is rusty at best, so I am not sure if non brute force method is even possible.
I am new here so if I have formatted wrong or done something incorrectly please let me know and I will fix it as soon as possible.
You can certainly reduce the brute force effort somewhat.
By using long division we can find that $$ x^2+a = -(b+x)(b-x) + (b^2+a) $$ and so applying $\mod (b-x)$ we get $$ x^2+a \mod (b-x) \equiv (b^2 +a) \mod (b-x)$$ This reduces your problem to finding $$ b^2+a \equiv 0 \mod (b-x)$$ which can be done by finding the prime factorisation of $b^2+a$ and determining which, if any, factors are strictly smaller than $b-1$.
This will work reasonably well for any numbers you can factorise quickly.