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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.