0
$\begingroup$

Check which $a$ has a square root modulo $p$ for each $a$ and $p$ below:

$(a) a=3\space \text{and}\space p=11$

$(b) a=-1\space \text{and}\space p=59$

$(c) a=36\space \text{and}\space p=37$

I feel like this is extremely simple, but I'm having trouble understanding what is being asked. Could someone tell me how to solve one, or point me in the right direction, so I can edit this post and add some work.

2 Answers 2

2

Have you heard of the Legendre symbol? Looking at the Wikipedia article, we see there are two "definitions" and they happen to be equivalent. One is $\left(\frac{a}{p}\right) = \begin{cases} 1 \text{ if $a$ is a quadratic residue modulo $p$ and $a \not\equiv 0\pmod{p}$} \\ -1 \text{ if $a$ is a quadratic non-residue modulo $p$}\\ 0 \text{ if } a \equiv 0 \pmod{p}. \end{cases} $

and the other is

$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\ \pmod{ p}\;\;\text{ and } \left(\frac{a}{p}\right) \in \{-1,0,1\}.$

where a quadratic residue is a number that has a square root. Since the two definitions are equivalent, you can use the second one to easily calculate things. For example,

$3^{(11-1)/2} \equiv 3^5 \equiv 9 \cdot 9 \cdot 3 \equiv (-2)(-2)(3) \equiv 1 \mod 11$

Thus, from the first definition, 3 is a quadratic residue mod 11. Or, 3 has a square root mod 11. If you just try a few values, you can find that $5^2 = 25 = 3 \mod 11$. You can always just square every number and see what you get. But, for example, are you going to want to square 0 through 36 and reduce those all mod 37 to see if 36 has a square root? Or, if your numbers were even bigger, would you want to do that? Probably not without a computer at least.

You can also read down further in that article, including quadratic reciprocity, to see another way to calculate these which might be easier when your numbers get big.

3

As $59\equiv-1\pmod 4,-1$ is not a quadratic residue of $59$ unlike $37\equiv 1\pmod 4$ using Euler's Criteria.

Clearly,$36=6^2$ So, $(\pm 6)^2 \equiv 36\equiv -1\pmod {37}$

We need to find $x^2\equiv a=3\pmod {11}$.

As $11$ is too small,we can directly try to find $x$ instead of using Euler's Criteria.

$(\pm 1)^2\equiv 1, (\pm 2)^2\equiv 4,(\pm 4)^2\equiv 9, (\pm 4)^2=16\equiv 5,(\pm 5)^2=25\equiv 3\pmod {11}$

So, $(\pm 5)^2 \equiv 3\pmod {11}$