How to Find Rational Points Like Your Job Depends on It

You’re sitting at the end of a long conference table, interviewing for your dream job. You’ve made it this far, but there’s just one more question you have to answer.

“Is it possible for a line that passes through the origin to pass through no other rational points?”

Five pairs of intense eyes watch you, waiting for your response. Do you get the job?

You might think this only happens in story problems, but it happened to me. “Rational points” are points in the plane whose coordinates are all rational numbers. For example, $latex \left(\frac{12}{5},-\frac{2}{3}\right)$, $latex \left(3,\frac{1}{2}\right)$ and  (11, 4) are rational points, but (4, $latex\sqrt{2}$) and (π, -1) aren’t, since $latex\sqrt{2}$ and π are irrational. Rational points are important to number theorists and cryptographers, and they even lie at the heart of one of the most famous mathematical theorems of all time. But the question before me had to do with a line that passes through the origin, which means it has at least one rational point, namely (0, 0). Could it avoid passing through another? I didn’t know the answer right away, so I had to think about it.

At first it seems like the answer must be no. Around any point in the coordinate plane there are infinitely many rational points close by. With rational points so densely packed, it seems impossible that a line could avoid them all.

But, as it turns out, it is possible.

The key realization comes from thinking about the slope of the line. You may know slope as “rise over run”: This is just the ratio of the change in the y-coordinate (the “rise”) to the change in the x-coordinate (the “run”) as you move along the line. For example, if you were on a line with slope m and you increased your x-coordinate by 1, you would have to increase the y-coordinate by m to stay on the line. That’s how slope works.

Now imagine starting at (0, 0) on a line with slope m. Going 1 to the right and up m will put you on the line at the point (1, m). Thus, if m is rational, this line must pass through another rational point. In fact, the points (2, 2m), (3, 3m), and so on must all be on the line, showing that if a line through the origin has rational slope, it actually passes through infinitely many rational points.

To crack the interview question, you have to consider lines with irrational slopes. Once you do, the answer comes right away. For example, consider the line through the origin with slope $latex \sqrt{2}$, which has the equation y = $latex \sqrt{2}$x. If a point (a, b) lies on this line, then  b = $latex \sqrt{2}a$, and as long as a ≠ 0 we can rearrange this as $latex \frac{b}{a}$ = $latex \sqrt{2}$. But if  (a, b) is a rational point then this is impossible: The left-hand side of this equation can’t be rational while the right-hand side, $latex\sqrt{2}$, is irrational. So there can’t be any other rational points on this line. (An interesting extension question, which we explore in the exercises at the end of the column: Are there any lines in the plane that pass through no rational points?)

Quick thinking about lines got me the job, but mathematicians have been studying rational points on curves for a long time, and they’re still learning about the complex structure of these points. To get a sense of this, let’s take a look at how rational points work on circles in the plane. For simplicity we’ll just consider circles centered at the origin with radius r, whose equations are always

x² + y² = r².

Some of these circles pass through no rational points. But, curiously, if a circle contains one rational point, then it contains infinitely many. Let’s see why.

Consider the circle centered at the origin with radius 5. This circle has the equation x² + y² = 25, and it contains rational points, like (0, 5) and (3, 4), as well as other points, like (2, $latex\sqrt{21}$) and ($latex\sqrt{11}$, -$latex\sqrt{14}$). But knowing just one rational point on the circle can lead us to infinitely many others, and we can use what we just learned about lines to find them.

Imagine a line passing through the rational point (0, 5) on the circle, and let’s assume that the line has a rational slope, like 2. This line will pass through the circle at a second point, and it turns out this other intersection also has to be a rational point.

Some algebra will show us why. Since the line has slope 2 and y-intercept 5, we can write its equation as y =  2x + 5. The equation of the circle is x² + y² = 25, so to find the points of intersection, we just solve the following system of equations:

x² + y² = 25
y = 2x + 5.

One approach to solving this system is substitution: Since y = 2x + 5, we can substitute 2x + 5 for y in the circle equation to get

x² + (2x + 5)² = 25.

You might be tempted to just solve this equation using your favorite technique, but before we do that, let’s make a few observations.

First, this is a quadratic equation. Quadratic equations can have two solutions, or roots, and we already know one of them: Since (0, 5) is a point of intersection of the line and the circle, x = 0 must be a solution to our equation. Notice that this solution, or root, is rational.

Second, since all the numbers in the equation are rational, when we put our quadratic into “standard form” — ax² + bx + c = 0 — all the coefficients will be rational. A famous result known as Vieta’s formula says that for a quadratic equation in standard form, the sum of the roots is equal to -$latex \frac{b}{a}$. In our case this sum is rational, so if one root is rational, the other must be, too.

This means both points of intersection have rational x-coordinates, so the “run” between them is rational. And since the line passing through them has rational slope, their “rise” must be rational as well. This guarantees that the second point of intersection has a rational y-coordinate, making it a second rational point on the circle.

In our example it probably would have been easier to just solve the system of equations and find the other point of intersection, which turns out to be the rational point (-4, -3). But the argument above generalizes very nicely. Imagine any line y = mx + b with rational slope that passes through our circle at a rational point. The system of equations

x² + y² = 25
y = mx + b

results in the quadratic equation

x² + (mx + b)² = 25

which has all rational coefficients. By the argument above, if the line passes through the circle again, the other point of intersection must also be rational. So if you know one rational point on a circle, you can find infinitely many others just by taking a line with rational slope, passing it through your rational point, and finding the other point of intersection.

