Square Root Mod

Question

On my homework it says $\sqrt{48}\pmod{73}$ but I have in my notes that $\sqrt{y\pmod{p}}\equiv y^{(p+1)/4}\mod{p}$. Which I feel like I should use. When I type it as it appears on the homework into wolfram alpha it says $4 \sqrt{3}$ is the answer. The hint is to use a table of $15^n\pmod{73}$. I am thoroughly confused. Please help.

Answer 1

Observe that $\;48=4^2\cdot 3\;$ , and since $\;73=1\pmod 4\;$ then

$$\binom 3{73}=\binom{73}3=\binom13=1$$

then $\;48\;$ is the product of two squares modulo $\;73\;$ and thus it iself is one of these.

Answer 2

$x\equiv \sqrt{48}\pmod{73}\iff x^2\equiv 48\pmod{73}$

This is the way you should see it.

Since $48 = 16\times 3= 4^2\times 3$

Then $x$ should be of the form $x=4y$ where $y^2\equiv 3\pmod{73}$

By extended Euclidean algorithm $3^{-1}\equiv 49\pmod{73}$

Thus $(3\times 7)^2\equiv (3\times 49)\times 3\equiv 1\times 3\equiv 3\pmod{73}$

Finally $x=4\times 21=84\equiv 11\pmod{73}$

Giving the result $$\sqrt{48}\equiv 11\pmod{73}$$

Rem: the other value being $-11\equiv 62\pmod{73}$.

Answer 3

Presumably if you have the table, then it renders $15^{26}\equiv 48$. So you get a square root by taking half that even exponent, thus $15^{13}\equiv ... $. Don't forget the additive inverse is a square root, too.