0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Barry Cipra Oct 14 '14 at 14:56
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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