# Thread: [SOLVED] quadratic residues congruence problem

1. ## [SOLVED] quadratic residues congruence problem

list all solutions of...the ten congruences $\displaystyle x^2\equiv a\mod 11^2$ where $\displaystyle a=1,3,4,5,9$.
We know that each congruence has two solutions, and that if we can find one solution $\displaystyle x\equiv s$ then the second solution is $\displaystyle x\equiv-s$. But I don't know any algorithms I can use to solve each of the first solutions, except trial and error, which of course is far too inefficient.

This is an exercise in the chapter for quadratic residues, so presumably that has something to do with it.

Any ideas would be appreciated.

2. Well first off solving $\displaystyle x^2 \equiv 1 \mod{p}$ is easy: $\displaystyle x = \{-1,1\}$.

3. Quite so.

And of course if $\displaystyle \sqrt{a}\in\mathbb{Z}$ then $\displaystyle x\equiv\pm\sqrt{a}$ are solutions to $\displaystyle x^2\equiv a\mod 11^2$. So cases $\displaystyle a=1,4,9$ are easy to solve in that manner.

However, for cases $\displaystyle a=3,5$, I am at a loss for an efficient method.

4. Originally Posted by hatsoff
We know that each congruence has two solutions, and that if we can find one solution $\displaystyle x\equiv s$ then the second solution is $\displaystyle x\equiv-s$. But I don't know any algorithms I can use to solve each of the first solutions, except trial and error, which of course is far too inefficient.

This is an exercise in the chapter for quadratic residues, so presumably that has something to do with it.

Any ideas would be appreciated.

Since $\displaystyle 5^2=6^2=3\!\!\!\!\pmod{11}$ , the solutions for the same congruence modulo $\displaystyle 11^2$ have to be $\displaystyle 5\,,\,6\!\!\!\!\pmod{11}$ , so you have to check "only" these cases:

$\displaystyle 5,16,27,38,49,60,71,82,93,104,115$...and indeed $\displaystyle 27^3=(-27)^2=94^2=3\!\!\!\!\pmod{121}$.

Do something simmilar with the rest.

Tonio