# Solving $2x^2 \equiv 7 \pmod{11}$

I'm doing some previous exams sets whilst preparing for an exam in Algebra.

I'm stuck with doing the below question in a trial-and-error manner:

Find all $x \in \mathbb{Z}$ where $0 \le x \lt 11$ that satisfy $2x^2 \equiv 7 \pmod{11}$

Since 11 is prime (and therefore not composite), the Chinese Remainder Theorem is of no use? I also thought about quadratic residues, but they don't seem to solve the question in this case.

• You only have 11 numbers to try, why not try each one by hand? – IanF1 Jan 4 '15 at 11:35
• When dealing with even powers, use the fact that $x^2=(-x)^2$, and halve your workload by rewriting the remainders modulo $2n+1$ as $0,\pm1\pm2,\pm3,\ldots,\pm n$. – Lucian Jan 4 '15 at 13:01

A first step in this could be to find the inverse of $2$, which turns out to be $6$, yielding $6\cdot2x^2\equiv x^2\equiv 6\cdot 7\mod 11\equiv 9\mod 11$. The obvious solutions to this are $3$ and $-3\equiv 8$. An important remark is that since $11$ is prime, there are at most two solutions to any given quadratic equation, so these are your desired solutions.

Notice however, that there can indeed be more solutions for non-primes. In these cases, the Chinese remainder theorem might be helpful. In a case like $x^2\equiv1\mod 12$, the solutions are $1, 5, 7$ and $11$. These correspond to the four combinations of $\pm1\mod3$ and $\pm1\mod4$. However, it isn't always possible to use this theorem. How would you, for instance, tackle $x^2=0$ working modulo $16$?

$2x^2 \equiv 7 \pmod {11} \iff x^2 \equiv 9 \pmod {11}$

so you should not be surprised by the solutions $x \equiv \pm3 \pmod {11}$

i.e. $x \equiv 3 \pmod {11}$ or $x \equiv 8 \pmod {11}$

• Although it's correct, it's missing the explanation why you can do that, so -1. – user2345215 Jan 4 '15 at 11:49

$$2x^2\equiv 7\pmod{11}\\2x^2\equiv -4\pmod{11}\\x^2\equiv -2\pmod{11}\\x^2\equiv 9\pmod{11}\\x^2\equiv\pm3\pmod{11}$$ As HSN mentioned since $11$ is prime than there are at most 2 solutions,

Hints:

• $6\cdot2=1\pmod{11}$
• $6\cdot7=9\pmod{11}$
• $ab=0\pmod{11}\iff (a=0\pmod{11}\vee b=0\pmod{11})$

$2x^2 - 7 \cong 2x^2 + 4 - 11 \cong 2(x^2+2)\pmod {11} \to x^2+2 = 0\pmod {11} \to x^2=-2\pmod {11}=9\pmod {11}\to x^2-9 = 0\pmod {11}\to (x-3)(x+3)=0\pmod {11}\to x-3=0\pmod {11} \text{ or } x+3 = 0\pmod {11}\to x=3,8$ $\text{since}$ $0\leq x < 11$.