One way to think about this is the distance between solutions. Let's assume that the equation is \(ax+by=c\), and \(\gcd(a,b)=1\). Then, using out technique from last time, from the solution \((x_0,y_0)\) we get a new solution \((x_0+b,y_0-a)\), so the distance between any two solutions is, by the Pythagorean Theorem, \begin{equation*}\sqrt{[(x_0+b)-x_0]^2+[(y_0-a)+y_0]^2}=\sqrt{a^2+b^2}\, .\end{equation*} Our strategy is to ask:

• How many times does that distance fit between the intercepts of the line?

Does that strategy make sense? It doesn't give an exact answer, but should give a good ballpark estimate.

Let's calculate these things. You may want to follow it \(a=3\), \(b=2\), \(c=4\).

• The intercepts are \(\frac{c}{a}\) and \(\frac{c}{b}\), respectively.

• Using the Pythagorean Theorem again, we see that the whole length available is \begin{equation*}\sqrt{\Big(\frac{c}{a}\Big)^2+\Big(\frac{c}{b}\Big)^2}=\frac{c}{ab}\sqrt{a^2+b^2}\, .\end{equation*}

• The ratio of this total length and the length between solutions is thus \(\frac{c}{ab}\).

That's a nice pat answer. There are two problems with it, though!

1. There is no guarantee that \(\frac{c}{ab}\) is an integer! In fact, it usually won't be. For instance, with \(2x+3y=10\), \(\frac{10}{2\cdot 3}\approx 1.67\). So should the number of points be bigger than or less than this?

2. Secondly, even so it's not clear what the precise connection between \(\frac{c}{ab}\) and the actual number of points is. \(2x+3y=5\) has one, and \(2x+3y=7\) has one, but \(2x+3y=6\) doesn't. Yet \(\frac{c}{ab}\) is about equal to one for all three of these. In fact, the number of points is thus not even monotone increasing with respect to \(c\) increasing, which is rather counterintuitive.

We will have to deal with each of these situations.

We can deal with each of these problems. To do so, we introduce a new function:

Now let's use this to rectify our problems.

1. To take care of the integer problem, we will just consider \(n=\left\lfloor \frac{c}{ab}\right\rfloor\), the greatest integer function applied to \(\frac{c}{ab}\).

2. Secondly, we simply recognize that there isn't a nice formula. On average, we should expect \(n\) lengths between integer points along the line segment in question (and hence as many as \(n+1\) lattice points, since a partition of \(n\) intervals has \(n+1\) endpoints associated to it).

Rather than give a general formula, we examine individual cases to show what to expect. This applet helps.

Let's focus on the case where \(a\) and \(b\) are relatively prime.

1. How could the fewest lattice points appear? That's when both the \(x\)- and \(y\)-intercepts actually are lattice points, because they do not have positive coordinates. So if \(c/a\) and \(c/b\) are both integers, then we get precisely \begin{equation*}n-1=\left\lfloor \frac{c}{ab}\right\rfloor-1\end{equation*} lattice points. This is the transition between \(2x+3y=5\) to \(2x+3y=6\).

2. What if just one of the intercepts is a lattice point? Then, beginning at that point, there is definitely room for the full \(n\) lengths to appear, and you're guaranteed to get \(n\) lattice points, because we just said the other intercept isn't a lattice point, so the \(n\)th one must appear before that point. So here the formula is just plain old \begin{equation*}n=\left\lfloor \frac{c}{ab}\right\rfloor\; .\end{equation*} Compare \(2x+3y=8\) and \(2x+3y=9\) to the others above.

3. Finally, if neither \(c/a\) nor \(c/b\) is an integer, then you get \(n\) or \(n+1\) lattice points (remember, \(n=\left\lfloor \frac{c}{ab}\right\rfloor\)). There's no nice formula for this otherwise; but notice that with \(2x+3y=11\) you do get \(\left\lfloor \frac{11}{2\cdot 3}\right\rfloor+1=2\) positive lattice points! (And it jumps back down to \(\left\lfloor\frac{12}{2\cdot 3}\right\rfloor-1=1\) at \(c=12\)!

For more details, see the excellent book The Geometry of Numbers [C.3.15].

If \(\gcd(a,b)\neq 1\), it is not too hard to show that any such line with respect to lattice points is the same as a line \(a'x+b'y=c'\) for which \(\gcd(a',b')=1\). Which line would that be?