# Determine whether $x^2 \equiv 667\pmod{919}$ has solutions.

Determine whether $x^2 \equiv 667\pmod{919}$ has solutions.

I'm not asking for an answer since I really want to figure this out, but researching and I can't find anything. Almost every example I find is that a is a perfect number such that $(x-a)(x+a)$, but in here The factors of $667$ are $1,23,29,667$ and $919$ is prime. Any links or hints to get me going?

• Look up Law of Quadratic Reciprocity. – Rene Schipperus Mar 28 '18 at 18:49
• Will do thanks. – Killercamin Mar 28 '18 at 18:50
• try it with $x=242$ or $x=677$ – Dr. Sonnhard Graubner Mar 28 '18 at 18:55
• I see that both of them are solutions, but how did you approach them? – Killercamin Mar 28 '18 at 19:10
• Wikipedia has an article on Quadratic Residues – steven gregory Mar 28 '18 at 19:10

$919$ is a prime $\equiv 3\pmod{4}$ and by the quadratic reciprocity theorem the Legendre symbol $\left(\frac{667}{919}\right)$ can be computed as follows: $$\left(\frac{667}{919}\right)=\left(\frac{23}{919}\right)\left(\frac{29}{919}\right)=-\left(\frac{-1}{23}\right)\left(\frac{20}{29}\right)=\left(\frac{5}{29}\right)=\left(\frac{-1}{5}\right)=+1$$ hence $x^2\equiv 667\pmod{919}$ has two solutions, namely $\pm242$.
• @Killercamin: $\pmod{919}$ to write $\pm 242$ or $\pm 677$ is the same thing, since $242+677\equiv 0$. – Jack D'Aurizio Mar 28 '18 at 19:14
• In $\mathbb{F}_{919}$ the polynomial $x^2-667$ cannot have more than two roots, since $\mathbb{F}_{919}$ is a field (a finite field, but still a field). An if $\alpha$ is a root then $-\alpha$ is also a root, obviously. – Jack D'Aurizio Mar 28 '18 at 19:15
• @Killercamin: if $p$ is a prime and $p\nmid a$, $\left(\frac{a}{p}\right)=+1$ iff $a$ is a quadratic residue $\pmod{p}$, i.e. if there is some $x\in\mathbb{F}_p$ such that $x^2\equiv a\pmod{p}$, correct. – Jack D'Aurizio Mar 28 '18 at 19:28
• Of course the computation of $\left(\frac{a}{p}\right)$ can be performed in many ways, by exploiting quadratic reciprocity / the multiplicativity of Legendre symbol at each step, but the final outcome has to be the same. – Jack D'Aurizio Mar 28 '18 at 19:29
• Similarly, $\gcd(29,86)=\gcd(29,28)=\gcd(1,28)=-1$ or simply $\gcd(29,86)=\gcd(29,-1)=1$. Your approach is fine. – Jack D'Aurizio Mar 28 '18 at 19:31