0
$\begingroup$

Find all solutions of equation $x^2 \equiv 2$ in $\Bbb Z_{7}$

I'm not sure how to do this generally so I just powered through the first $10$-$15$ possible values for $[2]$ in $\mod 7$ and I found that the only possible values are $x=3$ and $x=4$.

$3^2=9$ which is $2 \mod 7$

$4^2=16$ which is $2 \mod 7$

all the other possible numbers that I went through are not perfect squares so they couldn't be $x$.

So how would I go about doing this without guessing a testing?

$\endgroup$
  • 1
    $\begingroup$ 10 - 15 possible values ? There are only 7 possible values of x, try them and find 3 and 4 $\endgroup$ – Tom Collinge Feb 23 '14 at 15:16
  • $\begingroup$ There are only $7$ numbers to test ($5$ is you don't count the trivial $0$ and $1$). Also, you really calculate two of them at a time when you calculate because of $(-x)^2 = x^2$. So you only need to do three calculations and some thinking (see @Hagen's answer below) $\endgroup$ – Arthur Feb 23 '14 at 15:17
  • 1
    $\begingroup$ Would it be easier for you to solve $x^2\equiv9\pmod7$? $\endgroup$ – Mike Feb 23 '14 at 15:19
  • 1
    $\begingroup$ To make life easier for yourself, when working modulo $2n+1$, the possible remainders are $0,\pm1,\ldots,\pm n$. $\endgroup$ – Lucian Feb 23 '14 at 15:26
4
$\begingroup$

Notice that $2=3^2$ and then $$x^2=3^2\iff (x-3)(x+3)=0$$ and since $\Bbb Z_7$ is a field ($7$ is prime) then $x=\pm 3$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Instead of probing different represantatives of $[2]$ until you fall asleep, just compute $x^2$ for $0\le x<7$ and check if the result is $\equiv 2\pmod 7$. (More smartly: try $-3\le x\le 3$)

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Strangely. When I decided equation:

$$x^2=7y+2$$

When I decided equation:

$$x=7k+4$$

$$y=7k^2+8k+2$$

$$...$$

$$x=7k-3$$

$$y=7k^2-6k+1$$

$$...$$

$$x=14k+4$$

$$y=28k^2+16k+2$$

$$...$$

$$x=14k-3$$

$$y=28k^2-12k+1$$

$k$ - any integer. It's not by the module to be considered and the equation to solve.

| cite | improve this answer | |
$\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.