<s>[INST] $3x^2 ≡ 9 \pmod{13}$ What is $3x^2 ≡ 9 \pmod{13}$?
By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way?
I tried by stating that what the expression above says essentially means $13|(3x²-9)$, which only gives me more variables ($3x²-9=13k, k \in \mathbb{Z}$)
 [/INST] We have $13\mid 3(x^2-3)\iff 13\mid(x^2-3)$ as $(3,13)=1$ so, $x^2\equiv3\pmod {13}$.
Now, any number $x$ can be $\equiv 0,\pm1,\pm2,\pm3,\pm4,\pm5,\pm6 \pmod {13}$
So, $x^2\equiv 0,1,4,9,16(\equiv3),25(\equiv 12\equiv-1),36(\equiv10\equiv-3)\pmod {13}$
So, $x\equiv\pm4\pmod {13}$
For a larger prime, we can use Quadratic Reciprocity Theorem, to check the solutions exists or not before the trial as follows:
$$\left(\frac 3{13}\right)\left(\frac{13}3\right)=(-1)^\frac{(13-1)(3-1)}4=1$$
Now, $\left(\frac{13}3\right)=\left(\frac13\right)$ and $y\equiv\pm1\iff y^2\equiv1\pmod 3\implies \left(\frac{13}3\right)=1\implies \left(\frac{13}3\right)=1$ hence $3$ is a quadratic residue of $13$ and the given equation is solvable.
</s>