18 2. Elliptic curves
(a) Can we determine if Eq. (2.1) has any integral solutions,
xi ∈ Z, or rational solutions, xi ∈ Q?
(b) If so, can we find any of the integral or rational solutions?
(c) Finally, can we find all solutions and prove that we have
found all of them?
The first question was proposed by David Hilbert: to devise a
process according to which it can be determined in a finite number
of operations whether the equation is solvable in rational integers.
This was Hilbert’s tenth problem out of 23 fundamental questions
that he proposed to the mathematical community during the Second
International Congress of Mathematicians in Paris in the year 1900.
Surprisingly, in 1970, Matiyasevich, Putnam and Robinson discovered
that there is no such general algorithm that decides whether equation
(2.1) has integer solutions (see [Mat93]). However, if we restrict our
attention to certain particular cases, then we can answer questions
(a), (b) and (c) posed above. The most significant advances have
been obtained in equations with one and two variables:
• Polynomials in one variable:
+ . . . + an = 0
with ai ∈ Z. This case is fairly simple. The following crite-
rion determines how to search for rational or integral roots
of a polynomial: if
∈ Q is a solution of f(x) = 0, then an
is divisible by p and a0 is divisible by q.
• Linear equations in two variables:
ax + by = d
with a, b, d ∈ Z and ab = 0. Clearly, this type of equa-
tion always has an infinite number of rational solutions. As
for integral solutions, Euclid’s algorithm (to find gcd(a, b))
determines if there are solutions x, y ∈ Z and, if so, pro-
duces all solutions. In particular, the equation has integral
solutions if and only if d is divisible by gcd(a, b).
• Quadratic equations (conics):
+ bxy +
+ dx + ey = f with a, b, c, d, e, f ∈ Z.