Cornacchia's algorithm

Template:Short description In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation $x^2+d{y}^2=m$, where $1\le d<m$ and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.

The algorithm

First, find any solution to $r_0^2\equiv -d(\mathrm{mod}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 Template:Math (if not, then replace Template:Math with Template:Math, which will still be a root of Template:Math). Then use the Euclidean algorithm to find $r_1\equiv m(\mathrm{mod}{r}_0)$, $r_2\equiv r_0(\mathrm{mod}{r}_1)$ and so on; stop when $r_k<\sqrt{m}$. If $s=\sqrt{\frac{m-r_k^2}{d}}$ is an integer, then the solution is $x=r_k,y=s$; otherwise try another root of Template:Math 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 Template:Math where Template:Math, note that the existence of such a solution implies that Template:Math divides Template:Mvar (and equivalently, that if Template:Mvar is square-free, then all solutions are primitive). Thus the above algorithm can be used to search for a primitive solution Template:Math to Template:Math. If such a solution is found, then Template:Math 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{\frac{103-7^2}{6}}=3$, there is a solution x = 7, y = 3.

External links

• Template:Cite journal