View source for Cornacchia's algorithm

In [[Computational number theory|computational number theory]], '''Cornacchia's algorithm''' is an [[Algorithm|algorithm]] for solving the [[Diophantine equation]] <math>x^2+dy^2=m</math>, where <math>1\le d<m</math> and ''d'' and ''m'' are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.<ref>{{cite journal|last=Cornacchia|first=G.|year=1908|title=Su di un metodo per la risoluzione in numeri interi dell' equazione <math>\sum_{h=0}^nC_hx^{n-h}y^h=P</math>.|journal=Giornale di Matematiche di Battaglini|volume=46|pages=33–90}}</ref>
==The algorithm==
First, find any solution to <math>r_0^2\equiv-d\pmod m</math> (perhaps by using an algorithm listed here); if no such <math>r_0</math> exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that {{math|''r''<sub>0</sub> ≤ {{sfrac|''m''|2}}}} (if not, then replace {{math|''r''<sub>0</sub>}} with {{math| ''m'' - ''r''<sub>0</sub>}}, which will still be a root of {{math|-''d''}}).  Then use the [[Euclidean algorithm]] to find <math>r_1\equiv m\pmod{r_0}</math>, <math>r_2\equiv r_0\pmod{r_1}</math> and so on; stop when <math>r_k<\sqrt m</math>. If <math>s=\sqrt{\tfrac{m-r_k^2}d}</math> is an integer, then the solution is <math>x=r_k,y=s</math>; otherwise try another root of {{math|-''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 {{math|(''x'', ''y'')}} where {{math| gcd(''x'', ''y'') {{=}} ''g'' ≠ 1}}, note that the existence of such a solution implies that {{math|''g''<sup>2</sup>}} divides {{mvar|m}} (and equivalently, that if {{mvar|m}} is [[Square-free integer|square-free]], then all solutions are primitive).  Thus the above algorithm can be used to search for a primitive solution {{math|(''u'', ''v'')}} to {{math| ''u''<sup>2</sup> + ''dv''<sup>2</sup> {{=}} {{sfrac|''m''|''g''<sup>2</sup>}}}}.  If such a solution is found, then {{math|(''gu'', ''gv'')}} will be a solution to the original equation.

==Example==
Solve the equation <math>x^2+6y^2=103</math>. A square root of &minus;6&nbsp;(mod&nbsp;103) is 32, and 103&nbsp;≡&nbsp;7&nbsp;(mod&nbsp;32); since <math>7^2<103</math> and <math>\sqrt{\tfrac{103-7^2}6}=3</math>, there is a solution ''x''&nbsp;=&nbsp;7,&nbsp;''y''&nbsp;=&nbsp;3.

==References==
<references/>

==External links==
* {{cite journal|url=http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1116442240|title=On the solutions of <math>x^2+dy^2=m</math>|last=Basilla|first=J. M. |journal=Proc. Japan Acad. |volume=80(A) |year=2004 |pages=40-41 |format=PDF}}

{{number theoretic algorithms}}

[[Category:Number theoretic algorithms]]

{{Sourceattribution|Cornacchia's algorithm}}