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:

f(x) =

a0xn

+

a1xn−1

+ . . . + 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

p

q

∈ 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):

ax2

+ bxy +

cy2

+ dx + ey = f with a, b, c, d, e, f ∈ Z.