Find all primes $p$ such that $ 3x^2-1\equiv 0 \mod{p}$ has a solution

Question

So I generally know how to do this for equations where $x^2$'s coefficient is $1$. Completing squares and then using quadratic reciprocity I can find that primes for which there are solutions depend on congruences modulo some number. But now I'm clueless on how to deal with that $3$.

Answer 1

As I post this, another answer claims that "there is no known law for all primes satisfying the question", and insinuates that it is impossible to say which primes will yield a solution. This claim is incorrect. The problem yields to a standard application of Quadratic Reciprocity.

You want to find out for which primes the congruence $$3x^2-1\equiv 0\pmod{p}$$ has a solution. The congruence clearly has a solution for $p=2$, and no solution for $p=3$, so we may assume that $p$ is odd and $p\gt 3$.

There are two ways to proceed here, both yielding the same conclusion: One, as Mark Bennet suggests, is multiplying through by $3$ (which is invertible modulo $p$). We then are looking at the congruence $9x^2\equiv 3\pmod{p}$, and since $9$ is a square, this has a solution if and only if $3$ is a square modulo $p$. So we want to find all odd primes $p$ for which $3$ is a quadratic residue.

Alternatively, we want to solve $3x^2\equiv 1\pmod{p}$. But since $3$ is a square modulo $p$ if and only if its multiplicative inverse modulo $p$ is a square modulo $p$ (if $3\equiv g^2\pmod{p}$, then $3^{-1}\equiv 3^{p-2}\equiv (g^2)^{p-2} = (g^{p-2})^2\pmod{p}$, and conversely) then again we are reduced to finding the odd primes $p\gt 3$ for which $3$ is a quadratic residue.

By Quadratic Reciprocity, we have $$\begin{align*} \left(\frac{3}{p}\right) &= \left\{\begin{array}{ll} \left(\frac{p}{3}\right) &\text{if }p\equiv 1\pmod{4},\\ -\left(\frac{p}{3}\right) &\text{if }p\equiv 3\pmod{4} \end{array}\right. \\ &= \left\{\begin{array}{ll} 1 &\text{if }p\equiv 1\pmod{4}\text{ and }p\equiv 1\pmod{3}\\ -1 &\text{if }p\equiv 1\pmod{4}\text{ and }p\equiv 2\pmod{3}\\ -1 &\text{if }p\equiv 3\pmod{4}\text{ and }p\equiv 1\pmod{3}\\ 1 &\text{if }p\equiv 3\pmod{4}\text{ and }p\equiv 2\pmod{3}. \end{array}\right. \end{align*}$$ Using the Chinese Remainder Theorem this gives the complete description: $$\left(\frac{3}{p}\right) = \left\{\begin{array}{ll} 1 & \text{if } p\equiv 1, 11 \pmod{12}\\ -1 &\text{if } p\equiv 5, 7 \pmod{12} \end{array}\right.$$

So your congruence has solutions if $p=2$, $p\equiv 1\pmod{12}$, or $p\equiv 11\pmod{12}$; and no solutions if $p=3$, $p\equiv 5\pmod{12}$, or $p\equiv 7\pmod{12}$.