<s>[INST] Does $x^2 \equiv 3$ (mod $q$) (where $q$ is an odd prime) have infinite solutions? Not sure how to prove/disprove this. One thought I had for proving this was doing an indirect proof, assuming there are only finitely many solutions $x_1,x_2,...,x_n$ and perhaps:
1) constructing a new solution using these solutions 
or 
2) taking the largest of the solutions and show an even larger solution exists 
 [/INST] There is an ambiguity in the question.  I address the version of the question "For how many primes $q$ does $x^2 \cong 3 \pmod{q}$ have a solution?"  (I ignore the other interpretation because either we recognize that $\mathbb{Z} / q \mathbb{Z}$ is a finite set of residue classes, so there are only finitely many classes which are solutions, or we realize that the solution classes each contain infinitely many integers.  Either way, the answer depends on the question I choose to address.)
You as whether $3$ is a quadratic residue modulo $q$.  It is known that $3$ is a quadratic residue modulo $q$ if $q \cong 1$ or $q \cong 11 \pmod{12}$ (excepting $q = 1$, which is not prime).  We use the Legendre symbol to represent quadratic character:
$$ \left( \frac{3}{q} \right) = \begin{cases} 0, \text{if $q$ divides $3$} \\+1, \text{if $3$ is a quadratic residue modulo $q$ and $q$ does not divide $3$}\\ -1, \text{if $3$ is a quadratic nonresidue modulo $q$ and $q$ does not divide $3$} \end{cases}  \text{.}  $$
This may be shown using quadratic reciprocity.  By quadratic reciprocity,\begin{align*}
    \left( \frac{3}{q} \right) \left( \frac{q}{3} \right) &= (-1)^{\frac{3-1}{2} \cdot \frac{q-1}{2}}  \\
    &= (-1)^{\frac{q-1}{2}}  \text{.}  \\
\end{align*}


*

*If $q \cong 0 \pmod{3}$, then $q$ is not prime and we exclude it from consideration, since the question concerns odd primes, $q$.

*If $q \cong 1 \cong 1^2 \pmod{3}$, then $\left( \frac{q}{3} \right) = +1$.  So
$$  \left( \frac{3}{q} \right) \left( \frac{q}{3} \right) = \left( \frac{3}{q} \right) = (-1)^{\frac{q-1}{2}}  \text{.}  $$  This last is $+1$ if and only if $q \cong 1 \pmod{4}$.  Putting the two congruences for $q$ together using the Chinese Remainder Theorem, $q \cong 1 \pmod{12}$.

*If $q \cong 2 \pmod{3}$, then $\left( \frac{q}{3} \right) = -1$.  So 
$$  \left( \frac{3}{q} \right) \left( \frac{q}{3} \right) = -\left( \frac{3}{q} \right) = (-1)^{\frac{q-1}{2}}  \text{.}  $$  Then $\left( \frac{3}{q} \right) = +1$ if and only if $q \cong 3 \pmod{4}$ and combining congruences gives $q \cong 11 \pmod{12}$.


We have hereby demonstrated the claim that $3$ is a quadratic residue modulo $q$ if $q \cong 1$ or $q \cong 11 \pmod{12}$.
Edit:
Occurred to me that there is one more, perhaps not obvious, fact to use.  Dirichlet's result on the distribution of primes among residue classes (also known as Dirichlet's theorem on arithmetic progressions) shows that there are infinitely many primes congruent to $1 \pmod{12}$ and congruent to $11 \pmod{12}$.  Therefore, there are infinitely many such primes $q$.
</s>