How to calculate the square roots in $Z_n$ I have to calculate the square roots of $ [3] $ in $Z_{73}$.
Given that $73$ is prime, for a theorem:

If $p$ prime
$[a] \in Z_{p}$
$[a]$ has at maximum two square roots in the form $[k]$, $-[k]$

$[3]$ has at maximum two square roots.
After, I calculate the order of $73$ through Euler's totient function:

$\varphi(n)$ $:= \# \lbrace b$ such that $1 \leqslant b \leqslant n$ and $gdc(b, n)=1 \rbrace$
That is:

*

*$\varphi(n)$ is the number of smaller elements of b relatively prime with n

*$\varphi(n)$ is the number of invertible elements of $Z_{n}$

I find that the order of $73$ is $72$.

Given what I just said, what is the method to arrive at the solution?
The correct solutions of this exercise are $[21]$ and $[-21] = [52]$.
 A: Hint: Note that $3^{3}\equiv 100\pmod{73}$. It may also be useful to note that $3\cdot 24\equiv -1\pmod{73}$.
A: If $p$ is an odd prime, $a$ is a quadratic residue in $\mathbb{F}_p$ iff $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\equiv 1\pmod{p}$.
Quadratic reciprocity allows us to compute Legendre symbols pretty fast. In our case, since $73\equiv 1\pmod{4}$ and $73\equiv 1\pmod{3}$, we have that both $-1$ and $-3$ are quadratic residues, hence $3$ is a quadratic residue, too. $\pm 11$, on the other hand, is not a quadratic residue, since
$$\left(\frac{11}{73}\right)=\left(\frac{73}{11}\right)=\left(\frac{7}{11}\right)=-\left(\frac{11}{7}\right)=-\left(\frac{4}{7}\right)=-1,$$
hence the polynomial $x^2-x-3$ is irreducible over $\mathbb{F}_{73}$ and its roots belong to
$$ \mathbb{F}_{73^2}\simeq\mathbb{F}_{73}[x]/(x^2-x+3). $$
Such roots are of the form $\xi,\xi^{73}$ by Frobenius' automorphism, while by Vieta's formulas 
$$ 3= \xi\cdot \xi^{73}, $$
hence $\xi^{37}$ is a square root of $3$. Summarizing, it is enough to compute the remainder between $x^{37}$ and $x^2-x+3$ in $\mathbb{F}_{73}[x]$ to get a square root of $3$. Since
$$ x^{37}\pmod{x^2-x+3} = - 64624199 x - 630107040,$$
a square root of $3$ is given by $630107040\equiv\color{red}{21}\pmod{73}$. 
The outlined procedure is also known as the field extension or Cipolla-Lehmer algorithm: the Tonelli-Shanks algorithm is another viable alternative. It is interesting to point out that by performing the exponentiation $x^{37}$ in $\mathbb{F}_{73}[x]/(x^2-x+3)$ through repeated squaring, the two approaches turn out to be almost equivalent in terms of complexity.
