3
$\begingroup$

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.

Thanks in advance

$\endgroup$
  • 5
    $\begingroup$ You only have 11 numbers to try, why not try each one by hand? $\endgroup$ – IanF1 Jan 4 '15 at 11:35
  • $\begingroup$ 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$. $\endgroup$ – Lucian Jan 4 '15 at 13:01
6
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

$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}$

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

$$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,

$\endgroup$
1
$\begingroup$

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})$
$\endgroup$
1
$\begingroup$

$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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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