Algorithms for Determining the Quadratic Character

In the following we will present various ways of computing the symbol $$(\frac{a} {b})$$ . Basically two methods have been applied. One is based on a direct application of the reciprocity law, and the other on a development of the fraction $$\frac{a} {b}$$ into a continued fraction. In the latter case $$(\frac{a} {b})$$ may be computed both from the quotients and the residues that occur in the development as a continued fraction. The first method is easily explained by an example. Assume we have to compute $$(\frac{365} {847})$$ . Then we find $$\displaystyle\begin{array}{rcl} \Big(\frac{365} {847}\Big)& =& \Big(\frac{847} {365}\Big)\qquad \qquad \qquad \qquad \qquad \qquad \qquad \text{since}\ 365 \equiv 1\bmod 4, {}\\ & =& \Big(\frac{117} {365}\Big) =\Big (\frac{365} {117}\Big) =\Big ( \frac{14} {117}\Big) =\Big (\frac{117} {14} \Big) {}\\ & =& \Big( \frac{5} {14}\Big) =\Big (\frac{14} {5} \Big) =\Big (\frac{-1} {5} \Big) = +1, {}\\ \end{array}$$ hence1 $$(\frac{365} {847}) = +1$$ .