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

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?

-
What book are you citing? Where is lemma 4.1.3? – Dimitrije Kostic Nov 26 '11 at 16:57
Curiosity first: $-27=(-28)+1$. The congruence $2x+1\equiv \pm y \pmod{13}$ look to be of the right form already if you know $y$, except for the tiny change $2x\equiv (\pm y)-1$. Don't see how Chinese Remainder Theorem is relevant, there is just one modulus around. You can just multiply $2x$ by $7$, the inverse of $2$, but there are faster ways, specially for $2$. – André Nicolas Nov 26 '11 at 17:00
Lemma 4.1.3( from number theory lecture notes): Let $p>2$ be prime and let $a \in Z$ such that $p \nmid a$. Here either a is not quadratic residue mod p or there are exactly two incongruent numbers mod p, whose quadratic residue is a. – alvoutila Nov 26 '11 at 17:02
@Andre: Do you mean $7\cdot2x \equiv 7\cdot(\pm y-1)\pmod{13}$. If so, what next? – alvoutila Nov 26 '11 at 17:30
Reduce modulo $13$. Note that $2\cdot 7=14\equiv 1 \pmod {13}$, so on the left side you get $x$, like you want. But for $2$, that's overkill. Use the suggestion in the answer by @Phira. – André Nicolas Nov 26 '11 at 17:40

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.

-

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.

-