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?