Find the number of solutions of the congruence equation
$y^2 = 3x^2-x-9$ (mod $109$)
My progress: Considering myself as a beginner to these type of complex problems in Number Theory, I wonder if there is non-brute force way to find the number of solutions of this congruence. Taking granted, my knowledge in such quadratic equations is pretty low, so any suggestion or related theorems/lemmas/methods would be welcomed! Thank you very much!
On
First, note that $109$ is prime. So, you want to know when $3x^2-x-9$ is quadratic residue mod $109$. There is a whole theory about quadratic residues mod $p$ prime (look for Legendre symbol).
For this particular problem, we first try to complete the square, we multiply the equation by 12 to try to complete squares in the right hand side (since 12 is coprime with 109, this equation is equivalent to the original one). We get: $$12y^2=36x^2-12x-108 \pmod{109}$$ Luckily, the right hand side is in fact a perfect square mod 109,
$$12y^2=36x^2-12x+1=(6x-1)^2\pmod{109}$$ So, you have $$3(2y)^2=(6x-1)^2\pmod{109}$$ If $y=0\mod 109$, then $6x-1=0\bmod 109$, so you get one solution $(x,y)=(91,0)\pmod{109}$
If $y\neq 0\bmod 109$, then that would imply that $3= [(6x-1)(2y)^{-1}]^2\bmod 109$, i.e. $3$ would be a quadratic residue mod $109$. Is this possible? Let's see, by quadratic reciprocity, we have $$\left(\frac{3}{109}\right)=\left(\frac{109}{3}\right)=\left(\frac{1}{3}\right)=1.$$ So, yes, 3 is a quadratic residue mod $109$. You will have two square roots of $3\pmod{109}$, say $a$ and $-a$.
So, you have $ (6x-1)(2y)^{-1}=a\pmod{109}$, which will give you 108 solutions (for each value of $y$, you have a unique value of $x$. And similarly $ (6x-1)(2y)^{-1}=-a\pmod{109}$, gives you another 108 solutions.
In total, you will get $1+108+108=217$ solutions $(x,y)$ mod $109$.
Edit
1)Whenever you want to complete squares an expression like this $S=mx^2+nx$ with $m,n$ integer. Multiply the expression by $4m$ (in fact you only need to multiply it by $m$ if $n$ is even). Because in that way, you would have $$4mS=4m^2x^2+4mnx=(2mx+n)^2-n^2$$. That's why in the problem we multiply the equation by $4(3)=12$, to make the completion of squares.
2) Note in this solution I never needed to compute a square root mod 109. Although, something to point out, that I already mentioned, is that we really really got lucky to have a perfect square on the right hand side. If this wasn't the case, say instead we got $3(2y)^2=(6x-1)^2+2\pmod{109}$, then this would be painful since we would need to find two quadratic residues ($3(2y)^2$ and $(6x-1)^2$ ) whose difference is $2$. And I don't really see a way to count the solutions in an easy way.
On
Without any magic: $\bmod 109\!:\ 3x^2\color{#c00}{-1}\,x\,\overbrace{-\,9}^{\large\color{#0a0}{ 10^2}} \equiv (ax+b)^2 \equiv a^2\, x+ \color{#c00}{2ab}\,x+\color{#0a0}{b^2}$
yields $\,\color{#0a0}{b^2\! \equiv 10^2},\,$ wlog $\,b\!\equiv\!10,\,$ so $\, \color{#c00}{2ab \equiv -1}\,$ $\Rightarrow\, 20b\equiv108\!\iff\! b \equiv \dfrac{27}5\equiv \dfrac{27\cdot 22}{110}\equiv \dfrac{49}1$
Further $\,a^2\equiv49^2\equiv 3\ $ so $\,a \equiv 49,\, b\equiv 10\,$ works. The rest is straightforward.
Usually you want to try something similar to completing squares. So some knowledge of quadratic residues/ reciprocity is helpful. In this case, observe that $p=109$ is prime and we can write \begin{align*} y^2 & = 3x^2-x-9 \pmod{109}\\ &=3x^2-x+\color{red}{100} \pmod{109}\\ &=\color{red}{(60)^2}x-x+100 \pmod{109}\\ y^2&=(60)^2x-\color{red}{1200}x+(10)^2 \pmod{109}\\ y^2&=(60x-10)^2 \pmod{109}. \end{align*} Using the prime property ($p | ab \implies p|a \text{ or } p|b$) we get $$y-60x+10 \equiv 0 \pmod{109} \text{ or } y+60x-10 \equiv 0 \pmod{109}.$$ Now you can count the solutions.