2
$\begingroup$

how to solve $\pm y \equiv 2x+1 \pmod {13}$ with Chinese remainder theorem or iterative method?

It comes from solving $x^2+x+1 \equiv 0 \pmod {13}$ (* ) and background is following:

13 is prime. (* ) holds under Euclidean lemma if and only if $4(x^2+x+1) \equiv \pmod {13}$ or if and only if $(2x+1)^2 \equiv -3 \pmod {13}$. So if $p=13$, so by Euler's criterion $[ \frac{-3}{13} ] \equiv (-3)^{\frac{13-1}{2}} = (-3)^6 = 9^3 \equiv (-4)^3 =-64 \equiv 1 \pmod{13} $. Hence equation $y^2 \equiv -3 \pmod{13}$ has two incongruent solution( lemma 4.1.3) $\pm y$ so solutions of the equations $\pm y \equiv 2x+1 \pmod{13}$ are solutions of the equation (* ) So my most important question is how you change equation $\pm y \equiv 2x+1 \pmod{13}$ to the form $ax\equiv b \pmod{13} $ in other words to the form where you can use either Chinese remainder theorem or iterative method to solve $\pm y \equiv 2x+1 \pmod{13}$ and finally (* )? Finally just because of curiosity. Is $[\frac{-3}{7}]\equiv (-3)^3 = -27 \equiv -1 \pmod{7}$? So is mod(-27,7)=1 or -1?

  • 0
    Is $[\frac{-3}{7}]$ meant to be the Legendre symbol of $-3$ modulo $7$? Since $-3 \equiv 4 =2^2\pmod{7}$, then $-3$ is a square modulo $7$ ($2^2\equiv 5^2\equiv -3\pmod{7}$), so $(\frac{-3}{7})=1$ (this can also be obtained via quadratic reciprocity, since $(\frac{-1}{7})=-1$ as $7\equiv 3\pmod{4}$, and $(\frac{3}{7}) = -(\frac{7}{3}) = -(\frac{1}{3}) = -1$. Note that $-27 \equiv -(-1) \equiv 1\pmod{7}$, so your final computation is incorrect.2011-11-26

2 Answers 2

1

To solve $x^2 + x + 1 \equiv 0 \pmod{13}$, you can use the usual quadratic formula, interpreted appropriately. The solutions are given by $x = \frac{-1 \pm\sqrt{-3}}{2},$ where "$\sqrt{-3}$" means an integer $y$ such that $y^2\equiv -3\pmod{13}$, and "$\frac{1}{2}$" means an integer $z$ such that $2z\equiv 1\pmod{13}$.

The latter is easy: $z\equiv 7\pmod{13}$ does the job.

For the latter, you need $-3$ to be a quadratic residue modulo $13$; it is, because $3\equiv 4^2\pmod{13}$, and $-1\equiv 5^2\pmod{13}$, so $4\times 5 = 20\equiv 7\pmod{13}$ does the trick; indeed, $7^2 = 49 \equiv -3\pmod{13}$.

So the two solutions to $x^2+x+1\equiv 0\pmod{13}$ are: $x= (2)^{-1}(-1+\sqrt{-3}) \equiv 7(-1+7) = 7(6) = 42 \equiv 3\pmod{13}$ and $x= (2)^{-1}(-1-\sqrt{-3}) \equiv 7(-1-7) = 7(-8) = -56 \equiv 9\pmod{13}.$

You can verify this easily: $\begin{align*} 3^2 + 3 + 1 &= 9+3+1 = 13\equiv 0\pmod{13},\\ 9^2+9+1&=81+9+1 = 91=13\times 7\equiv 0\pmod{13}. \end{align*}$

If you want to go your route, you are trying to find values of $x$ such that $(2x+1)^2\equiv -3\pmod{13}$. That means finding the two square roots of $-3$ modulo $13$; as above, they are $7$ and $-7\equiv 6$, so you are looking for the values of $x$ such that $2x+1\equiv 7\pmod{13}$ and $2x+1\equiv 6\pmod{13}$. These translate to $2x\equiv 6\pmod{13}$ and $2x\equiv 5\pmod{13}$. We can solve these by multiplying both sides by $7$ (the multiplicative inverse of $2$), so we get $x\equiv 7(6) = 42\equiv 3\pmod{13}\qquad\text{and}\qquad x\equiv 7(5) = 35 = 9\pmod{13},$ the same answers as above.

I don't know why you are trying to find $\pm y\equiv 2x+1\pmod{13}$. This does not give you what you want.

0

Either, $\pm y-1$ is divisible by 2, so you divide by 2, or $\pm y+12$ is divisible by 2, so divide this by 2.