\documentclass[11pt]{amsart}

\pagestyle{empty}

\title{Comment on Solution of Quadratic Congruences}
\author{Alberto Tonelli}
\thanks{
	Cf.~\emph{Bemerkung \"uber die
	Aufl\"osung quadratischer Congruenzen}, 
	Nachr.~d.~Akad. d. Wiss. in G\"ottingen 1891, 344--346.
	Excerpt from letters dated 1891-04-18 and 1891-06-15.}

\begin{document}

\begin{abstract}
We have extended the well-known method of general solution of a
quadratic congruence for prime moduli not of the form $4h+1$, in
the way that it can now be applied to primes of said form.
\end{abstract}
\maketitle

If the congruence
$$xx\equiv c \pmod{p}$$
is to be solved, and also one arbitrary quadratic non-residue $g\pmod{p}$
is known, then the following shows the algorithm.

Let $p=\alpha2^s+1$, where $\alpha$ is odd and $s\ge1$, then it holds
by the theorem of Euler that
$$c^{\alpha2^{s-1}}\equiv+1,\quad g^{\alpha2^{s-1}}\equiv-1\pmod{p}.$$

If also $s\ge2$ then from the first of both congruences a new one follows
$$c^{\alpha2^{s-1}}\equiv\pm1\pmod{p}.$$

Let now $\varepsilon_0=0$ if the upper sign $(+)$ applies, and
$\varepsilon_0=1$\footnote{['$\varepsilon_1=1$' in the original --- RS]}
if it is the lower $(-)$, so it always holds that
$$g^{\varepsilon_0\alpha2^{s-1}}c^{\alpha2^{s-2}}\equiv\pm1\pmod{p}.$$

If now additionally $s\ge3$ then follows
$$g^{\varepsilon_0\alpha2^{s-2}}c^{\alpha2^{s-3}}\equiv\pm1\pmod{p}.$$

If $(+)$ holds here then we set $\varepsilon_1=0$, and if it is $(-)$
then $\varepsilon_1=1$, so that always
$$g^{\varepsilon_1\alpha2^{s-1}}g^{\varepsilon_0\alpha2^{s-2}}c^{\alpha2^{s-3}}\equiv\pm1\pmod{p}.$$

This way one gets the congruence
$$g^{\alpha2^{s-k}(\varepsilon_0+\varepsilon_12+\dotsb+\varepsilon_{k-1}
2^{k-1})}c^{\alpha2^{s-k-1}}\equiv1\pmod{p}$$
as long as $k<s$; thus for $k=s-1$
$$g^{\alpha2(\varepsilon_0+\varepsilon_12+\dotsb+\varepsilon_{s-2}
2^{s-2})}c^{\alpha}\equiv1\pmod{p}$$
and therefore
$$x\equiv\pm g^{\alpha(\varepsilon_0+\varepsilon_12+\dotsb+\varepsilon_{s-2}
2^{s-2})}c^{\frac{\alpha+1}2}\pmod{p}$$
gives the solution of the congruence
$$xx\equiv c \pmod{p}.$$

From this solution we get with
$$x_1\equiv x^{p^{\lambda-1}}c^{\frac{p^\lambda-2p^{\lambda-1}+1}2}
\pmod{p^\lambda}$$
a general solution of the congruence
$$x_1x_1\equiv c \pmod{p^\lambda},$$
as can be easily seen by usage of Fermat's general theorem and the fact
that if
$$a\equiv b\pmod{p} \qquad\text{then also}\qquad 
a^{p^{\lambda-1}}\equiv b^{p^{\lambda-1}}\pmod{p^\lambda}.$$

These formulas for the roots are not only theoretically remarkable but,
in cases where other methods fail, they can be of practical importance
for the computation of roots of quadratic congruences.


\end{document}