Line Segment Passes through a Pair of Integers

Is there any way to test whether a line segment in a 2D cartesian plane ever passes through a point where both coordinates are integers? Obviously, you can loop through all integers along one axes and solve for the other coordinate, then test if that’s an integer, but I’m hoping there’s something in the O(1) scale of determination.

The subject you want to look up is “linear diophantine equations”.

Assuming that the line segment connects (x_left, y_left) to (x_right, y_right), you should be able to set this up as a simple mixed integer program:



minimize           1
subject to         x <= x_max
                   x >= x_min
                   y <= y_max
                   y >= y_min
                   x = (1 - t)*x_left + t*x_right
                   y = (1 - t)*y_left + t*y_right
                   t <= 1
                   t >= 0
                   x is an integer
                   y is an integer


Here x_min = min(x_left, x_right), x_max = max(x_left, x_right), y_min = min(y_left, y_right) and y_max = max(y_left, y_right).

There are open source/free solvers which will either return an integer pair on the line segment or prove that it’s impossible.

just out of curiousity for us math-o-phobes:
Why does anybody need to solve this problem? What is it useful for in the real-world ?

Now, I understand why slopes of lines are important, and calculating intersections between two lines is useful. You have two sets of data,(maybe trajectories of missiles, maybe statistics on life expectancy, whatever) — and want to see how they match or intersect…I get that. But why is it important to know if the intersection point is an even integer?

If there’s a way to do this (I mean other than methods that involve some sort of iteration or brute-forcing), wouldn’t it imply a method for finding prime factors?

Hmmm… For finding a factorization of N, you’re looking for an integer solution of X*Y = N, which is the equation of a hyperbola, so it does seem like it could be similar difficulty.

Why do you think it would?

There are probably other reasons, but the simplest I can think of is for calculations involving things that come in quantized chunks. Things in the real world often come in discrete units that can’t reasonably be broken into smaller parts.

Like, let’s say you were running a daycare, and the law says that you need an employee on staff for every 3.25 kids present. You want to find the points where the results of the equation are integers because both employees and kids only come in whole numbers. You can’t take care of half a kid, nor hire a third of an employee. You could round your employees up, but then you’re overpaying for labor.

That’s sort of a silly example, but there are lots of things like it. Think seats in an airplane (no good to have enough room in the cabin for another three-quarters of a seat) or bullets in a gun (probably should make the handle long enough for a magazine that holds an whole number).

The larger class of optimization problems in this area is Integer Linear Programming, which is NP-complete.

Yeah, what ZenBeam said, I think.

How is the line segment defined?

This might be relevant, even though it deals with lines rather than line segments.

Let’s say we know one point on the line (we’ll leave the segment part of the question alone) called (a, b) with slope m. For all real numbers r, a point is on the line iff it is in the form (a+r, b+mr)

First, we’ll look at lattice points as a subset of the rational points.
Assume that a, b are rational because if every ordered pair on the line has at least one irrational coordinate then clearly there are no lattice points on the line. m must be rational since r must be rational for a+r to be rational but then if m is irrational then b+mr would be irrational.

Lemma: If u,v are rational then u+v is an integer simultaneously with uv being an integer iff u and v are both integers (exercise left to the reader)

So if you could show that given a, b, m that there exists an r such that a + b + (m+1)r is an integer and that ab + (am+b)r + r^2 is an integer. Incidently, this last part would indicate that there must exist an integer n so that (am+b)^2 + 4abn must be a perfect square rational number for there to be a lattice point on the line. If so, then solve for r in the second equation and plug it into the first to see if you get an integer.

ETA: I research this approach for primality testing specific to Goldbach’s Conjecture and for finding lattice points on a hyperbola you pretty much end up with a circular logic problem where you need to know n to solve for n.

Chapter 2
Since we know that the slope m is rational and the point (a, b) means a, b are rational, we can look at the theoretical lattice point on the line (u, v) and we get (v-b)/(u-a) = m. A little bit of cleaning up since a and be are rational we will multiply the left side by c/c where c = lcd(a, b) so that now we have a’, b’, u’ and v’ that are integers ac, bc, uc, vc respectively.

since m=p/q we get q(v’-b’) = p(u’-a’) all integers and qv’-pu’ = qb’-pa’. p and q are relatively prime which means that (qb’-pa’) is a multiple of gcf(p, q) so I am guarantied an infinite number of integral solutions. But remember the transformation we did earlier? For u and v to both be integers u’ and v’ must both be divisible by c. This means that with one solution (x, y) that x+kq and y+kp must both be divisible by c for some value of k. If either x or y is divisible by c then choosing k as a multiple of c suffices. If not then you would need to solve kq=-x mod c and kp=-y mod c to see if you get the same k for both. If so there you go. If not then there is no lattice point on the line.

Example: (2/5, 3/8) is a point on the line with slope 3/7. What are the lattice points?
Solution: a’=16, b’=15; p=3; q=7
We get that Diophantine equation 7v’-3u’ = 57 which has a solution (9, 2).
c=40 and neither 9 nor 2 are divisible by 40. Every solution is in the form (9+3k, 2+7k) so for what k are these both divisible by 40? Solving 3k=31 mod 40 and 7k=38 mod 40. The first gives us k=31 and the second gives us k=38. Because the intersection of the solution set is null, we conclude there are no lattice points on the line.

Here’s an article that covers the basics of solving such a problem. Note that GCDs (which usually gets into the general form of Euclid’s Algorithm) can be quite helpful.

Why do we need to solve these things? In Real Life, certain things can’t be fractional. You can’t ship 21.8 refrigerators. More examples in the Wikipedia article for Integer Programming which is a much more complicated version of the OP’s problem.

Note that a straight line is a one-d curve. A hyperbole is two-d. A lot of problems that are simple to solve for one-d get really hairy for two-d. So the difficulty between the two don’t always correspond.

A hyperbola is one dimensional, just like a straight line or a circle. A hyperboloid is two-dimensional. And as I’ve told you a million times, a hyperbole isn’t a mathematical object at all.

Not necessarily. Suppose, for instance, that a = sqrt(2), b = pi, and m = pi/sqrt(2). All three of these numbers are irrational, yet the line still passes through an integer lattice point.

Example: (7/2, 5/6); m=5/3
Solution: a’=21; b’=5; p=5; q=3

3v’-5u’ = -90 => (21, 5) with c=6
3k=3 mod 6; 5k=1 mod 6 yields k=5 (means there are lattice points)
u’ => 21+5x3=36 and v’ => 5+5x5=30 => u=6 v=5

Therefore (6,5) is a lattice point on the line as any point in the form (6+3n, 5+5n)

Leaving out the obvious (degenerate?) case where the lattice point is (0, 0) because the given point is (p, q) and m = (q/p)

Well, it could be adapted to be any lattice point: Make a = sqrt(2) + x and b = pi + y.

Although, it also depends on just how the numbers are expressed. Write them that way, and it’s obvious what I’m doing, but what if I expressed a as the root of some polynomial or another, and b as the root of a different polynomial? And the question of how they’re expressed is quite relevant, given that in any given notational system, the vast majority of irrational numbers can’t be expressed at all.

I get what you’re saying.
Let’s then adapt mine to say assuming more than one rational point on the line because yours clearly would only have one rational point. Given that yours would only have one rational point, I’m trying to think how we would find it (or even my lattice point) from an arbitrary (non-rational) point on the line. I’ll have to think about that.

How does the computational burden of your solution grow if those single digit numbers become hundreds-of-digits numbers? Even assuming we stick to rational numbers, is Mangetout’s intuition correct?