Csdrhrt

Given two points $A$ and $B$ on the $X-Y$-plane, I have to output the number of the lattice points on the segment $AB$. Note that $A$ and $B$ are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both $x$ and $y$ co-ordinate as an integer.

For example, for $A (3, 3)$ and $B (-1, -1)$ the output is $5$. The points are: $(-1, -1), (0, 0), (1, 1), (2, 2), (3, 3)$.

What is the procedure to solve this problem ?

HINT: Let one of the points be $langle a,brangle$ and the other $langle c,drangle$; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining $langle 0,0rangle$ to $langle c-a,d-brangle$. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to $langle m,nrangle$ for integers $m$ and $n$. Look at the equation of the line containing this segment: it’s

$$y=frac{n}mx;.$$

Suppose that when you reduce $frac{n}m$ to lowest terms, you get $frac{q}r$. Then your equation is

$$y=frac{q}rx;,$$

and $y$ is an integer if and only if $rmid x$.

Added: Suppose that the points are $langle -2,55rangle$ and $langle 1011,1055rangle$. I’d look at the segment from the origin to $langle 1011-(-2),1055-55rangle=langle 1013,1000rangle$. It lies on the line

$$y=frac{1000}{1013}x;.$$

Any lattice point on that line must have both $x$ and $y$ integers, so suppose that $x$ is an integer. When is $frac{1000}{1013}x$ an integer? The fraction is in lowest terms, so this occurs only when $x$ is a multiple of $1013$. On the other hand, we’re looking only at the segment between $langle 0,0$ and $langle 1013,1000rangle$, so clearly we must have $0le xle 1013$. How many multiples of $1013$ are there in this range? Just two, $0$ and $1013$. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding $langle 2,-55rangle$ to restore the original endpoints doesn’t change the number of lattice points, so $langle -2,55rangle$ and $langle 1011,1055rangle$ are the only lattice points on the original segment.

Let me explain this with an example:

The line segment with endpoints (−9, −2) and (6, 8) has
slope [8 − (−2)]/[6 − (−9)] = 10/15 = 2/3

This means that starting at (−9, −2) and moving “up 2
and right 3” (corresponding to the rise and run of 2 and
3) repeatedly will give other points on the line that have
coordinates which are both integers.
These points are (−9, −2),(−6, 0),(−3, 2),(0, 4),(3, 6),(6, 8).
So far, this gives 6 points on the line with integer coordinates.
Are there any other such points?

If there were such a point between (−9, −2) and (6, 8), its y-coordinate would have to be equal to one of −1, 1, 3, 5, 7, the other integer possibilities between −2 and 8.
Consider the point on this line segment with y-coordinate 7.
Since this point has y-coordinate halfway between 6 and 8, then this point must be the midpoint of (3, 6) and (6, 8), which means that its x-coordinate is 1/2(3 + 6) = 4.5, which is not an integer.
In a similar way, the points on the line segment with y-coordinates −1, 1, 3, 5 do not have integer x-coordinates.
Therefore, the 6 points listed before are the only points on this line segment with integer coordinates.

source: https://www.cemc.uwaterloo.ca/contests/past_contests/2018/2018CayleySolution.pdf