Cornacchia's algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation 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[edit]

First, find any solution to r_0^2\equiv-d\pmod 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 r0m/2 (if not, then replace r0 with m - r0, which will still be a root of -d). 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_k^2}d} is an integer, then the solution is x=r_k,y=s; otherwise there is no primitive solution.

To find non-primitive solutions (x, y) where gcd(x, y) = g ≠ 1, note that the existence of such a solution implies that g2 divides m (and equivalently, that if m is square-free, then all solutions are primitive). Thus the above algorithm can be used to search for a primitive solution (u, v) to u2 + dv2 = m/g2. If such a solution is found, then (gu, gv) will be a solution to the original equation.


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.


  1. ^ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione \sum_{h=0}^nC_hx^{n-h}y^h=P.". Giornale di Matematiche di Battaglini 46: 33–90. 

External links[edit]

Basilla, Julius Magalona (12 May 2004). "On Cornacchia's algorithm for solving the diophantine equation u^2+dv^2=m" (PDF).