In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation x 2 + d y 2 = m {\displaystyle x^{2}+dy^{2}=m} , where 1 ≤ d < m {\displaystyle 1\leq 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 ≡ − d ( mod m ) {\displaystyle r_{0}^{2}\equiv -d{\pmod {m}}} (perhaps by using an algorithm listed here); if no such r 0 {\displaystyle r_{0}} 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 r 1 ≡ m ( mod r 0 ) {\displaystyle r_{1}\equiv m{\pmod {r_{0}}}} , r 2 ≡ r 0 ( mod r 1 ) {\displaystyle r_{2}\equiv r_{0}{\pmod {r_{1}}}} and so on; stop when r k < m {\displaystyle r_{k}<{\sqrt {m}}} . If s = m − r k 2 d {\displaystyle s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}} is an integer, then the solution is x = r k , y = s {\displaystyle x=r_{k},y=s} ; 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 x 2 + 6 y 2 = 103 {\displaystyle x^{2}+6y^{2}=103} . A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since 7 2 < 103 {\displaystyle 7^{2}<103} and 103 − 7 2 6 = 3 {\displaystyle {\sqrt {\tfrac {103-7^{2}}{6}}}=3} , there is a solution x = 7, y = 3.
External links
- Basilla, J. M. (2004). "On the solutions of x 2 + d y 2 = m {\displaystyle x^{2}+dy^{2}=m} " (PDF). Proc. Japan Acad. 80(A): 40–41. doi:10.3792/pjaa.80.40.
References
Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione ∑ h = 0 n C h x n − h y h = P {\displaystyle \sum _{h=0}^{n}C_{h}x^{n-h}y^{h}=P} ". Giornale di Matematiche di Battaglini. 46: 33–90. ↩