Cornacchia's algorithm explained

x ^{2+dy} ^{2=m} , where 1 \le d<m and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.^[1]

The algorithm

First, find any solution to

r ^{2 \equiv - d\pmod} _{0} m (perhaps by using an algorithm listed here); if no such r _{0} exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that (if not, then replace with, which will still be a root of). Then use the Euclidean algorithm to find r _{1\equiv} m\pmod{r _{0}} , r _{2\equiv} r _{0\pmod{r} _{1}} and so on; stop when r _{k<\sqrt} m . If s = \sqrt{\tfrac{m - r ^{2 }d}} _{k} is an integer, then the solution is x = r _{k,y=s} ; otherwise try another root of until either a solution is found or all roots have been exhausted. In this case there is no primitive solution.

To find non-primitive solutions where, note that the existence of such a solution implies that divides (and equivalently, that if is square-free, then all solutions are primitive). Thus the above algorithm can be used to search for a primitive solution to . If such a solution is found, then will be a solution to the original equation.

Example

Solve the equation

x ^{2+6y} ^{2=103} . A square root of -6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since 7 ^{2<103} and \sqrt{\tfrac{ 103-7 ^{2}6}=3} , there is a solution x = 7, y = 3.

References

1. Cornacchia. G.. 1908. Su di un metodo per la risoluzione in numeri interi dell' equazione \sum ^{n - h} _{hx} y ^{h=P} .. Giornale di Matematiche di Battaglini. 46. 33–90.

External links

• On the solutions of x ^{2+dy} ^{2=m} . Basilla. J. M. . Proc. Japan Acad. . 80(A) . 2004 . 40–41 . PDF.