# Line Segment Passes through a Pair of Integers

**URL:** <https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287>\
**Category:** Factual Questions\
**Created:** [October 15, 2013, 4:39am UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287 "2013-10-15T04:39:26Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [October 15, 2013, 9:07pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/21 "2013-10-15T21:07:00Z")

</div>

Finding the GCD of two numbers using Euclid’s algorithm is much faster than factoring.

---

<div class="post-metadata">

**Author:** ![Learjeff](https://avatars.discourse-cdn.com/v4/letter/l/94ad74/32.png) [@Learjeff](https://boards.straightdope.com/u/Learjeff)\
**Post date:** [October 15, 2013, 9:08pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/22 "2013-10-15T21:08:40Z")

</div>

If the line is defined by floating point numbers, isn’t it possible that the line comes almost infinitessimally close to an integer point, but you won’t see it because of the resolution in the original numbers?

Seems to me that this is the kind of problem where even when you solve it correctly from a math standpoint, you’ll miss points you should hit due to quantization error. Using a method like **ultrafilter** ’s, you could replace “is an integer” with “is within _delta_ of an integer”.

---

<div class="post-metadata">

**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\
**Post date:** [October 15, 2013, 9:32pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/23 "2013-10-15T21:32:47Z")

</div>

> [@MilTan](#):
>
> Finding the GCD of two numbers using Euclid’s algorithm is much faster than factoring.

Is that the hardest part?

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [October 15, 2013, 10:03pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/24 "2013-10-15T22:03:11Z")

</div>

If all you want to do is figure out whether any point on a line (ax + by = c, where a, b and c are rational) intersects an integer point, yes. Constraining it to a segment is somewhat harder. The ILP solution **ultrafilter** suggested works, though in the general case, ILP is NP-complete.

---

<div class="post-metadata">

**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\
**Post date:** [October 15, 2013, 11:20pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/25 "2013-10-15T23:20:49Z")

</div>

> [@MilTan](#):
>
> If all you want to do is figure out whether any point on a line (ax + by = c, where a, b and c are rational) intersects an integer point, yes. Constraining it to a segment is somewhat harder. The ILP solution **ultrafilter** suggested works, though in the general case, ILP is NP-complete.

I’ve been assuming we want the solution, not just whether one exists.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 16, 2013, 2:21am UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/26 "2013-10-16T02:21:37Z")

</div>

> [@ZenBeam](#):
>
> I’ve been assuming we want the solution, not just whether one exists.

An ILP solver will give the solution if one exists.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [October 16, 2013, 2:23am UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/27 "2013-10-16T02:23:01Z")

</div>

> [@](#):
>
> Quoth **Learjeff** :
> 
> If the line is defined by floating point numbers, isn’t it possible that the line comes almost infinitessimally close to an integer point, but you won’t see it because of the resolution in the original numbers?

All numbers expressible as floating point numbers are rational, and hence one can in principle determine absolutely, yes or no, whether the line passes through a lattice point (though it might take longer to do it if your numbers are expressed to high precision). Alternately, if you meant a number that can’t be expressed exactly as a floating point number, but only approximated as one, well, then we’ve got a loss of information, with no way of recovering it, so of course we can’t be certain of getting the right answer.

**ZenBeam** , actually finding the solution is somewhat harder, but not by very much. In fact, it mostly consists of the same method you use to find out if the solution exists, except you keep a little closer track of what you’re doing.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 16, 2013, 2:24am UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/28 "2013-10-16T02:24:54Z")

</div>

I just realized that some of the constraints in my original problem formulation are redundant. This is the simpler version:

```auto

minimize 1
subject to 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

```

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 16, 2013, 3:05am UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/29 "2013-10-16T03:05:19Z")

</div>

There’s actually an embarrassingly simple algorithm for solving this problem that I should have thought of first:  
[ol]  
[li]Enumerate all the integers z with x\_left \<= z \<= x\_right.[/li][li]For each integer in this list, set t = (z - x\_left)/(x\_right - x\_left) and see if (1 - t)_y\_left + t_y\_right is an integer.[/li][/ol]

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [October 16, 2013, 11:47am UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/30 "2013-10-16T11:47:28Z")

</div>

**Sage Rat** suggested exactly that in the OP 😉

---

<div class="post-metadata">

**Author:** ![j\_sum1](https://avatars.discourse-cdn.com/v4/letter/j/8baadc/32.png) [@j\_sum1](https://boards.straightdope.com/u/j_sum1)\
**Post date:** [October 16, 2013, 1:35pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/31 "2013-10-16T13:35:38Z")

</div>

> [@ultrafilter](#):
>
> There’s actually an embarrassingly simple algorithm for solving this problem that I should have thought of first:  
> [ol]  
> [li]Enumerate all the integers z with x\_left \<= z \<= x\_right.[/li][li]For each integer in this list, set t = (z - x\_left)/(x\_right - x\_left) and see if (1 - t)_y\_left + t_y\_right is an integer.[/li][/ol]

That’s fine and probably quite practical for a line segment of reasonable length.  
I am actually more interested in the unbounded case. What is the proof that the line never passes through a lattice point.

And I concede that the solution depends entirely on the framing of the question: that is, how the line is defined.

I visualise a case where the line passes through the two points (a,b) and (c,d) where a, b, c and d are all irrational – say, the solution to a fifth order polynomial or the solution to a trig or exponential function or perhaps defined by an infinite series.  
Presented with one of these, I would intuitively guess that no lattice points would be touched. But there is a remote chance of my being wrong. It is theoretically possible.  
The question that then arises is where did the values a, b, c and d come from. Presumably they would have come from the same context – solutions to the same set of equations. And in unpacking that lies the answer to the question. I don’t doubt that arbitrary reals give rise to lines that never pass through lattice points – for the same reason that real numbers outnumber rationals.

---

<div class="post-metadata">

**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\
**Post date:** [October 16, 2013, 2:14pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/32 "2013-10-16T14:14:41Z")

</div>

Line is: y=mx+b

It seems to me if m is rational, then y=mx obviously has other points besides 0,0 that are integer.  
If m=a/d then y=ax/d or dy=ax, so d,a would be a solution?

Then - if I translate the line upward by “b” can we show it must still intercept a integer pair?  
I don’t think so, since the result adds an irrational to the y value.

If y=ax/d + b, but b is irrational - I can’t make a/d irrational and still have x integer.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [October 16, 2013, 2:45pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/33 "2013-10-16T14:45:10Z")

</div>

You’re assuming that b is an integer. Suppose m = 1 and b = .5:

y = x + .5

It should be obvious that there is no way to pass through lattice points (if y is an integer, then x cannot be, and vice-versa).

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [October 16, 2013, 4:51pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/34 "2013-10-16T16:51:42Z")

</div>

> [@Chronos](#):
>
> 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.

I don’t know what universe you live in, but in my Euclidean one, a straight line is one dimensional, a curved one isn’t. I’ll conceded the error on hyperbola. OTOH, as to “told you a million times”, cite?

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [October 16, 2013, 4:58pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/35 "2013-10-16T16:58:36Z")

</div>

I think that was a joke. Hyperbole, even.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [October 16, 2013, 5:24pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/36 "2013-10-16T17:24:46Z")

</div>

> [@j\_sum1](#):
>
> What is the proof that the line never passes through a lattice point.

Here goes (this is pretty much what **Saint Cad** posted, just written up slightly differently).

Let’s start by proving that if a and b are relatively prime (their GCD is 1), there exist some integer i and j such that:

a_i + b_j = 1

If a and b are relatively prime, then there must exist some k such that a \* k mod b = 1. Thus, if we set i = k, and j = -(a \* k - 1)/b, we have integer i and j that satisfy the equation.

We can extend this a little bit and say there must be integer i and j such that a_i + b_j = z for _any_ integer z (which you can get by multiplying through on the original equation).

Now let’s turn to the original question. Suppose we have a line, whose equation can be rewritten as:

a_x + b_y = c

Where a, b and c are rational. We can assume, without loss of generality, that a, b and c are integers (by multiplying through by the LCM of the denominators of a, b and c).

Let g be the GCD of a and b. We can rewrite the equation as:

a’\*x + b’\*y = c/g

Where a’ = a/g and b’ = b/g. Note that by definition, a’ and b’ are relatively prime. Thus, as long as c/g is an integer, we know there must exist some integer x and y that satisfy the equation by our earlier proof. Moreover, if c/g _is not_ an integer, there cannot be any integer x and y that satisfy the equation.

* * *

To show that there are an infinite number of possible solutions, note that for a’ and b’, there are an infinite number of non-zero, integer p and q such that:

a’ \* p + b’ \* q = 0

Which you can get by setting p to kb and q to -ka for some integer k. Thus if you find an (x, y) that solves the equation, (x + kb, y - ka) also solves it.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [October 16, 2013, 6:29pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/37 "2013-10-16T18:29:26Z")

</div>

> [@](#):
>
> Quoth **ftg** :
> 
> I don’t know what universe you live in, but in my Euclidean one, a straight line is one dimensional, a curved one isn’t.

You can specify a position along a curve by a single number. That’s the definition of one-dimensional.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [October 16, 2013, 9:18pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/38 "2013-10-16T21:18:56Z")

</div>

> [@Chronos](#):
>
> You can specify a position along a curve by a single number. That’s the definition of one-dimensional.

Uh, as opposed to being actually one dimension? You know, like a straight line?

And a “single number” is sort of useless. The position of any point in a two dimensional plane can be given by a single number by one of Cantor’s old trick. Saying a plane is one dimensional isn’t what most people would agree with. It’s a lousy metric, but it’s a single number.

Most people don’t think in terms of metrics when they talk about 1, 2 or 3-d. They think line, plane, space.

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [October 16, 2013, 9:57pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/39 "2013-10-16T21:57:58Z")

</div>

A curve is a one-dimensional object, but it exists within a two-dimensional space (the plane).

Cites:

> **[Fractal Dimension](https://www.math.stonybrook.edu/~scott/Book331/Fractal_Dimension.html)**
>
> Fractal Dimension

> **[Dimension -- from Wolfram MathWorld](https://mathworld.wolfram.com/Dimension.html)**
>
> The dimension of an object is a topological measure of the size of its covering properties. Roughly speaking, it is the number of coordinates needed to specify a point on the object. For example, a rectangle is two-dimensional, while a cube is...

> **[Dimension](https://en.wikipedia.org/wiki/Dimension)**
>
> In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordinate is needed to specify a point on it – for example, the point at 5 on a number line. A surface, such as the boundary of a cylinder or sphere, has a dimension of two (2D) because two coordinates are needed to specify a point on it – for example, both a In cl...

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [October 16, 2013, 10:03pm UTC](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287/40 "2013-10-16T22:03:05Z")

</div>

> [@](#):
>
> Uh, as opposed to being actually one dimension? You know, like a straight line?

Or, you know, like a curved line.

And the actual definition for dimensionality is of course a bit more rigorous, as it gets into matters of topology (the mapping of a plane to a line isn’t continuous). But that’s the gist of it. If you’d prefer, you could also say that a thing is one-dimensional if there’s a continuous one-to-one function between it and a line.

[Previous page](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287.md?page=1)

[Next page](https://boards.straightdope.com/t/line-segment-passes-through-a-pair-of-integers/671287.md?page=3)