In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation
x
2
+
d
y
2
=
m
, where
1
≤
d
<
m
and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.
First, find any solution to
r
0
2
≡
−
d
(
mod
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 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
)
,
r
2
≡
r
0
(
mod
r
1
)
and so on; stop when
r
k
<
m
. If
s
=
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
+
6
y
2
=
103
. A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since
7
2
<
103
and
103
−
7
2
6
=
3
, there is a solution x = 7, y = 3.