Cornacchia's algorithm
In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation [math]\displaystyle{ x^2+dy^2=m }[/math], where [math]\displaystyle{ 1\le d\lt m }[/math] and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.[1]
The algorithm
First, find any solution to [math]\displaystyle{ r_0^2\equiv-d\pmod m }[/math] (perhaps by using an algorithm listed here); if no such [math]\displaystyle{ r_0 }[/math] exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that r0 ≤ m/2 (if not, then replace r0 with m - r0, which will still be a root of -d). Then use the Euclidean algorithm to find [math]\displaystyle{ r_1\equiv m\pmod{r_0} }[/math], [math]\displaystyle{ r_2\equiv r_0\pmod{r_1} }[/math] and so on; stop when [math]\displaystyle{ r_k\lt \sqrt m }[/math]. If [math]\displaystyle{ s=\sqrt{\tfrac{m-r_k^2}d} }[/math] is an integer, then the solution is [math]\displaystyle{ x=r_k,y=s }[/math]; otherwise try another root of -d 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 (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.
Example
Solve the equation [math]\displaystyle{ x^2+6y^2=103 }[/math]. A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since [math]\displaystyle{ 7^2\lt 103 }[/math] and [math]\displaystyle{ \sqrt{\tfrac{103-7^2}6}=3 }[/math], there is a solution x = 7, y = 3.
References
- ↑ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione [math]\displaystyle{ \sum_{h=0}^nC_hx^{n-h}y^h=P }[/math].". Giornale di Matematiche di Battaglini 46: 33–90.
External links
- Basilla, J. M. (2004). "On the solutions of [math]\displaystyle{ x^2+dy^2=m }[/math]" (PDF). Proc. Japan Acad. 80(A): 40-41. http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1116442240.
 |  |
