0
$\begingroup$

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?

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

$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$.

$\endgroup$
  • 1
    $\begingroup$ @Killercamin: $\pmod{919}$ to write $\pm 242$ or $\pm 677$ is the same thing, since $242+677\equiv 0$. $\endgroup$ – Jack D'Aurizio Mar 28 '18 at 19:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Mar 28 '18 at 19:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Mar 28 '18 at 19:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Mar 28 '18 at 19:29
  • 1
    $\begingroup$ Similarly, $\gcd(29,86)=\gcd(29,28)=\gcd(1,28)=-1$ or simply $\gcd(29,86)=\gcd(29,-1)=1$. Your approach is fine. $\endgroup$ – Jack D'Aurizio Mar 28 '18 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.