# Find all solutions of equation $x^2 \equiv 2$ in $\mathbb Z/7\mathbb Z$

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

• 10 - 15 possible values ? There are only 7 possible values of x, try them and find 3 and 4 – Tom Collinge Feb 23 '14 at 15:16
• 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) – Arthur Feb 23 '14 at 15:17
• Would it be easier for you to solve $x^2\equiv9\pmod7$? – Mike Feb 23 '14 at 15:19
• To make life easier for yourself, when working modulo $2n+1$, the possible remainders are $0,\pm1,\ldots,\pm n$. – Lucian Feb 23 '14 at 15:26

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

Instead of probing different represantatives of $$ 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$)

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.