# Square roots and modular arithmetic

Find 4 different square roots of:

I have no idea how to get started on this, could someone explain what the first step would be?!

a. 1mod35

b. 1mod77

• At the very least, you can try squaring the numbers $1$, $2$, $3$, etc., and compute their remainders mod $35$ and $77$ and see what you get. – Barry Cipra Oct 14 '14 at 14:56

## 2 Answers

Since $35=5\cdot 7$, by the CRT, $x^2=1\pmod{35}$ is equivalent to
$\big(x^2=1\pmod{5}$ and $x^2=1\pmod{7}\big)$.

Hence the four solutions you want are:
$x=1 \pmod{5},~~~ x=1\pmod{7}$
$x=-1 \pmod{5},~~~ x=1\pmod{7}$
$x=1 \pmod{5},~~~ x=-1\pmod{7}$
$x=-1 \pmod{5},~~~ x=-1\pmod{7}$

Use the CRT to get the four solutions mod 35. The second problem is similar, since $77=7\cdot 11$.

In modular arithmetic, in say $\mod35$, a square root of $a\mod 35$ is a solution to the equation

$$x^2=a.$$

Now you have $(\pm 1)^2=1$, with $-1\equiv34\mod 35$, so that gives you two solutions and now you have to look for more...