How would I determine whether $a^2-3b^2=0 \pmod 7$? By trying all values of $a$ and $b$ it is clear that this is only true for $a=b=0$, but I need a way to show this algebraically so that I can generalize to different values for 3 and 7.
If $b \ne 0 \pmod 7$, then it has an inverse (because 7 is prime). So you get $$(a/b)^2 = 3$$ But $3$ is not a square mod $7$, so this equation has no solutions.
Conversely, suppose $3$ were a square mod $7$, so there would exist $c$ such that $c^2 = 3$. Then you could just take $a=c$ and $b=1$.
So the solvability of $a^2 - kb^2 = 0 \pmod p$ depends only on whether $k$ is a square mod $p$ (in the jargon: $k$ is a quadratic residue mod $p$).
This Wikipedia article on the Legendre symbol shows you how to find out whether $k$ is a quadratic residue mod $p$ without having to try all the possibilities.