Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  laovultai Nov 26 '11 at 17:02
    
@Andre: Do you mean $7\cdot2x \equiv 7\cdot(\pm y-1)\pmod{13}$. If so, what next? –  laovultai 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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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