- Cornacchia's algorithm
-
In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where
and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1].
Contents
The algorithm
First, find any solution to
; if no such r0 exist, there can be no solution to the original equation. Then use the Euclidean algorithm to find
,
and so on; stop when
. If
is an integer, then the solution is x = rk,y = s; otherwise there is no solution.
Example
Solve the equation x2 + 6y2 = 103. A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since 72 < 103 and
, there is a solution x = 7, y = 3.
References
- ^ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione
.". Giornale di Matematiche di Battaglini 46: 33–90.
External links
Morain, M.; Nicolas, J.-L. (12 September 1990). "On Cornacchia's algorithm for solving the diophantine equation u2 + dv2 = m" (PDF). http://www.gage.polytechnique.fr/~morain/Articles/cornac.pdf. Basilla, Julius Magalona (12 May 2004). "On Cornacchia's algorithm for solving the diophantine equation u2 + dv2 = m" (PDF). http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1116442240.
Categories:- Number theoretic algorithms
- ^ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione
Wikimedia Foundation. 2010.