Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.