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 
 A: 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$.
A: Everything is empirically apparent on that there are countless prime $q$ such that  $3$ is quadratic residue modulo $q$. Among the primes $q$ with two digits a calculation shows that for $5,7,17,19,29,31,41,43,53,67,79,89$ $3$ is not quadratic residue modulo $q$. On the contrary one has the following solutions for the other two digits primes:
$$x^2=3\pmod q$$
$$ \text{ For }11, x=5,6\\\text{ For }13, x=4,9\\\text{ For }23, x=7,16\\\text{ For }37, x=15,22\\\text{ For }47, x=12,35\\\text{ For }59, x=11,48\\\text{ For }61, x=8,53\\\text{ For }71, x=28,43\\\text{ For }73, x=21,52\\\text{ For }83, x=13,70\\\text{ For }97, x=10,87$$
We can see that $ 3 $ is square module $ q $ when $q\equiv{\pm1}\pmod {12}$.
Theoretically it can be shown with the law of quadratic reciprocity law and the so-called complementary formula for $ -1 $. which is usually of some difficulty for the beginner. In fact one has
$$\left(\frac 3q\cdot\frac q3\right)=\left(\frac {-3}{q}\right)\left(\frac {-q}{3}\right)\Rightarrow\left(\frac {3}{q}\right)=(-1)^{\frac{q-1}{2}}(-1)^{\frac{3-1}{2}}\left(\frac {q}{3}\right)=(-1)^{\frac{q+1}{2}}\left(\frac {q}{3}\right)$$ then to have positive sign we do both $q=4k\pm1$, for the exponent of $-1$, and $q=3l\mp 1$, for the Legendre symbol $\left(\dfrac {q}{3}\right)$ which produces $q\equiv{\pm1}\pmod {12}$
NOTE.-Strictly speaking, there are infinitely many primes $q$ because of  Dirichlet's theorem on arithmetic progressions  knowing that $q\equiv{\pm1}\pmod {12}$.
A: Assume that $q\equiv 1\pmod{12}$. The existence of infinite primes of this form is granted by Dirichlet's theorem. $-1$ is a quadratic residue $\!\!\pmod{q}$ and by Cauchy's theorem there is an element with order $3$ in $\mathbb{Z}/(q\mathbb{Z})^*$, which we may denote as $\omega$. Since
$$ \omega^2+\omega+1 \equiv 0\pmod{q} $$
we have
$$ (2\omega+1)^2 +3 \equiv 0\pmod{q} $$
hence $-3$ is a a quadratic residue $\!\!\pmod{q}$ and $3$ is a quadratic residue as well.