A similar approach can be taken to find rational points on so-called elliptic curves. These are “cubic” curves, with equations that have variables raised to the third power. They’re more complex than lines and circles and are of great interest to number theorists and cryptographers. The study of elliptic curves even played a major role in the solving of Fermat’s Last Theorem — a theorem about finding integer points on certain curves that was proved by Andrew Wiles in the 1990s (about 350 years after Pierre de Fermat famously claimed in the margin of a math book that he had a beautiful proof but the margin was too small to contain it).

There are many different kinds of elliptic curves. Here’s a simple example:

y² = x³ – 4x + 1.

And here is its graph in the plane:

Though it’s not obvious, there are many rational points on this elliptic curve. For example, (0, 1) and (4, 7) both lie on this curve, since

1² = 0³ – 4 × 0 + 1

and

7² = 4³ – 4 × 4 + 1.

And as with circles, there’s a clever way to use these known rational points to find more on the curve. The secret once again is using lines.

The equation of the line through (0, 1) and (4, 7) is easy enough to find: The slope is the change in y over the change in x, or m = $latex \frac{7-1}{4-0}$ = $latex \frac{6}{4}$ = $latex \frac{3}{2}$, and since the line passes through (0, 1), its y-intercept is 1. This makes the equation of the line through those two points y = $latex \frac{3}{2}$x + 1. Here’s the graph of the line along with the elliptic curve:

Notice that the line intersects the elliptic curve three times: at (0, 1), (4, 7) and a third unknown point. It turns out that the third point must also be rational.

Consider the elliptic curve and the line as a system of equations:

y² = x³ – 4x + 1
y = $latex \frac{3}{2}$x + 1.

We can substitute just like we did with the circle and the line. Here’s what we get:

$latex \left(\frac{3}{2} x+1\right)$² = x³ – 4x + 1.

This is a cubic equation with rational coefficients. A cubic equation can have up to three real solutions, which makes sense, because we are looking for three points of intersection. And we already know two of those solutions: x = 0, which corresponds to the point (0, 1), and x = 4, which corresponds to the point (4, 7).

So we know that two of the three solutions are rational. What about the third? Well, just as it did with our quadratic equation, Vieta’s formula guarantees that the sum of the roots of this cubic equation must be rational, so if two of the solutions are rational, the third must be rational, too. And that solution will lead us to a new rational point on the elliptic curve. It’s not hard to solve our cubic equation and find the third point of intersection to be $latex \left(-\frac{7}{4},-\frac{13}{8}\right)$. As with the circle, this argument generalizes: If a line intersects our elliptic curve at two rational points, then if there’s a third intersection, it must also be rational.

This technique is especially useful in combination with another nice feature of this elliptic curve. Notice that the graph is symmetric about the x-axis: The bottom half of the curve is a reflection of the top. Algebraically this means that if the point (a, b) is on the curve, the point (a, –b) must also be on the curve. Thus, if$latex \left(-\frac{7}{4},-\frac{13}{8}\right)$ lies on the curve, so does $latex \left(-\frac{7}{4}, \frac{13}{8}\right)$.

This symmetry does more than just give us another rational point on the curve. It gives us a new pair of points to run a line through.

The line through the rational points $latex \left(-\frac{7}{4}, \frac{13}{8}\right)$ and (0, 1) will yield yet another rational point on the curve. We can reflect that point, repeat our procedure, and continue to find even more rational points. This procedure has been exploited by mathematicians to create elliptic-curve cryptography, a means of creating secret codes that leverages the structure of these rational points on elliptic curves. It’s easy to use this procedure to find rational points on the curve, but if you’re just given a rational point, it’s difficult to figure out exactly where the procedure began. This sort of hard-to-reverse process is essential to making secure secret codes.

The rich structure of rational points on elliptic curves is an active area of mathematical research. Starting with the point (0, 1) we generated an infinite list of rational points on the curve y² = x³ – 4x + 1, each of which could lead us to the others. But there are more. The rational point (-1, 2) lies on the curve but isn’t on that list, and we can use it to generate a second infinite set of rational points on y² = x³ – 4x + 1. It turns out that every rational point on this curve is a combination of those two starting points, which means the “rank” of the curve is 2: Two starting points are all that are needed to generate all the infinitely many rational points on the curve. Mathematicians are actively studying the rank of curves like this, and it is currently unknown whether there is a maximum rank possible for elliptic curves.

From the search for integer solutions to equations 2,000 years ago to Fermat’s Last Theorem to elliptic-curve cryptography today, the study of rational points starts with high school algebra and geometry and leads to advanced mathematics in a beautiful and satisfying way. It may even help you land your dream job.

Exercises

1. Give the equation of a line that passes through no rational points.

2. The points (0, 1) and (4, -7) both lie on the elliptic curve y² = x³ – 4x + 1, and the equation of the line between them is y = -2x + 1. Yet the system of equations

y = -2x + 1
y² = x³ – 4x + 1

has only two distinct real solutions. Why doesn’t this conflict with the argument given in the column?

3. Show that the circle with equation x² + y² = 3 passes through no rational points.

4. What is the third point of intersection between the line through $latex \left(-\frac{7}{4}, \frac{13}{8}\right)$ and (0, 1) and the elliptic curve y² = x³ – 4x + 1? (Warning: only for algebra and arithmetic lovers!)

Answers

Click for Answer 1:

Click for Answer 2:

Click for Answer 3:

Click for Answer 4: