2
$\begingroup$

$x^2 + 3x +1 \equiv 0 \pmod{101}$. To solve this I found the determinant $D = 5 \pmod{101}$). Using the Legendre symbol,

$$\left(\frac{5}{101}\right) = \left(\frac{101}{5}\right) \equiv \left(\frac{1}{5}\right) \equiv 1,$$

$\therefore$ The equations have a solution.

My question is how I can find out how many solutions it has?

$\endgroup$
  • $\begingroup$ The solutions are $21$ and $77$ $\endgroup$ – MonsieurGalois Dec 7 '16 at 5:32
  • $\begingroup$ How did you get that solution? $\endgroup$ – Orland Dec 7 '16 at 5:42
  • 3
    $\begingroup$ Weeeeeeell.... Python. $\endgroup$ – MonsieurGalois Dec 7 '16 at 6:19
  • $\begingroup$ You need to find how many $k\in\mathbb{N}$ exist such that $5+404k$ is a perfect square. $\endgroup$ – barak manos Dec 7 '16 at 6:44
2
$\begingroup$

Since $$ (x-49)^2-77\equiv x^2+3x+1\pmod{101} $$ we are looking for solutions to $(x-49)^2\equiv77\pmod{101}$. You have verified that there is a root, so $77$ is a quadratic residue mod $101$, thus, there are two solutions for $$ (x-49)^2\equiv77\pmod{101} $$ Alternatively, working mod $101$, by squaring and multiplying $$ 77^2\equiv71\\ 77^3\equiv13\\ 77^6\equiv68\\ 77^{12}\equiv79\\ 77^{24}\equiv80\\ 77^{25}\equiv100\\ 77^{50}\equiv1 $$ Therefore, $77$ is a quadratic residue mod $101$. Thus, there are two solutions to $x^2+3x+1\pmod{101}$.

$\endgroup$
1
$\begingroup$

An idea to tackle this and similar questions using as small numbers and multiples of $\;101\;$ as possible (when possible, of course...).

Observe that $\;5=-96\pmod {101}\;$ , and $\;96=2^5\cdot3\;$ , so we can try to deal with these apparently easier numbers. Since we have $\;96=16\cdot6\;$, we have:

$$4^2=16=2^4\;,\;\;101\cdot2=202-6=196=14^2$$

and thus we have:

$$\;\sqrt{16}=4\;,\;\;\sqrt{-6}=14\implies \sqrt{16\cdot(-6)=-96}=4\cdot14=56$$

and thus also $\;\sqrt{-96}=-56=45\;$ , so $\;x^2=5\pmod{101}\implies x=\pm56=56,\,45\;$

Finally, your quadratic's solutions are ($\pmod{101}$ ):

$$x_{1,2}=\frac{-3\pm56}2=\begin{cases}\frac{98+56}2=77\\{}\\\frac{98-56}2=21\end{cases}$$

$\endgroup$
0
$\begingroup$

If the discriminant of a quadratic is a nonzero square modulo odd prime $p$, then the quadratic has exactly two roots mod $p$.

$\endgroup$
  • $\begingroup$ Okay, but with what I found with the Legendre Symbol, how can I find out that there is two roots. $\endgroup$ – Orland Dec 7 '16 at 5:59
  • 1
    $\begingroup$ @Orland: The quadratic formula tells you that the solutions are $$x=\frac{-3\pm\sqrt{D}}2.$$ There are no solutions in a domain of interest, if $D$ has no square root in that domain. There are two solutions if $D$ has a non-zero square root, and one double root if $\sqrt{D}=0$. The reasoning we all learned in school, relevant to the field of real numbers, applies to all fields where $2\neq0$. Legendre symbol tells you that there is a $\sqrt{5}\in\Bbb{Z}_{101}$. $\endgroup$ – Jyrki Lahtonen Dec 7 '16 at 7:09
0
$\begingroup$

For prime $p$: If $A$ is a square modulo $p,$ take any B such that $A\equiv B^2\pmod p.$ Then $$x^2\equiv A \pmod p\iff (x-B)(x+B)\equiv x^2-B^2\equiv 0 \pmod p\iff$$ $$\iff (\;p|(x-B)\lor p|(x+B)\;)\iff x\equiv \pm B \pmod p.$$ If $A\not \equiv 0 \pmod p,$ then $B\not \equiv 0\pmod p.$ If $p\ne 2,$ and $B\not \equiv 0 \pmod p$ then $B\not \equiv -B \pmod p.$ So for $p\ne 2$ and $A\not \equiv 0\pmod p$ there are, modulo $p,$ exactly $2$ solutions to $x^2\equiv A \pmod p,$ which are $x\equiv \pm B \pmod p.$

In your Q you are looking for solutions to $(2x+3)^2\equiv 5 \pmod {101}.$ Take any $B$ such that $B^2\equiv 5 \pmod {101}.$ Then $(2x+3)^2\equiv B^2 \iff 2x+3\equiv \pm B \pmod {101},$ which implies there exactly $2$ values, modulo $101$, for $x$.

$\endgroup$

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.